使用A*算法解决旅行商问题

Question

我被委托编写实现A*算法（提供启发式）以解决旅行推销员问题的任务。我理解这个算法，它足够简单，但我就是看不到实现它的代码。我的意思是，我明白节点的优先队列按距离+启发式（节点）排序，将最接近的节点添加到路径上。问题是，如果从前一个最近的节点无法到达最接近的节点会发生什么？如何将“图形”作为函数参数传递？我就是看不到算法如何实际运作，即代码方面。

我在发布问题之前多次阅读了维基百科页面。它并没有真正回答这个问题——搜索图形与解决TSP完全不同。例如，可以构造一个图形，其中任何时候最短节点都会导致回溯，因为两条相同长度的路径并不相等，而如果你只是想从A到B，则两条相同长度的路径是相等的。

您可以通过始终选择最接近的节点来派生图形，其中某些节点永远不会到达。

我确实看不出A*算法如何应用于TSP。我的意思是，从A到B找到路线，当然可以。但是TSP呢？我看不出二者之间的联系。

- Puppy

---

A*算法似乎是我在CS课程中记得的一个相当好的总结。Dijkstra算法非常相似（但更简单），因此可能更容易开始。在两种情况下，优先队列都很方便。 - user166390

如果你想从点A到点B，A*算法和Dijkstra算法很有用。但如果你想通过具有特定限制条件的路径从点A到达点A，那就是另外一回事了。 - David Thornley

当我还在大学时（上个千年），我们有一个任务，可以用任何语言实现A*算法。大多数人选择了我们都最熟悉的C++，但我选择了Prolog，因为它似乎更适合这个问题。长话短说，我比大多数人完成得更快，也许你可以直接从Prolog开始，跳过中间阶段。 - Motti

Boost::graph有A*的实现，或者像Boost这样的特定语言代码。 - Alexandre C.

这个被关闭了，因为它是这个的重复。 - ChrisF

Answer 1

我在这里找到了解决方案。

使用最小生成树作为启发式。

设置 初始状态：代理在起始城市并且没有访问过其他任何城市

目标状态：代理已经访问了所有城市并回到了起始城市

后继函数：生成尚未访问的所有城市

边缘成本：节点表示的城市之间的距离，使用该成本计算g(n)。

h(n)：从当前城市到最近未访问城市的距离+预计通过所有未访问城市的距离（这里使用MST启发式）+最近未访问城市到起始城市的距离。请注意，这是一种可接受的启发式函数。   您可以考虑维护已访问城市列表和未访问城市列表以便于计算。

- user972616

---

可以构造出问题图形，其中MST的行为是违反直觉的。假设您有一个包含N个城市的图形需要访问。使用MST可以得到到达目标的剩余距离的下限。然后删除一个城市，留下N-1个城市需要访问。现在，到达目标的剩余距离可能会更大！这个问题在我尝试在我的A *最近邻搜索中使用最小生成树时困扰了我。我的解决方案是减去一个奖励乘以已访问城市数量来平滑函数。 - Paul Chernoch

这个启发式算法甚至不可行。由于在构建最小生成树时删除了一些边，因此MST中两个城市之间的距离可能大于实际图中两个城市之间的距离。 - unlut

Answer 2

混淆的地方在于你试图解决TSP的图形并不是你执行A*搜索的图形。

参见相关：Sudoku solving algorithm C++ 要解决这个问题，您需要：

- 定义您的：

- TSP状态 - TSP初始状态 - TSP目标状态 - TSP状态后继函数 - TSP状态启发式

- 将通用A*求解器应用于此TSP状态图

我可以想到一个快速的例子：

- TSP状态：当前在TSP循环中的节点（城市）列表 - TSP初始状态：包含单个节点（旅行商的家乡）的列表 - TSP目标状态：如果包含城市图中的每个节点，则状态为目标状态 - TSP后继函数：可以将任何不在当前循环中的节点（城市）添加到节点循环的末尾以获得新状态

- 过渡的成本等于您正在添加到循环中的边缘的成本

- TSP状态启发式：由您决定

- Timothy Shields

Answer 3

如果您只是不理解算法及其工作原理，您可以考虑在纸上画出图形，为其分配权重并将其画出。此外，您可能会发现一些动画展示Dijkstra的最短路径，维基百科上有一个很好的动画。Dijkstra和A*之间唯一的区别是加入了启发式，并且当您到达目标节点时停止搜索。至于将其用于解决TSP问题，祝您好运！

- fbl

---

如果暗示使用A*算法解决TSP问题会很困难，那么这是不正确的。我同意上面的评论，从Dijkstra算法开始可能更容易些，但一旦你决定了实现细节，两者都相当简单。 - Mike Linington

