问题标签 [longest-path]

我正在尝试用递归解决这个问题。
问题是：对于正整数的二维数组，我如何返回最长路径（步数），以便最长路径的每个单元格中的值来自整数的降序序列，并且每个单元格和单元格之间的差异是给定数字（num）。
假设n是单元格的值，因此 ( n - num) 是正数（非零）。
我不能使用任何循环（for、while、...等）

方法：

例如：

如果我们搜索差数= 1的最长路径

1-在单元格矩阵[0][3]中，路径长为3，该路径中的值是33 -> 32 -> 31以矩阵[1][4]结尾

2-在单元矩阵 [1][0 ] 中，路径 long 为 6，路径 60 -> 59 -> 58 -> 57 -> 56 -> 55 中的值以矩阵 [2][4]结尾

3-在单元格矩阵[1][0]中，路径长为2，此路径中的值为60 -> 59以矩阵[2][0]结尾

所以该方法必须返回最长的路径，它的 6

如果我们搜索差数= 2的最长路径

1-在单元格矩阵[2][1]中，路径长为3，此路径中的值是17 -> 15 -> 13 以矩阵[3][2]结尾

该方法必须返回其 3 的最长路径。

我的非工作代码：

在编写代码时，我遇到了很多运行问题

我做错了什么？提前致谢

我有一个问题，我需要找到最长的路径。给定一个未加权的无向图。从给定的顶点开始，我需要访问尽可能多的顶点并在同一个顶点中完成，而不是访问每个顶点一次以上。

我发现的大多数算法都是针对特殊情况（非循环、有向等）的。一个想法可以是为每个顶点子集找到哈密顿循环（可以通过回溯生成子集）。但我想一定有更好的算法。

我正在使用此代码https://www.geeksforgeeks.org/longest-path-undirected-tree/来查找无向图中的最长路径。该代码使用两次 BFS 搜索来找到最长的路径，然后输出路径的开始和结束以及长度。如何将路径保存在列表中并打印出来？我将前辈保存在一个数组int predecessors[n]中，但这当然没有给出路径。我知道我应该以某种方式修改它，pred[V]以便它存储前辈列表，但我不知道如何实现它。任何帮助表示赞赏。

// 方法返回最远节点及其到节点 u 的距离

// 方法打印给定树的最长路径

// 测试上述方法的驱动代码

// 结果：

我需要找到到给定目标的最长路径。数据是一个 id 字典，其值是指向该 id 的所有 id 的列表。另外值得注意的是，每个 ID 只能指向另一个 ID。

我尝试编写一个递归函数，它将遍历每个可能的路径，并将每个唯一路径选项存储到另一个列表中，从中我将找到最长的路径。

和最长的函数

做的时候

我得到主要的路径堆叠在彼此之上。我将如何修复代码以使路径不会堆叠。我希望主要看起来像

编辑：

更改行main, vec, id = create(main,[],'D4')以main, vec, id = create([],[],'D4')澄清这main是一个列表列表。

我找到了一段伪代码，它解释了最长路径问题的模拟退火，但有一些我不明白的细节。

目前我已经实现了一个表示图的结构，以及在图中生成随机图和随机路径的方法——两者都是统一的。

这是模拟退火的伪代码：

我觉得不够清楚无法理解的细节是：

随机邻居（P，G）

阿尔法（温度）

itermax = Beta(itermax)

这些方法应该做什么？

我需要找到点值变大的最长路径。首先我找到最长路径的步数，然后我使用 DFS 搜索地图中的所有点，看看他们是否提供具有该步数的解决方案。

当我运行地图以发现步数时，我知道至少 O(L*C) 是 L 和 C 是地图的大小。但我找不到下一步该做什么。

我正在学习C语言。我想在从 A 到 B 的图中找到最长的非循环路径。

例如，我有一个这样的图表：

现在我想编写一个函数，它可以找到从节点 A 到节点 B 的最长非循环路径。

input: longestPath(node A, node B) output: the longest length is x, node_a -> ... -> node_b

例如：

input: longestPath(0, 6) output: the longest length is 6, 0 -> 1 -> 2 -> 3 -> 4 -> 6 （输出答案可能不是唯一的，而是正确答案之一）

但我不知道如何实现一个合适的算法来找到它。

我应该使用 BFS 还是 DFS 来查找所有可能的路径并进行比较？（但似乎很慢）

你能给我一些建议吗？谢谢！

假设有两个列表

和

然后输出应该返回所有具有最长公共路径的子路径。例如：

由于'A'、'C'、'B'是共同的L1和L2；输出应该是：

. 此外，“A”、“D”、“K”在 L1 和 L2 中也常见一次；输出应该是：

我试过了 ：

但它会给出所有公共路径的输出，直到叶子（结束）。

我有一个图表，想找到从源到接收器的最长路径。我的想法是将权重反转为负数并在其上运行 dijkstra，如在 JGraphT 中实现的那样

不幸的是，当我想设置负权重时，出现错误“不允许负权重”。

我正在尝试创建一个函数来在有向图中找到最高分。我确实有一个起始节点，不能两次通过同一个节点。我尝试使用递归来获取值的总和，直到我到达一个末端节点。然后我会将我的函数回调到起始节点并尝试其他选项，直到我遇到另一个选项。等等。

我的问题是，当我返回具有多个路径的节点时，该节点的得分值是它可以采用的所有路径的总和。我只想要一条特定路径的总和。

到目前为止，这是我的代码：

我怎样才能让它最终只用它所走的路径（caminho）返回最好的分数。

对不起，如果我不能让自己足够清楚。随意问任何问题。