问题标签 [traveling-salesman]

我正在尝试实现这一点，但我找不到一篇好的论文或描述如何做到这一点，你们能指出我正确的方向吗？我确实在 C# 中有一个实现，但我不知道将代码转换为 Java。

根据评论，我添加了一些我无法转换为 Java 的 C# 代码：

为学校做一个项目，我们实现最近邻启发式（我已经做过），以及我们进行详尽搜索的旅行销售员问题（然后我们分析算法，它们的时间复杂度等）。我们的老师说要四处寻找用于详尽搜索部分的代码（或修改），而不是像在最近邻部分中那样对整个事物进行编程。我环顾四周，只找到了与我们被指示如何执行程序无关的内容。与使用整数的典型问题相反，我们使用点 (x, y)。我的目标是计算最短排列并能够知道该排列是什么。所以我想有一个数组数组（其中包含排列）。

如果有人可以帮助我进行详尽的搜索，那就太好了。

这是我的代码的一些摘录（成员变量、计算两点之间距离的函数以及所有点的存储位置）：

任何帮助是极大的赞赏。

在尝试解决一个相当大的 TSP 问题时，我在计算 Mathprog 中的链接节点时遇到了麻烦：假设我有

距离函数 d(c1,c2)

和其他一些条件

进行所有可能的削减以解决电路需要电源组和其他一些东西，但是在 20 多个节点上，问题太贪婪了，我无法找到解决方案。

所以我想我会限制求解器连接所有 a[i,j] 强加

这与

这可能不会导致解决方案，但无法实现如此简单的事情令人非常沮丧......有没有办法在 mathprog (gmpl) 中实现这样的伪代码？

我正在从事一项小型学术任务，以使用遗传算法 (GA) 解决旅行商问题 (TSP)。我正在遵循一个非常简单的经典表示，将城市和旅游存储在数组中，例如，10 个城市的旅游可以表示为 9-1-0-4-3-8-6-5-2-7 等等。对 GA 有相当基本的了解，我对您将遵循哪种方法将不同类型的突变应用于 TSP 有点困惑。假设我们的路线表示为路线，突变率用变量 m_rate 表示。

[1] 简单插入突变

假设我们有：1-2-3-4-5-6-7-8-9。然后我们选择一个随机城市，比如索引 5，然后选择一个随机插入索引，比如 2，那么突变的染色体是：1-2-6-3-4-5-7-8-9。

现在这是我正在做的应用突变：

换句话说，我正在遍历路线中的每个城市并查看突变条件是否成立 (m_rate>Math.random())，如果是，那么我会在该索引处停下来，然后随机选择一个插入点，而不使用变异概率变量。只要没有遇到数组的末尾，我就会继续将相同的东西应用于其他所有剩余的城市或索引。这是正确的方法吗？应用第一个突变后，我应该停止还是跳出循环？突变概率是否应该以某种方式参与选择插入点？虽然这对我来说似乎没有多大意义。如果有可能不止一个城市在染色体或路线上发生突变，染色体有没有可能发生突变？换句话说，如果我最终进行第二次或第三次突变将染色体反转为其初始形式（突变之前）会发生什么？

[2] 相互交换突变。

在染色体中选择一个随机城市，然后选择第二个随机城市并交换两者。例如，在路线 1-5-2-8-0-9-3-7-4-6 中。如果我们最终选择索引 2 和索引 7，那么突变的染色体是：1-5-7-8-0-9-3-2-4-6。

我正在遵循与上述插入突变类似的方法，遍历路线中的每个城市并检查概率条件，然后直接选择一个随机城市进行交换，而不应用任何类型的突变率。上面同样的问题在这里适用..

[3] 反转突变。

这是最棘手的一个。给定一个像这样的染色体：1-2-3-4-5-6-7-8-9，我们选择一个像索引 2 到索引 5 的突变切割，然后反转那个子路径 ==> 1-2-6-5- 4-3-7-8-9。

