问题标签 [longest-path]

我目前正在尝试获取来自节点 1 的唯一路径的数量 .. 加权有向无环图的最大长度 N，我已经计算出获得最大长度，但我一直坚持获取给定路径的数量最长长度...

数据输入如下：

.... 作为节点 1-> 节点 2，权重为 34，

我已经研究出如何使用这个来实现最长的路径长度：

首先我制作一个顶点列表

接下来我遍历我的字典，将每个节点设置为最大权重

完成后，最后一个节点的权重将是最大值，所以我可以调用

以获得最大重量。这似乎执行得很快，并且即使在更大的数据集上执行时也可以轻松找到最大长度路径，然后我取我的最大值并将其运行到这个函数中：

一旦我们到达结束节点，我只需检查我们当前的总和是否为最大值，如果是，则将计数加一，如果不通过。

这适用于输入，例如 8 个节点，最长路径为 20，找到 3 条路径，以及输入，例如 100 个节点，最长长度为 149，只有 1 个该长度的唯一路径，但是当我尝试做一个数据集时具有 91 个节点，例如最长路径 1338 和唯一路径数为 32，该函数需要非常长的时间，它可以工作但很慢。

有人可以给我一些提示，说明我的函数出了什么问题，导致它需要很长时间才能从 1..N 中找到路径长度 X 的#？我假设它的运行时间呈指数增长，但我不确定如何修复它

谢谢您的帮助！

编辑：好的，我想太多了，并且以错误的方式解决了这个问题，我重组了我的方法，我的代码现在如下：

我在我的 Vertice 类中添加了一个 pathsTo 变量，它将保存 MAX 长度的唯一路径的数量

我正在创建全景图像，为此我使用了一个以编程方式逐步移动的相机。图像是逐行捕获的。

所以基本上捕获可以看作是某种二维数组：

相机在数字中按顺序移动的位置。

我注意到如果一辆车在相机前移动并跟随相机相同的速度，汽车出现在每张照片上，全景看起来很奇怪。

所以，我有了以下想法：以非顺序移动相机，这样汽车很可能只被捕获一次。然后我考虑如何以相机在每个位置之间移动最多的方式捕获图像。

我找到了一种单行全景图的方法。基本上它从头开始，向右跳一半，向左半回负1，然后重复。

以下是示例：

需要明确的是，这意味着对于 1x6 (0, 2, 4, 1, 3, 5)，相机移动如下：

所以基本上它至少总是跳跃n/2，这看起来是最佳的，因为没有捕获最终成为另一个捕获的邻居，并且捕获之间的距离看起来最大化并且波动很小。

我使用的简化代码类似于：

我试着让它与几行一起工作，几乎到了那里，但后来放弃了。以下是我的想法的示例：

如果您查看数字，我们会发现左侧通常只是偶数，右侧是奇数，但以模数方式移动。这种奇数的移动很难进行算法化，因为逻辑会根据行/列是偶数/奇数而略有变化。

目前我忽略了这些行，只是对每一行重新应用相同的算法。这意味着 2x5 是这样完成的：

所以，这是我的问题：

• 多行实现我想要的最佳算法是什么？我阅读了有关https://en.wikipedia.org/wiki/Longest_path_problem的信息，我认为可以构建一个图形，其中网格的所有节点之间都存在路径，并且每条边的权重将是之间的距离节点。这听起来很复杂，而且不容易编码。
• 申请多行的最简单/最实用的算法是什么？我对“足够好”的解决方案没意见（网格的尺寸应该保持在 1x3 到 3x9 之间）。我不想要基于随机性的解决方案，因为我希望每次捕获全景图时捕获始终以相同的顺序发生。

编辑：附加信息：汽车通常移动缓慢（以连续捕获的速度），因此四处跳动是避免重复的好方法。如果汽车以相机的速度移动（发生了这种情况），那么在 2-3 个图块中看到汽车也比在 7 个图块中看到汽车更好。全景图通常在 180° 左右，但应支持 360°。每次图像捕获之间有大约 3 秒的暂停。全景图主要是拍摄巨型建筑工地（建筑物）的建筑，但有时有汽车或人在建筑物前行走。我们不关心移动部件，目标是捕捉建筑物并最大限度地减少人/汽车对全景的照片轰炸。

我正在尝试获取列表中最长的子列表。我需要一个递归搜索列表列表并确定哪个列表长度最长的规则。

例如：
输入：[[1],[1,2],[],[1,2,3,4],[5,6]]
输出：[1,2,3,4]

这是我到目前为止所拥有的：

我想这样max()工作：

当我运行跟踪时，这是输出：

我认为问题在于我没有处理空集“ []”的出现。但是，我尝试了几种不同的方法，但无法获得我想要的输出。

我想在有向无环图（DAG）中找到 K 条最长的路径。我已经阅读了几篇关于它的文章，但我找不到任何实现它的实际代码。有人可以帮助我使用python或伪代码吗？

这是一个有趣的算法解释： https ://www.ncbi.nlm.nih.gov/pmc/articles/PMC3009499/

我只是想知道：您可以反转图中的所有权重，然后进行 Dijkstra 吗？当我们最小化权重的倒数时，得到的路径会最大化，对吧？因此，通过这种方式，我们可以使用 Dijkstra 获得图中的最长路径！这似乎太容易了，我弄错了吗？请赐教。

我想从图中获得最长的路径，其中每个对象可能相互连接。甚至每个对象都可以连接到自身。我想计算从 id 为 1 的元素到其他每个元素的最长路径。

由于所有连接都是可能的，我必须注意循环，因为代码可能会陷入无限循环。

我创建了以下对象

并从一些随机数据开始

因此，我创建了一个算法，该算法应该返回这些连接可能的最长路径。

不知何故，我没有陷入无限循环，也没有得到任何错误，但算法没有返回正确的路径。

当前元素的起始连接器没有以当前目标 id 结尾的正确路径。

我想构建 GKGraph 并找到两点之间的最长路径。我看到 GKGraph 有一种方法可以找到最短路径，但最长我什么也没找到。你能建议我如何使用 GameplayKit 找到两点之间的最长路径吗？

我知道之前有人问过类似的问题，并且网上有大量的资源，但我有一个稍微不同的问题。我了解从 HAM 路径到最长路径的减少。它依赖于两者都需要使用 n-1 条边。但是，如果在最长路径中给出的图具有负边权重怎么办。那么最长的路径可能有 n-2 条边，但 HAM 仍然有 n-1 条边。

这个问题有不同的减少方式吗？我错过了什么吗？

我无法弄清楚如何更新 networkx dag_find_longest_path() 算法以返回“N”表示关系，而不是返回找到的第一个最大边，或者返回与最大权重相关的所有边的列表。

我首先从 pandas 数据帧创建了一个 DAG，其中包含如下子集的边缘列表：

然后我使用下面的代码对图进行拓扑排序，然后根据边的权重找到最长的路径：

这很好用，除非当最大加权边缘存在联系时，它会返回找到的第一个最大边缘，而我希望它只返回一个表示“Null”的“N”。所以目前，输出是：

但我真正需要的是：

寻找最长路径的算法是：

的可复制粘贴定义G。

我在网上看到找到最长路径问题是NP-Complete问题。

出于某种原因，我的老师告诉我这不是一个 NP 完全问题。因此，现在我正在寻找一个示例，该示例显示获得最长路径所需的计算量大于多项式时间。

目前，我只看到了具有多项式复杂时间的示例。

任何人都可以给我证明这个问题是NP完全的吗？