3

感谢大家回复想法和替代解决方案。更有效的解决问题的方法总是受欢迎的，并且提醒我质疑我的假设。也就是说，我希望你暂时忽略我试图用算法解决的问题，并帮助我分析我的算法的复杂性，因为我已经编写了它——所有简单的路径在使用深度限制搜索的图表中，如此处所述，并在此处实现。谢谢！

编辑：这是家庭作业，但我已经提交了这个作业，我只想知道我的答案是否正确。当涉及到递归时，我对 Big-O 复杂性感到有些困惑。

下面的原始问题：

我试图找到该算法给出的所有路径搜索的复杂性。给定两个顶点，我使用深度优先搜索找到它们之间的所有简单路径。

我知道DFS的时间复杂度是O(V+E)，它的空间复杂度是O(V)，我的直觉是全路径搜索的复杂度会更多，但是我做不到确定它将是什么。

相关的 SO 问题在这里和这里。

更新（回应下面的评论）：

我正在尝试解决凯文培根的六度问题。这通常需要找到一对演员之间的最低分离度，但我必须找到所有的分离度（目前，小于 6，但这可以改变）。

4

4 回答 4

5

最坏的情况是（我认为）n个顶点上的完整图。该图有n ! 简单的路径，并且对于它们中的每一个，您的算法至少执行n ^2 计算步骤——对于与路径中最后一个相邻的每个顶点，它对先前访问过的节点的链表进行线性扫描。（这还不包括搜索的所有中间阶段。）所以复杂度至少为 O( n ^2 * n！)，可能更糟。

你要解决的更大的问题是什么？

于 2009-12-02T05:02:23.400 回答
1

6 度很好，因为它给了你一个限制。我意识到 6 可以改变，但我认为这里的方法仍然适用。在我说“6”的任何地方，只需用“# of degree”代替。

如果您愿意，可以使用广度优先搜索 (BFS)。如果我理解正确，您将获得一个起点（演员/女演员），您需要找到距离小于或等于 6 条边的端点（Kevin Bacon）的所有路径。您可以将其分解为子问题，首先找到所有距离 1 边的连接，然后找到所有距离 2 边的路径，...，最后找到所有距离 6 边的路径。这正是 BFS 的工作方式……首先检查一个边缘的所有节点，然后是两个，等等。

或者，您也可以使用修改后的深度优先搜索 (DFS)，通过执行正常的 DFS 并尽可能地沿着每条路径前进，但保留一个计数器并阻止它在任何特定路径的深度超过 6 个边缘。

我认为您的解决方案可能会比正常的 O(V + E) 好得多，因为您可能不会访问所有顶点或沿所有边旅行（假设我们的图表是大量参与者之间的关系），但是相反，您被限制在整个图的子图中。你开始你的搜索算法，就像你要访问所有顶点/边一样，但无论你使用 BFS 还是 DFS，你都会在起始顶点的 6 个边处停止，而不是查看整个图形.

考虑到像 DFS 这样的东西可以表示为 O(V+E)，但它也可以表示为 O(b^d)，其中 b 是分支因子，d 是图深度（有关更多信息，请参见Wikipedia_DFS）。那么考虑到有多少演员，b 会是什么？考虑到您对问题的了解（6 度等等），d 会是什么？

我想我可能已经说得够多了。希望这会为您启动它。我应该补充一点，我实际上并不确定答案，这就是我遇到的问题；）

于 2009-12-02T06:40:34.317 回答
1

用我的分析回答我自己的问题，请评论/更正！

The algorithm is simplified and analyzed as follows: 
(Note: here MAXDEPTH is the maximum degrees of separation to search for, default 6)
1. For the current vertex, get neighbors (amortized O(1))
2. For every neighbor, do the following [O(b), where b is the branching factor, or the avg. number of neighbors of a vertex]
2.1.    Check if already visited [O(MAXDEPTH), since it’s a linked list of max size MAXDEPTH)
2.2.    Append path to paths list [amortized O(1)]
3. End for 
4. Do the following MAXDEPTH times [O(MAXDEPTH)]
4.1.    For every neighbor do the following [O(b)]
4.1.1.      Check if already visited [O(MAXDEPTH)]
4.1.2.      Add to visited list [O(1)]
4.1.3.      Recursively call search again [becomes O(MAXDEPTH*b)]
4.1.4.      Delete from visited list [O(1)]
4.2 End for /* Neighbor */
5. End loop /* MAXDEPTH */

Thus, the complexity becomes O((MAXDEPTH*b)^MAXDEPTH).
于 2009-12-04T04:04:46.197 回答
0

我正在考虑使用O((n^2)*depth ) 算法

  1. 对于每个演员，找到他正在与之合作的所有演员。（O(n^2) 空间和时间复杂度，但都取决于实际连接数，对于大多数演员来说，Facebook 上的朋友数量不超过 500 或 5 倍）这带来了 500*n 的时间和空间复杂度。

  2. 将所有三个以相同深度组合起来，并附加所有这些连接。O(n^2*深度)

如果您使用双链树来存储连接，您可以找到深度*n 复杂度的所有连接

于 2009-12-02T08:00:33.467 回答