但是你如何应用这个？你是不是循环遍历路线，然后根据突变率选择一个城市，然后直接选择另一个指标来确定子路线的长度？突变一次并退出？在这种实现中，如果我们的突变切割最终是 0-9 或 0-(length-1) ，整个染色体或路线是否可以突变以反转整个事物？在这种情况下，突变率的真正价值是什么？我有点迷失在这里...

我提前道歉，因为它太长了。但我会很感激任何关于这些问题的评论，或者如果有人可以指导我到任何详细讨论这些事情的资源。我看过很多研究论文，但没有多少人接触过这种细节和细节。

谢谢你。

我正在寻找问题的名称和解决方案的算法。

我有一个连接节点图（A..Z），其中每个节点都连接到其他每个节点。我想绘制通过这些节点访问给定节点子集（A，D，K，W）的最短路径。路径可能包括不在子集中的节点，即 A->C->W->D->K 是可以接受的。在节点之间旅行的成本是非负的，但不一定是线性的。因此，从 A->B->C 的路径段可能比 A->C“更短”

我认为这是旅行销售员的变体。

我正在尝试实施本地搜索（使用 2-opt）来解决旅行商问题。但是，我无法正确地重新创建一个完整的电路（节点之旅）。我认为我的算法可能有缺陷。这是我对 2-opt 的实现：

a->b->...d->c->...a

切换到

a->d->...b->c->...a

我的一般过程看起来像标准交换：将 b 存储为临时存储 c 作为 temp2 a->d b->c

我的代码如下所示：

现在我明白这段代码并不完美。例如，如果重新洗牌的两个节点没有创建完整的电路，则代码只会在再次尝试之前更改第二个节点。但我的问题是为什么我一开始就无法完成完整的巡回演出。

谢谢你的帮助！

我正在尝试为 PACMAN 问题找到一个解决方案，即找到一条可以吃掉大迷宫中所有点的短路径（不是最短的，而是一条好的路径）。我见过很多人在谈论 TSP、Dijsktra、BFS、A*。我不认为这是一个 TSP，因为我不必回到我开始的地方，如果我愿意，我可以重复节点。而且我认为 Dijsktra、BFS 和 A* 不会有帮助，因为我不是在寻找最短路径，即使是这样，它也不会在合理的时间内给出答案。

任何人都可以给我提示吗？这是什么问题？这是一种TSP吗？什么样的算法可以有效地解决这个问题？我将不胜感激有关实施的任何提示。

我在SO的答案之一中阅读了以下内容：

旅行商问题，正如通常所提出的，是找到连接所有城市的最便宜的路线。这不是决策问题，我们无法直接验证任何提议的解决方案。我们可以将其重述为一个决策问题：给定成本 C，有没有比 C 更便宜的路线？这个问题是 NP 完全的，只需一点点工作，我们就可以像修改后的 NP 完全形式一样简单地求解原始 TSP。因此，TSP 是 NP 难的，因为它至少与 NP 完全问题一样难。

我知道 TSP 是 NP-Complete 但问题是如何 NP-Hard ？我读到NP中但不在P中的问题是NP-Hard。我无法将这件事与 TSP 联系起来。请解释一下。

我正在尝试解决这个问题http://coj.uci.cu/24h/problem.xhtml?abb=1368。

经过大量研究并花费大量时间，我能够为 TSP 实现分支定界算法，该算法得到一条通过所有点并返回开始的路径。

我在想从那条路径中删除最长的边我会得到答案，但是当我完成我的算法时，我发现这并非在所有情况下都是正确的，阅读这个问题：Minimal Distance Hamiltonian Path Javascript

我找到了一些答案，说添加一个与其他点的距离为零的虚拟点，然后删除它可以解决问题，但我不知道具体情况。我已经添加了那个虚拟点，现在不是得到 26.01，而是 16.23 作为答案。我还没有删除虚拟点，因为我不明白“添加虚拟点的全部意义”。

你能指导我解决这个问题吗？还是采用另一种方法而不是 TSP 更好？

我从多个来源以及我对它在 2^N 时间内运行的算法的理解中阅读。我的问题是什么导致 TSP 达到这个运行时间？我似乎找不到伪代码，所以我可以检查它。