我的任务是编写一个将解决旅行商问题的A *算法（启发式提供）的实现。我理解算法，它很简单，但我看不到实现它的代码。我的意思是，我明白了。按距离+启发式（节点）排序的节点的优先队列将最近的节点添加到路径上。问题是，如果从最近的节点无法到达最近的节点会发生什么？一个人如何将一个“图”作为一个函数参数？作为代码，我看不出算法的实际功能。使用A *解决旅行推销员
我在发布问题前阅读了维基百科页面。反复。它并没有真正回答这个问题 - 搜索图表与解决TSP的方式不同。例如，您可以构造一个图，其中在任何给定时间的最短节点总是导致回溯，因为两条相同长度的路径不相等，而如果您只是试图从A到B，那么两条路径长度相同。
您可以导出一个图形，通过该图形总是先离得近，从而永远不会到达某些节点。
我真的不知道A *如何适用于TSP。我的意思是，找到从A到B的路线，当然，我明白了。但是TSP？我没有看到连接。
要回答你的问题一个...
传递一个图形作为函数参数，你有几种选择。您可以将指针传递给包含所有节点的数组。如果它是一个完全连接的图，那么您可以仅传递一个起始节点并从那里开始工作。最后，你可以用你需要的任何数据结构编写一个图形类，并将引用传递给该类的一个实例。
至于你关于最近节点的其他问题，是不是A *搜索的一部分，它会根据需要回溯？或者你可以实现你自己的回溯来处理这种情况。
如果只是理解算法及其工作原理的问题，您可能需要考虑在纸上绘制图形，为其分配权重并将其绘制出来。你也可以找到一些展示Dijkstra最短路径的动画，Wikipedia有一个很好的动画。 Dijkstra和A *之间的唯一区别是增加了启发式，并在您到达目标节点后立即停止搜索。至于用它来解决TSP，祝你好运！
“祝你好运”，的确如此！ – 2010-12-15 18:38:18
如果含义是用A *解决TSP将很困难，但事实并非如此。我同意上面的评论，从Dijkstra开始可能会更容易一些，但是一旦你决定实现细节，两者都是非常微不足道的。 – 2010-12-15 18:38:36
我想我没有看到A *如何帮助你解决TSP问题。通过只允许选择最近的未访问邻居，您将获得有效的路由，但它不一定是最短路由。 TSP（正如我一直声明的）要求最短的非重复路径。也许我错误地解释了OP的目标。 – fbl 2010-12-15 19:58:46
想想这更抽象一点。忘记A *了一会儿，它只是dijkstra的启发而已。以前，你想从A到B得到什么？你的目标是什么？到达B.目标是以最低的成本到达B.在任何时候，你现在的“状态”是什么？可能只是你在图表上的位置。
现在，你想从A开始，然后去B和C.你现在的目标是什么？为了传递B和C，保持最低成本。你可以用更多的节点来概括它：D，E，F ......或者仅仅是N个节点。现在，在任何一点上，你现在的“状态”是什么？这很关键：它不仅仅是你在图中的位置 - 它还是B或C中的哪一个，或者你在搜索中到目前为止访问过的任何节点。
实现您的原始算法，以便在调用X移动后调用某个函数询问它是否已达到“目标状态”。之前，该功能只会说“是的，你处于B状态，因此你在目标上”。但是现在，如果搜索路径遍历了每个感兴趣的点，那么让该函数返回“是的，你处于目标状态”。它会知道搜索是否已经通过了所有关注点，因为它包含在当前状态中。
在得到这些之后，用一些启发式方法改进搜索，然后A *起来。
我很难理解dijekstrs，但你的想法看起来像蛮力。 – Bytemain 2012-02-08 09:40:53
我找到了解决办法here
使用最小生成树的启发。
集 初始状态：代理在启动城市还没有去过的其他城市
目标国家：代理已访问过的所有城市和到达起始城市再次
后继功能：生成所有城市尚未访问
边缘成本：由节点表示的城市之间的距离，使用此成本来计算g（n）。
h（n）：距离当前城市最近的未访问城市的距离+所有未访问城市的估计距离（此处使用的MST启发式）+从未访问城市到起始城市的最近距离。请注意，这是一个可接受的启发式功能。 您可能会考虑维护访问城市的列表和未访问城市的列表以方便计算。
有可能构建有问题的图，其中MST违反直觉行为。假设你有一个图表，有N个城市可供参观。使用MST可以获得到目标的剩余距离的下限。然后移除一座城市，留下N-1个城市参观。目标的剩余距离现在可能更大！这个问题在本周中陷入了困境，因为我试图在我的A *最近邻居搜索中使用最小生成树。我的解决方案是减去奖励次数，以减少访问城市的数量以平滑功能。 – 2017-11-09 22:17:37
问题是，如果最近的节点无法从前一个最近的节点到达会发生什么？
此步骤不是必需的。如你所说的，你不是在计算从前一个最接近到最接近的路径，而是试图到达你的目标节点，并且当前最接近的是唯一重要的事情（例如，该算法不关心最后一次迭代你距离100公里，因为这次迭代只有96公里）。作为一个广泛的介绍，A *并不直接构造一条路径：它探索直到它明确知道路径包含在它探索的区域内，然后根据探索过程中记录的信息构建路径。
（我将使用the code in the Wikipedia article作为一个参考实现，以帮助我的解释。）
你有两套节点：closedset和openset
closedset认为已经充分评估节点，也就是说，你知道他们距离start有多远，并且他们所有的邻居都在两组中。这样就没有更多的计算可以用它们做，所以我们可以（忽略）忽略它们。 （基本上这些边界内完全包含。）
openset举办的“边界”的节点，你知道有多远这些都是start，但是你有没有触动他们的邻居呢，所以他们对搜索的边缘至今。
（含蓄的，还有第三组：完全不变节点，但你真的不碰他们，直到他们在openset所以他们并不重要。）
在一个给定的迭代，如果你”已经有了探索节点（也就是openset中的节点），您需要确定要探索哪一个节点。这是启发式的工作，它通过告诉你哪个节点它认为将具有到goal的最短路径，从而基本上给出了关于边界上的哪一点将是最佳探索的暗示。
上一个最接近的节点是不相关的，它只是扩大了边界，增加了新的节点到openset。这些新节点现在成为本次迭代中最近节点的候选节点。
起初，openset只包含start，但你迭代，并在每一步的边界扩展一点（在最有前途的方向），直到最终达到goal。
当A *实际进行探索时，它并不担心哪个节点来自哪里。它不需要，因为它知道它们与start和启发式函数的距离，这就是它所需要的。
但是为了稍后重建路径，您需要有一些路径记录，这就是camefrom。对于给定节点，camefrom将其链接到最靠近start的节点，因此您可以通过从goal反向链接来重建最短路径。
如何实际上将“图形”作为函数参数？
通过representations of a graph之一。
我真的不知道A *如何适用于TSP。我的意思是，找到从A到B的路线，当然，我明白了。但是TSP？我没有看到连接。
你需要一个不同的启发式和不同的终止条件：goal不再是单个节点的任何更多，但具有一切连接的状态;你的启发式就是连接其余节点的最短路径长度的一些估计值。
的混乱这里是上正在试图解决的TSP图为不图表要执行A *搜索上。
参见相关：Sudoku solving algorithm C++
为了解决这个问题，你需要：
一个简单的例子我能想起来：
[A *]（http://en.wikipedia.org/wiki/A*_search_algorithm）似乎是b从CS课程中我能记得的一个非常好的总结。 [Dijkstra算法]（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）非常相似（但更简单），因此它可能更好。在这两种情况下，优先队列都很方便。 – 2010-12-15 18:30:53
@pst：如果你想从点A到点B，A *和Dijkstra的算法是有用的。如果你想从具有特定约束的路径从点A到点A，那么这是另一回事。 – 2010-12-15 18:56:45
当我在Uni时（在上一个千年期间），我们有一项任务是要以我们想要的任何语言实现A *，大多数选择了我们最熟悉的C++，但是我选择了Prolog，因为它似乎更适合问题。短小的故事，我完成任务比大多数人快得多，你可以从Prolog开始，跳过中间阶段。 – Motti 2010-12-15 19:54:08