问题标签 [longest-path]

我已经解决了这里发布的大多数问题，除了最长的路径之一。我已经阅读了关于最长路径的 Wikipedia 文章，如果图表是非循环的，这似乎很容易出现问题，而我的不是。

那我该如何解决这个问题呢？蛮力，通过检查所有可能的路径？我什至如何开始这样做？

我知道它会在大约 18000 的图表上花费很多。但无论如何我只想开发它，因为它是项目所必需的，我将对其进行测试并以较小比例的图表展示给讲师，其中执行时间仅为一两秒。

至少我完成了所有需要的任务，并且我有一个运行的概念证明它可以工作，但是在循环图上没有更好的方法。但我不知道从哪里开始检查所有这些路径......

我需要编写一个 Lisp 函数来查找两个节点之间的最长路径，而无需重新访问任何节点。但是，如果起始节点和结束节点相同，则可以重新访问该节点。该函数需要既是递归的又是深度优先搜索的。

我一直试图解决这个问题几个小时，但无法提出解决方案。我知道该功能的大致轮廓，但无法正确编程。在一些代码中，主要是伪代码：

网络看起来像 '((ab) (bc)) ，其中第一项是节点，其他一切都是它的邻居（例如节点 a 有邻居 b，节点 b 有邻居 c）。

是的，这是用于家庭作业的，所以如果您不愿意发布解决方案或其中的任何部分，请不要发布。我是 Lisp 的新手，想要一些技巧/帮助来获得一个体面的开始。

谢谢

编辑：嗯，我能得到的最多的是：

它会产生正确的解决方案，除非开始节点和结束节点相同。即使它们相同，我也不知道如何执行搜索。

在具有非负加权边的 DAG G 中，如何找到 G 中两个顶点之间的最大权重路径？

感谢你们！

尝试在循环图中找到最长路径时存在哪些优化？

已知循环图中的最长路径是 NP 完全的。哪些优化或启发式方法可以使找到最长路径比对整个图进行 DFS 更快？有没有概率方法？

我有一张具有特定品质的图表，但我正在寻找一般情况下的答案。链接到论文会很棒。这是部分答案：

1. 确认它是循环的。使用动态规划很容易计算出无环图中的最长路径。

2. 找出图形是否是平面的（哪种算法最好？）。如果是，您可能会查看它是块图、托勒密图还是仙人掌图，然后应用本文中找到的方法。

3. 找出使用Donald B Johnson 算法（Java 实现）有多少个简单循环。您可以通过在一个简单的循环中删除一条边，将任何循环图变为非循环图。然后，您可以运行在Wikipedia 页面上找到的动态编程解决方案。为了完整起见，您必须为每个周期执行 N 次，其中 N 是周期的长度。因此，对于整个图形，您必须运行 DP 解决方案的次数等于所有循环长度的乘积。

4. 如果必须对整个图进行 DFS，可以通过提前计算每个节点的“可达性”来修剪一些路径。这种可达性，主要适用于有向图，是每个节点在不重复的情况下可以到达的节点数。这是从该节点可能的最长路径的最大值。有了这些信息，如果您当前的路径加上子节点的可达性小于您已经找到的最长路径，那么采用该分支是没有意义的，因为您不可能找到更长的路径。

我编写了一个代码段来确定图中的最长路径。以下是代码。但是由于中间的递归方法，我不知道如何获得其中的计算复杂度。由于找到最长的路径是一个 NP 完全问题，我认为它类似于O(n!)or O(2^n)，但我如何才能真正确定它呢？

我知道在 NP-HARD 中存在以下问题：给定一个简单的图 G=(V,E)，V 中有两个顶点 v，v'，一个整数 B，以及一个非负长度函数 len：E-> Z+ ，是否有一条从 v 到 v' 长度小于 B的简单路径？

我的问题是：在与以前相同的条件下，如果我们有兴趣在 G 中找到从顶点 v 到 v' 的最长但不一定简单的路径，那么问题仍然存在于 NP-HARD 中吗？

注意：我试图减少汉密尔顿路径，但我仍然无法证明 NP 是否存在问题，可简化为我提到的这个问题。我也查过Garey & Johnson，但我什么也没找到。

我想要一点提示来证明这个问题是否是 NP-HARD。提前致谢！

我想知道是否有一种算法可以在有向加权图中找到最长的循环路径（我认为这是找到最大哈密顿子图的问题）。

我需要从一个顶点开始并返回到同一个顶点，遍历最可能的节点。

谢谢

我只是想确保这会奏效。你能找到使用 Dijkstra 算法的最佳路径吗？您是否必须先将距离初始化为-1，然后更改relax 子例程以检查它是否更大？

这是一个不会有任何负权重的问题。

这实际上是问题所在：

假设给定一个电话网络图，它是一个图 G，其顶点代表交换机中心，其边代表两个中心之间的通信线路。边缘由其最低带宽边缘的带宽标记。给出一个算法，给定一个图表和两个开关中心 a 和 b，将输出 a 和 b 之间路径的最大带宽。

这行得通吗？

编辑：

我确实找到了这个：

提示：基本子程序与 Dijkstra 中的 Relax 子程序非常相似。假设我们有一条边 (u, v)。如果 min{d[u],w(u, v)} > d[v] 那么我们应该将 d[v] 更新为 min{d[u],w(u, v)} （因为从 a 到u 然后到 v 的带宽为 min{d[u],w(u, v)}，比我们目前的带宽还要多）。

不完全确定这意味着什么，因为所有距离在初始化时都是无穷大的。所以，我不知道这将如何工作。任何线索？

我试图找出是否可以使用 Dijkstra 算法来找到有向无环路径中的最长路径。我知道由于负成本周期，不可能在一般图表中找到 Dijkstra 的最长路径。但我认为它应该在 DAG 中工作。通过谷歌，我发现了很多相互矛盾的来源。有人说它在 dag 中有效，有人说它不起作用，但我没有找到证据或反例。有人可以指出我的证据或反例吗？

从最近两天开始，我试图找到一些计算图中最长路径的逻辑。我知道我可以很容易地为 DAG 找到它，一般来说它是多项式时间算法。形式上，我想实现启发式计算最长路径，此外，如果给出图中边存在的概率 p，我们如何解决这个问题..帮助...