解释A-star算法的java实现

Question

我最近有一个关于A星形算法的Java实现的课程工作，其中输入数据是20 * 20网格的形式。

根据A- star算法伪码，选择开放列表中最终代价最低的节点作为当前移动节点。

在用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，这正是您想要的。

如果您只是按成本排序(假设是int?)然后你可以这样做：

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

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