我的任务是编写 A* 算法（提供启发式算法）的实现，以解决旅行商问题。我了解算法，它很简单，但我看不到实现它的代码。我的意思是，我明白了。节点的优先级队列，按距离 + 启发式（节点）排序，将最近的节点添加到路径上。问题是，如果不能从前一个最近的节点到达最近的节点会发生什么？一个人实际上如何将“图形”作为函数参数？我只是看不到算法实际上是如何运作的，就像代码一样。
在发布问题之前，我阅读了维基百科页面。反复。它并没有真正回答这个问题——搜索图表是一种方式，与解决 TSP 方式不同。例如，您可以构建一个图，其中任何给定时间的最短节点总是导致回溯，因为两条相同长度的路径不相等，而如果您只是尝试从 A 到 B，那么两条路径相同的长度是相等的。
您可以得出一个图表，通过始终最接近的方式永远无法到达某些节点。
我真的不明白 A* 如何适用于 TSP。我的意思是，找到从 A 到 B 的路线，当然，我明白了。但是TSP？我没有看到联系。
使用最小生成树作为启发式。
设置初始状态：代理在起始城市并且没有访问过任何其他城市
目标状态：代理已走遍所有城市，再次到达起始城市
后继功能：生成所有尚未访问的城市
Edge-cost：节点所代表的城市之间的距离，用这个成本来计算g(n)。
h(n)：从当前城市到最近的未访问城市的距离 + 估计旅行所有未访问城市的距离（此处使用 MST 启发式）+ 从未访问城市到起始城市的最近距离。请注意，这是一个可接受的启发式函数。您可以考虑维护访问城市列表和未访问城市列表以方便计算。
如果这只是理解算法及其工作原理的问题，您可能需要考虑在纸上绘制图表，为其分配权重并将其绘制出来。你也可以找到一些显示 Dijkstra 最短路径的动画，维基百科有一个很好的。Dijkstra 和 A* 之间的唯一区别是添加了启发式算法，一旦到达目标节点就停止搜索。至于用它来解决 TSP，祝你好运！
这里的困惑是，您试图解决 TSP的图不是您正在执行 A* 搜索的图。
参见相关：数独求解算法 C++
要解决此问题，您需要：
我能想到的一个简单的例子：
更抽象地考虑一下。暂时忘掉A*吧，无论如何它只是带有启发式的dijkstra。以前，你想从 A 到 B。你的目标是什么？到达 B。目标是以最少的成本到达 B。在任何给定的时间点，您当前的“状态”是什么？可能只是您在图表上的位置。
现在，你想从 A 开始，然后去 B 和 C。你现在的目标是什么？通过 B 和 C，保持最低成本。您可以使用更多节点来概括这一点：D、E、F、...或仅 N 个节点。现在，在任何给定的点上，您当前的“状态”是什么？这很关键：它不仅仅是您在图中的位置——它也是 B 或 C 中的哪一个，或者您迄今为止在搜索中访问过的任何节点。
实现您的原始算法，以便在 X 移动后调用一些函数来询问它是否已达到“目标状态”。之前，该函数只会说“是的，您处于状态 B，因此您处于目标位置”。但是现在，如果搜索的路径已经经过每个兴趣点，让该函数返回“是的，您处于目标状态”。它会知道搜索是否已通过所有兴趣点，因为它包含在当前状态中。
在你得到那个之后，用一些启发式改进搜索，然后 A* 它。
要回答您的一个问题...
要将图形作为函数参数传递，您有多种选择。您可以将指针传递给包含所有节点的数组。如果它是一个完全连接的图，您可以只传递一个起始节点并从那里开始工作。最后，您可以编写一个图形类，其中包含您需要的任何数据结构，并将引用传递给该类的实例。
至于您关于最近节点的其他问题，A* 搜索的一部分是否会根据需要回溯？或者您可以实施自己的回溯来处理这种情况。
问题是，如果不能从前一个最近的节点到达最近的节点会发生什么？
这一步不是必须的。例如，您不是在计算从上一个最近到当前最近的路径，而是在尝试到达目标节点，而当前最接近的是唯一重要的事情（例如，算法不关心最后一次迭代你在 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不再是单个节点，而是所有连接的状态；并且您的启发式是对连接其余节点的最短路径长度的一些估计。