问题标签 [longest-path]

我正在寻找一种算法，通过从中删除一条边来拆分具有 N 个节点（每个节点的最大度数为 3）的树，以便结果的两棵树尽可能接近 N/2 . 如何找到“最居中”的边缘？

树作为算法前一阶段的输入，并作为图输入 - 所以它不平衡，也不清楚哪个节点是根。

我的想法是在树中找到最长的路径，然后选择最长路径中间的边。它有效吗？

最理想的是，我正在寻找一种解决方案，可以确保两棵树的节点数都不超过 2N / 3 个。

感谢您的回答。

这是[来自 CLRS] 的问题：

将优化问题 LONGEST-PATH-LENGTH 定义为将无向图的每个实例和两个顶点与两个顶点之间最长简单路径中的边数相关联的关系。定义决策问题LONGEST-PATH = {：G=(V,E)是一个无向图，u,v包含在V中，k >= 0是一个整数，G中存在一条从u到v的简单路径由至少有 k 个边}。证明当且仅当 LONGEST-PATH 包含在 P 中时，优化问题 LONGEST-PATH-LENGTH 可以在多项式时间内求解。

我的解决方案：给定一个算法 A，它可以在多时间内求解 G(u,v)，所以我们在 G(u,v) 上运行 A，如果它返回 'YES' 和 k' 使得 k' 是最长的路径G(u,v)，现在我们要做的就是比较 if

如果然后解决最长路径长度。如果我们收到“NO”或 k>=k'，则不存在解决方案。

所以 polytime 运行 A + 常数进行比较，然后找到最长的路径长度，它需要 poly time。这也是唯一可能的，因为 G(u,v) 在 Polytime (in P) 中运行，因此 G(u,v,k) 也在 polytime (in P) 中运行，因此由于最长路径可以简化为最长路径-长度，那么最长路径长度在 P 中。

我们可以用相反的方式解决它，我们所做的是，运行 G(u,v,k') for k'=0 到 n，每次检查是否 k==k'，所以我们解决了它。运行时分析：n*polytime+ n*(constant comparsion)=polytime

谁能告诉我我的回答是否合理？如果不是，请告诉我哪里出错了

你也能给我一些关于如何学习算法的建议，以及我应该采取什么方法来解决算法问题（或图形问题）

谢谢，麻烦您了

我有一个国家列表，我想拥有最长的国家路径，其中每个选择的国家必须以结束前一个元素的相同字母开头

我试过这种方式，但它不起作用

有什么建议吗？

我想知道如何从节点 0（最小节点）开始获得 DAG 中的最长路径

我搜索了wiki并得到了以下算法：

但是我不知道怎么实现，当然下面我写的代码是行不通的：（topo是拓扑排序的节点）

我应该怎么做？谢谢！

此外，你能给我一个算法来计算从 0 到 n-1 的不同路径的数量吗？

在无环图中，我试图找出两个给定节点之间是否存在长度为 L 的路径。我的问题是，在这种情况下使用的最好和最简单的算法是什么。

请注意，该图最多有 50 个节点和 100 条边。

我尝试使用 DFS 查找所有路径，然后检查两个节点之间是否存在该路径，但我从在线法官那里得到了“超出时间限制”的答案。

我也使用了统一成本搜索算法，但我也得到了否定的回应。

我需要一种更有效的方法来解决此类问题。谢谢你。

我目前正在开发一个计算机视觉程序，该程序需要我确定图像中颜色斑点的“方向”。颜色斑点通常遵循椭圆形状，因此可用于随时间跟踪方向（相对于最初定义/确定的方向）。

我认为计算方向变化的方法描述如下：

1. 将可能的方向（360 度）量化为 N 个方向（可能为 8 个，以 45 度角为增量）。
2. 给定一个表示颜色 blob 的初始状态 (t0) 的存储矩阵，还获取一个表示 blob 当前状态 (tn) 的矩阵。
3. 遍历这 N 个方向并搜索该给定方向的颜色值的最长延伸。（例如，如果椭圆旋转 45 度，0 为垂直，则最长的长度应归因于 45 度标记/或 225 度）。

这个概念本身并不复杂，但我遇到了以下问题：

• 计算图像中任意角度的值的最长拉伸。这对于 0、45、90 等角度很简单，但对于中间角度则更困难。“量化”角度对我来说并不像听起来那么容易。

请不要担心区分角度（例如 0 和 90）的潜在问题。惯性可用于确定颜色斑点的最可能方向（换句话说，基于过去的方向状态）。

我主要关心的是确定矩阵中的“最长延伸”。

谢谢您的帮助！

我是 OGDF 库的新手，需要在无环有向图中找到最长的路径（我想使用 OGDF 内置函数）。我知道，可以使用边缘权重为负的最短路径算法找到最长路径，但也找不到合适的函数。OGDF 是否具有执行此操作的特定功能？如果是，我该如何使用它？

我正在开发一个程序来生成公司的组织结构图。我一直在阅读关于对顶点进行分层的最长路径算法，有一件事一直困扰着我。我所做的阅读表明，该图应该从下往上分层，首先将没有子节点的节点放在底层，然后向上处理。但是，我还读到最长路径算法会导致底部非常宽的图。

我在想我会尝试从上到下构建图表，从没有父节点的节点开始，然后一路向下。也许这很常见，我只是没有看到它使用过，但我担心有一些我没有看到的原因导致这种方法不切实际。有什么我想念的吗？

我正在尝试将这个问题概念化，然后为它编写 Java 代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望得到你们的一些反馈。谢谢！

我的想法：对于每个叶节点找到从根节点到它的最长路径对于所有路径找到最大路径长度

然而，这不就是简单的蛮力吗？有没有更优雅的解决方案？

我听说过使用负权重的 Djikstra 算法，但在某些地方它说这仅适用于特定情况？我也看到了 Bellman Ford 算法的建议，但这不是用来找到最短路径的吗？

谢谢！！

最近遇到一个编程问题。

给定一棵树，可以是非二元的，可以是单链（或线性），具有 N 个节点。

输入将是一组 K 节点，表示为 a1,a2....ak。我想找到从这些 K 节点之一开始并在其中一个 K 节点（不同于起始节点）处结束的最长简单路径。取决于N或K的对数算法应该满足运行时间要求（例如：KlogK，KlogN）如果需要的话应该在我想要的时间限制内。

谢谢