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

Question

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

我最近了解到A*算法可以应用于旅行商问题。Bot 我们如何在这里定义起点和目标，以及我们如何将权重应用于节点（什么是启发式）？

有人可以向我解释如何在这里应用 A* 吗？

Answer 1

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

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

要实现这一点，您的起始节点将是 (1,{})，而您的结束节点将是 (1,{1..n})。您将模仿原始图的边权重。至于关于启发式的建议，你靠自己..

Answer 2

A* 可以在这里应用，尽管它可能不是最好的算法。

您将不得不远离城市和它们之间的道路图。相反，定义一个有向图，其中部分路线是节点，两个节点x和y是连接的，如果y可以通过在原始城市图中添加单个“步骤”从x构造而成。起始节点是一个空路径。目标节点是访问所有城市的路径。（此路径的最优性由启发式和 A* 算法本身的属性保证。）

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

路径成本是行进的总距离。启发式必须是总最小行程长度的一些可接受的估计（通常是低估）。

这种估计的一个很好的候选可能是 TSP 的快速近似（一个松弛问题的解决方案）。您将在尚未覆盖的城市集上为每个节点（部分路线）运行近似算法。这为算法提供了推销员仍然必须走的距离的必要上限。

Answer 3

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

是的，理论上可以将 TSP 问题转换为更大的图并在其上使用A* 搜索。但遗憾的是它没有用，因为它不会扩展（参见 spin_plate 的评论）。即使是小型实例也可能需要数年才能在现代硬件上以这种方式解决。

TSP 是NP-complete，寻路不是。

如果是螺丝（NP 完全问题），请使用螺丝刀（metaheurstics，...）。

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

Answer 4

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

TSP 问题指出，您希望在每个目的地仅访问一次时最小化旅行距离。A* 算法需要一个启发式方法来指导它的最佳解决方案是一条直线的方式（您必须小心 A* 启发式方法，不要高估到目标的距离）。这不适用于 TSP 问题。

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