问题标签 [longest-path]

如何在没有权重的 DAG 中找到最长的路径？

我知道如果对 DAG 进行拓扑排序，则可以在线性时间内找到从 A 到 B 的最长路径，但我需要在所有图中找到最长的路径。有没有比搜索所有顶点对之间的最长路径更快的方法（这将是 O(n^3)）？

我正在寻找一种算法来确定网格上两点之间的最长路径，并增加了您无法重新访问网格上的单元格的限制。（此外，您只能向上、向下、向左和向右移动）。

考虑到这些限制，我想走最长的路径与试图填满尽可能多的空间是一样的。但是，我在弄清楚如何做到这一点时遇到了一些困难。

给定一个网格 G。每个单元格可以包含数字 [0 - 9] 或大写字母（比如 Z）；我们可以从左上角开始。然后，如果我们所在的单元格编号是 a，我们可以允许将一个单元格向上、向左或向右移动。直到我们到达一个字母字母，然后我们才停下来。鉴于这些规则，我们希望找到从开始到离开网格的最大路径。如果路径是无限的，打印“-1”；

我正在尝试使用 jGraphT 在 Java 中实现最长路径算法，但是在编译时出现 java.lang.StackOverflowError。错误消息指向我复制图形的行以及该方法在算法内部调用自身的行。我使用的算法描述是Liao Wong 最长路径，第 11 页。

我在哪里做错了什么？

大约一个月以来，我一直致力于制作游戏求解器，尝试了各种策略，但大多数都以蛮力为导向。这适用于更简单的游戏情况，但不适用于更复杂的情况（更高的游戏树深度）。这是游戏的抽象表述：

1）有一组可能的动作要做，A。

2) 将动作应用于状态会产生可能状态的概率分布。应用(A, s) = [[s1, p1], [s2, p2], [s3, p3]]

3) 当达到目标状态时，游戏结束。

4) 每个状态都有一个与之相关的分数。

3) 有两种类型的目标状态，“成功”状态的得分是其前一状态的得分，“失败”状态的得分为 0。

5) 目标是制定一种策略，使游戏结束时的平均得分最大化。

6) 没有循环。所有路径的长度都是有限的。

我尽可能以最抽象的方式制定游戏，因为我认为这是人们最熟悉的游戏。我目前的策略是一个简单的深度优先搜索，它缓存独特的状态以防止工作重复。这一直有效到大约 2 亿个唯一状态，这是我内存不足的时候。在我开始分解较低级别的细节以找到优化之前，我想知道是否有任何巧妙的算法适用于游戏的一般情况。如果有人对如何生成状态转换的细节感兴趣，我可以提供。以下是我将问题减少为已知问题的一些方法。

1) 随机马尔可夫决策过程，其中状态奖励函数对于任何非目标状态为 0，否则为目标状态的得分。我知道 MDP 的通用算法不是很有效，但是某些类型的 MDP 有有效的解决方案。这个问题是否适合这些特定类别之一？

2) 具有负边权的有向无环图中的随机最长路径问题。

我需要在最小生成树中找到从所有节点到离它最远的节点的距离。到目前为止我已经这样做了，但我不知道如何找到距节点的最长距离。

如果我有一个节点为 1 2 3 4 的生成树，我需要在生成树中找到距 1 2 3 4 的最长距离（最长距离可以包含许多边，而不仅仅是一条边）。

我有一个非常大的 DAG 字符串（~200k）。我想找到该图中存在的最长路径。下面的代码是我设置图表的方式（来自字符串列表new_list）。

我尝试了检查从每个节点到每个其他节点的路径距离的幼稚方法......这显然是不切实际的并且不会终止。

我也试图longest_path()从这个线程重新编写代码，但无济于事。

我已经阅读了很多关于执行图形的拓扑排序和排序的知识，但是在实现这一点时遇到了麻烦。Networkx 提供了一个功能topological_sort(g)，以便为我完成工作。但是，既然我有一个 topo_sorted 图，我该如何从这里开始呢？

我有一个问答流程，如下所示：

基本思想是，根据为问题选择的答案，接下来会提出不同的问题。

我目前使用以下 JavaScript 对象表示此问答流程：

为了向用户显示进度条，我希望能够通过问题流计算最长和最短路径。

我最初的想法是编写一个如下所示的递归函数来遍历流程中的每条可能路径：

上面的函数确实允许我点击流中的每个节点，但我不确定如何计算流中的最长和最短路径。

任何帮助/建议/代码将不胜感激。
非常感谢。

我目前正在研究一个问题，我想尝试找到一个执行以下操作的算法：给定一个方形网格图 G 和起始节点 S 和一个结束节点 E，其中 E 和 S 在 G 中，找到从 S 到的路径 P具有最大值的 E 和 |P| <= k。如果它变得更容易，则可以使 G 成为 DAG。

网格单元为 0 或 1。

举个例子：

k = 5 的解决方案（据我所见）

S 和 E 是任意的，所以不能假设只是向下和向右移动，但我可以将图转换为 DAG，但我假设会损失一些最优性。

边值是一个成本，G 是一个网格图，其中每个节点都连接到它的四个邻居。

首先，这个问题在文献中是否已经知道？我没有找到任何关于它的信息。是在 NP 中还是有人对快速算法有想法？我问了我选择的搜索引擎，有人在StackOverflow上问了一些可能与之相关的问题，但他们的问题描述与 100% 不匹配，因为他们的目标是最后一行，而我的目标是一个不同的节点。

我知道对于无向图，这个问题是 NP 完全的，因此我们应该使用蛮力来检查所有可能的路径。我们怎么能做到这一点？请提出一个伪代码并告诉我该算法的复杂性。

如果有优化，那就太棒了！