我觉得我不明白A*算法如何帮助你解决TSP问题。只允许选择最近的未访问邻居会得到一个有效路径，但不一定是最短的路径。TSP问题（如一直被告知的那样）需要最短的非重复路径。也许我误解了原始问题的目标。 - fbl

Answer 4

抽象地思考一下。暂时忘记A*算法，它只是带有启发式的Dijkstra算法而已。之前，你想从A到B。你的目标是什么？是到达B。目标是以最小代价到达B。在任何给定的时刻，你的当前“状态”是什么？可能只是你在图上的位置。

现在，你想从A开始，然后去B和C。你现在的目标是什么？是经过B和C，保持最小代价。你可以通过更多节点来概括这个问题：D、E、F...或者N个节点。现在，在任何给定的时刻，你的当前“状态”是什么？这很关键：它不仅仅是你在图中的位置——还包括你在搜索中已经访问过哪些节点，比如B或C或其他节点。

实现您的原始算法，使其调用某些函数询问是否在进行X次移动后已达到“目标状态”。在此之前，该函数只会说“是的，您处于B状态，因此您已经到达了目标”。但现在，让该函数返回“是的，您已经到达了目标状态”，如果搜索路径已经经过了所有感兴趣的点。它将知道搜索是否已经经过了所有感兴趣的点，因为这包含在当前状态中。

在完成上述步骤后，使用一些启发式方法来改进搜索，并进行A*优化。

- Robz

---

我很难理解Dijkstra算法，但你的想法看起来像是暴力破解。 - Micromega

Answer 5

回答你的一个问题...

要将图形作为函数参数传递，您有几个选项。您可以传递指向包含所有节点的数组的指针。如果它是完全连接的图，则可以仅传递一个起始节点并从那里开始工作。最后，您可以编写一个带有所需数据结构的图形类，并传递对该类实例的引用。

至于您关于最接近节点的另一个问题，A*搜索的一部分不是会根据需要进行回溯吗？或者您可以实现自己的回溯方式来处理这种情况。

- DGH

Answer 6

问题是，如果无法从先前的最近节点到达最接近的节点会发生什么？

这一步并不是必要的。也就是说，您不是从先前的最接近点计算路径到当前最接近点，而是试图到达目标节点，当前最接近点是唯一重要的事情（例如，算法不关心上一次迭代您距离目标100公里，因为本次迭代您只有96公里）。

作为一个广泛的介绍，A*算法不直接构建路径：它探索直到确定路径包含在其已探索的区域内，然后根据探索期间记录的信息构建路径。

（我将使用维基百科文章中的代码作为参考实现来帮助解释。）

您有两组节点：closedset和openset

closedset 存储已经完全评估过的节点，也就是说，你已经知道它们离 start 的距离以及它们所有邻居节点所在的集合。因此，你无法再进行更多的计算，可以（某种程度上）忽略它们。（基本上，这些节点完全包含在边界内部。）

openset 存储“边缘”节点，即你已经知道它们离start有多远，但是它们的邻居节点还没有被访问，因此它们是目前搜索的边缘。

（隐含地，存在第三个集合：完全未访问的节点。但是直到它们进入 openset 才会真正访问它们，因此它们并不重要。）

在给定的迭代中，如果你有要探索的节点（即在 openset 中的节点），则需要确定要探索哪个节点。这是启发式算法的工作，它基本上会提示你关于边界上最佳探索点的信息，并告诉你认为哪个节点将具有到 goal 的最短路径。

之前最接近的节点并不重要，它只是稍微扩展了边界，向openset添加了新节点。这些新节点现在成为本次迭代中最接近节点的候选。

起初，openset只包含start，但随后您会进行迭代，在每个步骤中，边界会稍微扩展一点（在最有希望的方向上），直到最终到达goal。

当A*实际进行探索时，它不需要担心哪些节点来自哪里。它不需要，因为它知道它们距离start的距离和启发式函数，这就是它所需要的全部。

然而，为了以后重构路径，您需要记录一些路径信息，这就是camefrom的作用。对于给定的节点，camefrom将其链接到最靠近start的节点，因此您可以通过从goal反向跟随链接来重构最短路径。

如何将“图形”作为函数参数？

通过传递图的表示方式之一。

我真的不明白A*算法如何应用于TSP问题。我的意思是，从A到B找到一条路线，当然，我明白这一点。但是TSP问题呢？我看不出两者之间的联系。

你需要一个不同的启发式和不同的结束条件：goal不再是单个节点，而是所有节点都连接的状态；你的启发式是连接剩余节点的最短路径长度的估计值。

- huon