java - A星算法java实现详解

Question

我最近学习了 A 星算法的 Java 实现，其中输入数据采用 20 * 20 网格的形式。

根据A星算法伪代码，选择open list中最终代价最低的节点作为当前要前往的节点。

在实际用 Java 实现该算法之前，我经历了许多其他语言的不同实现，例如 ruby​​、python 和 c++。

在其他语言的实现中，一个共同点是在遍历路径时，它坚持以最终成本最低的节点作为新的当前节点的算法方法。

我使用了一个优先级队列来实现这个算法的开放列表，在下面添加比较器，它给最终成本较低的节点更高的优先级

PriorityQueue<GridPiece> unvisitedNodes = new PriorityQueue<>(10,
            (gridPie1, gridPie2) -> ((GridPiece) gridPie1).getFinalCost() > 
((GridPiece) gridPie2).getFinalCost()? -1
                    : ((GridPiece) gridPie1).getFinalCost() < ((GridPiece) 
gridPie2).getFinalCost() ? 1 : 0);

但是当我运行算法时，我得到了可能的最长路径。 两个图像的图例是，路径是橙色的，源是粉红色的，目的地是紫色的。

当我针对基于网格的输入研究此算法的 Java 实现时，如果使用优先级队列，它们总是会为最终成本较高的节点提供更高的优先级。我通过将比较器更改为此来尝试这种方法

PriorityQueue<GridPiece> unvisitedNodes = new PriorityQueue<>(10,
            (gridPie1, gridPie2) -> ((GridPiece) gridPie1).getFinalCost() < 
((GridPiece) gridPie2).getFinalCost()? -1
                    : ((GridPiece) gridPie1).getFinalCost() > ((GridPiece) 
gridPie2).getFinalCost() ? 1 : 0);

然后我得到了更好的路径；

我的简单请求是一个简短的解释，说明为什么当实现完全遵循伪代码时算法没有按预期运行，以及为什么需要切换节点的优先级(最终成本较高的优先级)在 Java 实现中工作的算法？

可以找到该项目的完整代码 here .

Answer 1

相对于给定的顺序，优先队列的头部是最少的元素。当第一个元素的成本大于第二个元素的成本时，您的比较器返回 -1。换句话说，您将成本最高的元素放在首位。这就是为什么队列的头部拥有成本最高的网格饼。

在您的第二个实现中，当第一个元素的成本小于第二个元素的成本时，比较器返回 -1，这正是您想要的。

如果您只是按成本排序(大概是一个整数？)那么您可以这样做:

new PriorityQueue<GridPiece>(Comparator.comparingInt(GridPiece::getFinalCost));

很少有理由指定初始容量。对于像您这样的小型网格，只需使用默认容量即可使事情变得简单。