我使用曼哈顿距离+移动自初始板优先级。通常情况下，更多可能的下一个板具有相同的优先级，优先队列如何知道选择哪一个?当我第一次尝试求解时，它总是选择错误的棋盘。我在github上找到了代码，它使用了与我相同的逻辑，但代码总是选择正确的一个，他在compareTo函数中没有任何不同。现在我又开始了，我做了一些类似于github代码的东西，现在它工作了，我不知道为什么。有人知道是什么造成了不同吗?
这是算法
的基础minSearchNode = pq.delMin();
for(Board neighbour : minSearchNode.board.neighbors()){
if(minSearchNode.moves == 0){
pq.insert(new SearchNode(neighbour, minSearchNode.moves + 1, minSearchNode));
}
else if(!neighbour.equals(minSearchNode.previous.board)){
pq.insert(new SearchNode(neighbour, minSearchNode.moves + 1, minSearchNode));
}
}
我在某个地方读到，如果A*做了一个错误的选择并不重要，因为它是启发式的，以后它会找到正确的解决方案。好吧，它不会，程序会尝试数以百万计的组合，总是选择错误的下一个板在平局
一开始我不知道你做错了什么，所以我猜不出是什么改变使结果正确。但你读的是对的。
首先，优先级队列如何打破关系在很大程度上取决于实现。通常的实现是一个堆。但使用DEQ也有好处。无论哪种方法，你只能保证下一个最小值是最小值，而不能保证是哪个最小值。
至于"选错了"，一旦你不得不做任何看起来像是回到对启发式更糟糕的事情上的事情，搜索就会切换它的重点。然后，它会尝试其他的方法。如果启发式是有用的，这意味着它会一直寻找有希望的东西来跟踪，直到找到一条好的路线。如果启发式不能证明有用，它确实可能面临指数爆炸。
第二，大多数A*实现将跟踪它到达的位置。找到通往同一节点的多条路径是很常见的，但只有最好的那条才能最终成为最好的。拒绝重新访问节点控制了搜索空间，使找到最佳路径更容易。但对于搜索一个非常大的图，这可能是令人望而却步的。
第三，我有时发现优先级不是一个简单的数字是很有用的。让它变成一对像(cost + heuristic, -cost)这样的。(这可以通过多种方式实现。)它的作用是根据我们对路线优劣的估计来确定优先级，然后根据我们探索的距离来确定优先级。这意味着如果存在多条同样优秀的路径，我们将先探索其中一条，然后再切换到其他路径。这对你浏览的空间大小有很大的影响。