algorithm - 基于有向图树建立列表的年表

Question

因此，在我一直从事的个人项目中，我遇到了以下问题，由于我的数学技能不是特别好，我一直在努力想出一个解决方案。

假设您有以下数字树 abcdefgh：

    a
   / \
   b  c
 / |  |
g  d  f
|  |
h  e

树的每一步都意味着下一个数字大于前一个数字。所以a < b，d < e，a < c。但是，无法确定是 b > c 还是 c < b - 我们只能判断这两个数字都大于 a。

假设我们有一个有序的数字列表，例如 [a, b, c, d, e]。我们如何编写一个算法来检查列表中数字的顺序（假设 L[i] < L[i+1]）相对于我们根据这棵树获得的信息是否正确？

I. E，[a, c, b, d, e] 和 [a, b, d, c, e] 都是正确的，但 [c, a, b, d, e] 不是（因为我们知道c > a，但与其他数字的结构无关）。

为了算法的缘故，假设我们对树的访问是一个函数 provably_greater(X, Y) 如果树知道一个数字高于另一个数字，则返回 true。IE provably_greater(a, d) = True，但 provably_greater(d, f) = False。自然，如果一个数字可证明不更大，它也会返回 false。

这不是一个家庭作业问题，我已经对这个问题进行了很多抽象以使其更加清晰，但是解决这个问题对于我正在尝试做的事情非常重要。我自己曾多次尝试破解它，但我想出的一切最终都不足以应对我后来发现的一些极端情况。

提前致谢。

标签： algorithmmathgraph-algorithm

Answer 1

您的陈述“我想出的一切最终都不足以满足我以后发现的某些极端情况”，这使您似乎根本没有解决方案。这是一个适用于所有情况的蛮力算法。我可以想到几种可能的方法来提高速度，但这是一个开始。

首先，建立一个允许provably_greater(X, Y)基于树进行快速评估的数据结构。这个结构可以是一个集合或哈希表，这将占用大量内存但允许快速访问。对于树的每一片叶子，走一条到根的路径。在每个节点处，查看所有后代节点并将有序对添加到显示这两个节点的小于关系的集合中。在您的示例树中，如果您从节点开始，则h向上移动到节点并g添加(g,h)到集合中，然后向上移动到节点b并将对添加到集合中，然后向上移动到节点并将对添加到集合中. 对叶节点和做同样的事情。这对(b,h)(b,g)a(a,h)(a,g)(a,b)ef(a,b)由于叶节点h和，将被添加到集合中两次e，但是集合结构可以轻松处理此问题。

该功能provably_greater(X, Y)现在快速而简单：结果是True该对(Y,X)是否在集合中，False否则。

您现在查看列表中的所有数字对 - 对于列表[a,b,c,d,e]，您将查看数字对(a,b)、(a,c)、(b,c)等。如果provably_greater(X, Y)其中任何数字对为真，则列表无序。否则，列表是有序的。

这应该很容易用像 Python 这样的语言来实现。如果您想要一些 Python 3 代码，请告诉我。