使用 A* 解决旅行商问题
我的任务是编写 A* 算法的实现（提供启发式算法）来解决旅行商问题。我理解这个算法，它很简单，但我只是看不到实现它的代码。我的意思是，我明白了。节点的优先级队列，按距离+启发式（节点）排序，将最近的节点添加到路径上。问题是，如果从前一个最近的节点无法到达最近的节点，会发生什么？实际上如何将“图”作为函数参数？我只是看不出该算法作为代码实际上是如何运作的。
我在发布问题之前阅读了维基百科页面。反复。它并没有真正回答问题——搜索图表与解决 TSP 是非常非常不同的。例如，您可以构建一个图，其中任何给定时间的最短节点总是导致回溯，因为长度相同的两条路径不相等，而如果您只是尝试从 A 到 B，则两条路径相同长度的则相等。
您可以导出一个图表，通过该图表，某些节点始终先最接近的节点永远不会到达。
我真的不明白 A* 如何应用于 TSP。我的意思是，找到从 A 到 B 的路线，当然，我明白了。但 TSP 呢？我没有看到其中的联系。
I've been tasked to write an implementation of the A* algorithm (heuristics provided) that will solve the travelling salesman problem. I understand the algorithm, it's simple enough, but I just can't see the code that implements it. I mean, I get it. Priority queue for the nodes, sorted by distance + heuristic(node), add the closest node on to the path. The question is, like, what happens if the closest node can't be reached from the previous closest node? How does one actually take a "graph" as a function argument? I just can't see how the algorithm actually functions, as code.
I read the Wikipedia page before posting the question. Repeatedly. It doesn't really answer the question- searching the graph is way, way different to solving the TSP. For example, you could construct a graph where the shortest node at any given time always results in a backtrack, since two paths of the same length aren't equal, whereas if you're just trying to go from A to B then two paths of the same length are equal.
You could derive a graph by which some nodes are never reached by always going closest first.
I don't really see how A* applies to the TSP. I mean, finding a route from A to B, sure, I get that. But the TSP? I don't see the connection.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我在此处找到了一个解决方案，
使用最小生成树作为启发式。
放
初始状态：Agent 位于起始城市，尚未访问过任何其他城市
目标状态：Agent 已访问过所有城市并再次到达起始城市
后继功能：生成所有尚未访问过的城市 边
成本：表示的城市之间的距离通过节点，使用此成本来计算 g(n)。
h(n)：从当前城市到最近的未访问过的城市的距离+前往所有未访问过的城市的估计距离（此处使用MST启发式）+从未访问过的城市到起始城市的最近距离。请注意，这是一个可接受的启发式函数。
您可以考虑维护一个访问过的城市列表和一个未访问过的城市列表以方便计算。
I found a solution here
Use minimum spanning tree as a heuristic.
Set
Initial State: Agent in the start city and has not visited any other city
Goal State: Agent has visited all the cities and reached the start city again
Successor Function: Generates all cities that have not yet visited
Edge-cost: distance between the cities represented by the nodes, use this cost to calculate g(n).
h(n): distance to the nearest unvisited city from the current city + estimated distance to travel all the unvisited cities (MST heuristic used here) + nearest distance from an unvisited city to the start city. Note that this is an admissible heuristic function.
You may consider maintaining a list of visited cities and a list of unvisited cities to facilitate computations.
这里令人困惑的是，您尝试求解 TSP 的图不是您正在执行 A* 搜索的图。
请参阅相关内容： 数独求解算法 C++
要解决此问题，您需要：
我能想到的一个简单示例：
The confusion here is that the graph on which you are trying to solve the TSP is not the graph you are performing an A* search on.
See related: Sudoku solving algorithm C++
To solve this problem you need to:
A quick example I can think up:
如果这只是理解算法及其工作原理的问题，您可能需要考虑在纸上绘制图表，为其分配权重并将其绘制出来。另外，您可能还可以找到一些显示 Dijkstra 最短路径的动画，Wikipedia 有一个很好的动画。 Dijkstra 和 A* 之间的唯一区别是增加了启发式，一旦到达目标节点就停止搜索。至于用它来解决 TSP，祝你好运！
If it's just a problem of understanding the algorithm and how it works you might want to consider drawing a graph on paper, assigning weights to it and drawing it out. Also you can probably find some animations that show Dijkstra's shortest path, Wikipedia has a good one. The only difference between Dijkstra and A* is the addition of the heuristic, and you stop the search as soon as you reach the target node. As far as using it to solve the TSP, good luck with that!
更抽象地思考一下这个问题。暂时忘记 A*，无论如何，它只是带有启发式的 dijkstra。之前，您想从 A 点到达 B 点。您的目标是什么？到达B。目标是以最少的成本到达B。在任何特定时刻，您当前的“状态”是什么？可能只是您在图表上的位置。
现在，你想从A开始，然后去B和C。你现在的目标是什么？跳过 B 和 C，保持最低成本。您可以使用更多节点来概括这一点：D、E、F……或仅 N 个节点。现在，在任何给定的时刻，您当前的“状态”是什么？这很重要：它不仅仅是您在图中的位置，还包括 B 或 C 中的哪一个或您迄今为止在搜索中访问过的任何节点。
实现您的原始算法，以便它在进行 X 移动后调用一些函数来询问它是否已达到“目标状态”。以前，该函数只会说“是的，您处于状态 B，因此您已达到目标”。但是现在，如果搜索路径已经经过每个兴趣点，则让该函数返回“是的，您处于目标状态”。它将知道搜索是否已通过所有兴趣点，因为这些兴趣点包含在当前状态中。
得到之后，通过一些启发式改进搜索，然后 A* 完成。
Think about this a little more abstractly. Forget about A* for a moment, it's just dijkstra's with a heuristic anyway. Before, you wanted to get from A to B. What was your goal? To get to B. The goal was to get to B with the least cost. At any given point, what was your current "state"? Probably just your location on the graph.
Now, you want to start at A, then go to both B and C. What is your goal now? To pass over both B and C, maintaining least cost. You can generalize this with more nodes: D, E, F, ... or just N nodes. Now, at any given point, what is your current "state"? This is critical: it ISN'T just your location in the graph--it's also which of B or C or whatever nodes you have visited so far in the search.
Implement your original algorithm so that it calls some function asking if it has reached "the goal state" after making X move. Before, the function would have just said "yes, you're at state B, therefore you are at the goal". But now, let that function return "yes, you're at the goal state" if the search's path has passed over each of the points of interest. It'll know whether or not the search has passed over all points of interest because that's included in the current state.
After you get that, improve the search with some heuristic, and A* it up.
要回答您的问题之一...
要将图形作为函数参数传递，您有多种选择。您可以将指针传递给包含所有节点的数组。如果它是一个完全连接的图，您可以仅传递一个起始节点并从那里开始工作。最后，您可以编写一个图形类，其中包含您需要的任何数据结构，并传递对该类实例的引用。
至于您关于最近节点的其他问题，A* 搜索不是会根据需要回溯的一部分吗？或者您可以实施自己的回溯来处理这种情况。
To answer one of your questions...
To pass a graph as a function argument, you have several options. You could pass a pointer to an array containing all the nodes. You could pass just the one starting node and work from there, if it's a fully connected graph. And finally, you could write a graph class with whatever data structures you need inside it, and pass a reference to an instance of that class.
As for your other question about closest nodes, isn't part of A* search that it will backtrack as needed? Or you could implement your own sort of backtracking to handle that kind of situation.
这一步没有必要。例如，您并不是计算从前一个最近的节点到当前最近的节点的路径，而是尝试到达目标节点，而当前最接近的节点是唯一重要的事情（例如，算法不关心最后一次迭代）你距离 100 公里，因为本次迭代你距离只有 96 公里）。
作为一个广泛的介绍，A*并不直接构造一条路径：它会进行探索，直到它明确知道该路径包含在它所探索的区域内，然后根据探索过程中记录的信息构造路径。
（我将使用维基百科文章中的代码作为参考实现以帮助我的解释。）
您有两组节点：
Closedset和OpenSetClosedset保存已完全评估的节点，即您确切地知道它们距start有多远，并且它们的所有邻居都位于两个集合之一中。您无法对它们进行更多计算，因此我们可以（某种程度上）忽略它们。 （基本上这些完全包含在边界内。）openset保存“边界”节点，您知道它们距离start有多远，但您还没有触及它们的邻居，因此到目前为止它们位于您搜索的边缘。（隐式地，存在第三组：完全未触及的节点。但是直到它们处于
openset中之前你才真正触及它们，所以它们并不重要。）在给定的迭代中，如果你已经有了要探索的节点（即
openset中的节点），您需要弄清楚要探索哪个节点。这是启发式的工作，它基本上通过告诉您它认为哪个节点具有到达目标的最短路径来提示您接下来最好探索边界上的哪个点。之前最接近的节点是无关紧要的，它只是稍微扩展了边界，向
openset添加了新节点。这些新节点现在是本次迭代中最接近节点的候选节点。起初，
openset仅包含start，但随后进行迭代，并且在每一步中边界都会扩展一点（在最有希望的方向上），直到最终到达目标。当A*实际进行探索时，它并不关心哪些节点来自哪里。它不需要，因为它知道它们与
start的距离和启发式函数，这就是它所需要的。然而，为了稍后重建路径，您需要对路径进行一些记录，这就是
camefrom。对于给定节点，camefrom将其链接到最接近start的节点，因此您可以通过从goal向后跟踪链接来重建最短路径代码>.通过传递图表的表示形式之一。
您需要不同的启发式方法和不同的结束条件：目标不再是单个节点，而是所有事物都连接起来的状态；你的启发式是对连接其余节点的最短路径长度的一些估计。
This step isn't necessary. As in, you aren't computing a path from the previous closest to the current closest, you are trying to get to your goal node, and the current closest is the only thing that matters (e.g. the algorithm doesn't care that last iteration you were 100km away, because this iteration you are only 96km away).
As a broad introduction, A* doesn't directly construct a path: it explores until it definitely knows that the path is contained within the region it has explored, and then constructs the path based on the information recorded during the exploration.
(I'm going to use the code in the Wikipedia article as a reference implementation to aid my explanation.)
You have a two sets of nodes:
closedsetandopensetclosedsetholds nodes that have been fully evaluated, that is, you know exactly how far they are fromstartand all their neighbours are in one of the two sets. This there is no more computation you can do with them and so we can (sort of) ignore them. (Basically these are completely contained within the border.)opensetholds "border" nodes, you know how far these are fromstart, but you haven't touched their neighbours yet, so they are on the edge of your search so far.(Implicitly, there is a third set: completely untouched nodes. But you don't really touch them until they are in
opensetso they don't matter.)At a given iteration, if you've got nodes to explore (that is, nodes in
openset), you need to work out which one to explore. This is the job of the heuristic, it basically gives you a hint about which point on the border will be the best to explore next by telling you which node it thinks will have the shortest path togoal.The previous closest node is irrelevant, it just expanded the border a bit, adding new nodes to
openset. These new nodes are now candidates for the closest node in this iteration.At first,
opensetonly containsstart, but then you iterate and at each step the border is expanded a little (in the most promising direction), until you eventually reachgoal.When A* is actually doing the exploration, it doesn't worry about which nodes came from where. It doesn't need to, because it knows their distance from
startand the heuristic function and that's all it needs.However to reconstruct the path later, you need to have some record of the path, this is what
camefromis. For a given node,camefromlinks it to the node that is closest tostart, so you can reconstruct the shortest path by following the links backwards fromgoal.By passing one of the representations of a graph.
You need a different heuristic and a different end condition:
goalis no longer a single node any more, but the state of having everything connected; and your heuristic is some estimate of the length of the shortest path connecting the remaining nodes.