A*算法如何应用于旅行商问题？

Question

可能重复：
使用A*算法解决旅行商问题

我最近了解到A*算法可以应用于旅行商问题。但是我们如何定义起点和终点，如何为节点赋权值（什么是启发式）？

有人能向我解释一下A*如何在这里应用吗？

- gruszczy

---

我并不打算开发任何东西，只是想深入了解A*算法如何应用于实际问题。 - gruszczy

你确定它是A算法还是广义自适应A算法？我想这两者都可以使用类似于larsmans答案中描述的方法进行应用。 (参见 http://www.aamas-conference.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0026.pdf) - HasaniH

@Spaceghost - 嗯？“在这篇论文中，我们展示了如何做到这一点，从而得到了广义自适应A（GAA），它可以在动作成本会随着时间的增加或减少的状态空间中找到最短路径。”- 这与这个问题有什么关系呢？ - dfb

顺便说一下，有人在重复的问题中找到了解决方案：https://dev59.com/LW855IYBdhLWcg3wPB36#10247947 - Lenar Hoyt

我非常确定这是一个重复的问题，并且已经被正确标记。如果能够发布原始链接，那就太好了，因为这是我在谷歌搜索中得到的第一个结果... - ntg

Answer 1

A*是Dijsktra的一个衍生算法，我认为它不能以这种方式使用。首先，TSP通常从任何节点开始。更重要的是，这些算法寻求找到两点之间的最短路径，而不考虑访问的节点数。事实上，它们依赖于这样一个事实：从S到T经过某个节点A的最短路径，如果S到A的路径成本相同，则S到A的路径是无关紧要的。

我唯一看到这个算法能够发挥作用的方法是生成一个表示已访问节点的新图。例如，在您的优先队列中，您会放置已访问节点和当前节点的集合。这将导致可能检查$n2^n$个节点（这恰好是TSP动态规划解决方案的运行时间http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM）。到目前为止，这不是很好，但通过使用A*代替Dijsktra，您可能能够找到在合理时间内运行的启发式算法。

要实现此操作，您的起始节点将是（1，{}），结束节点将是（1，{1..n}）。您将模拟原始图的边权重。至于启发式建议，您可以自己想办法...

- dfb

---

+1，除了节点应该是路径而不是城市集合。请参考我的答案以获取启发式提示。 - Fred Foo

@larsmans - 我不100%确定，但我不同意。 就像在常规的最短路径中一样，我们到达节点X和{节点Y，Z和T}的方式对于路径的其余部分是无关紧要的，无论我们是否访问了YZT或TZY等节点。 然而，我们需要存储最大值来重构路径。 动态编程方法也表明这是正确的，如果我们构建一个算法TSP（node，visited）= min TSP（node2，visited + node）+ cost（node，node2），其中node2不在visited中，并进行记忆化，我们有一个o（2 ^ n）而不是N！的解决方案。 - dfb

是的，我认为你是对的。一个（集合，长度）组合可能就是算法需要的所有内容，这立即为你提供了必要的对称性破缺。 - Fred Foo

一种可能的启发式方法是最小生成树（MST）加上连接MST和已固定段的最短边的长度。 - Pedro Dusso

你并不需要为每一步创建一个新的图表。只需知道每个节点的状态（已访问/未访问）以及你的上一步操作是什么，这意味着对于每个状态，你至少需要O(n)的状态（仍然不可忽略...）。 - ntg

Answer 2

虽然可能不是最佳算法，但可以使用A*算法。

你需要离开城市和它们之间的道路的图表。相反，定义一个有向图，其中部分路径是节点，当且仅当通过在原始城市图中添加单个“步骤”可以从x构建y时，两个节点x和y相连。起始节点是空路径。目标节点是经过所有城市的路径。（启发式和A*算法本身的属性保证了这条路径的最优性。）

[编辑：起初我认为路径应该是一个有序的城市列表，但现在我相信@spinning_plate的建议，用一对（长度，城市集合）表示路径就足够了。]

路径成本是旅行的总距离。启发式估计必须是总体最小旅行长度的某个可接受估计值（通常是低估）。这样的估计值的一个很好的候选者可能是TSP的快速近似（放松问题的解决方案）。您将为每个节点（部分路径）在尚未覆盖的城市集上运行近似算法。这为算法提供了销售员仍需前往的距离的必要上限。

- Fred Foo

---

但这与 Dijkstra 算法有何不同呢？没有启发式函数，A* 算法与 Dijkstra 算法没有区别。 - John Leidegren

我发表了一个可能的启发式算法，或者至少是它的草图。使用近似值来引导A*算法朝着正确的方向前进是一种相当普遍的做法。 - Fred Foo

我可能误解了，但这种情况下的内存要求不是非常大吗？ - John Leidegren

@larsmans - 你刚才不是把可接受启发式的定义搞错了吗？根据维基百科，“如果启发式从不高估到达目标的成本，则它是可接受的”。 - John Leidegren

一种可接受的启发式方法是从已添加到集合中的最后一个城市到尚未访问的城市的最小距离。另一个（可以事先轻松计算）是从最后添加的城市到任何其他城市的最小距离。 - Ted Hopp

Answer 3

如果我有一把锤子（A*搜索），每个问题（TSP）都是一个钉子（路径规划）。

是的，在理论上，可以将TSP问题转换为一个更大的图，并在其上使用A*搜索。但遗憾的是，由于不会扩展，它是无用的（请参见spinning_plate的评论）。即使是小实例也可能需要多年才能在现代硬件上解决。

TSP是NP完全问题，而路径规划则不是。

如果是螺丝钉（NP完全问题），请使用螺丝刀（元启发式算法，...）。

使用诸如元启发式算法（禁忌搜索，遗传算法，模拟退火，...）等算法。有关软件示例，请参见Drools Planner，openTS，jgap，cpsolver等。

- Geoffrey De Smet

Answer 4

A*算法是Dijkstra算法的扩展，它考虑了遍历有向图的最优解。我不确定这是否适用于TSP问题。

TSP问题指的是您希望在恰好访问每个目的地一次的情况下最小化旅行距离。A*算法需要启发式来引导其前进，其中已知最优解为直线（您必须小心A*启发式，以免高估到达目标的距离）。这不适用于TSP问题。

此问题还包含有关A*算法和TSP问题的信息。

- John Leidegren