java - 给定一个网格，如果启发式更好，最好先搜索跳到整个单元格吗？

Question

我目前正在使用二维数组来实现贪婪最佳优先搜索来表示网格。我的实现现在返回打开的节点。我正在使用 PriorityQueue。当我返回遍历路径/打开的节点并查看节点时，该算法有时会从网格的一侧跳到另一侧。它应该这样做吗？玩家在遍历网格时跳转到网格另一侧的单元格是没有意义的，因为那里的启发式算法更好，然后再跳回去。 我正在使用这个网格:

这些是已经打开的所有节点的(y,x)坐标(注意是y,x代表一个二维数组):

0,0 Goes across the top of the board
0,1
0,2
0,3
0,4
0,5
1,5 Goes down one cell
1,4 goes left
1,6 goes right 2 spaces
0,6 goes up
1,7 goes down the side of the board
2,7 \/
3,7 \/
4,7 \/
5,7 \/
0,7 jumps up across the board
6,7
1,2 jumps up across the board
2,2
3,2
4,2
3,1
4,1
3,0
2,1
5,2
5,1
4,0
2,0
7,7 jumps up across the board
7,6
7,5
6,5
5,5
5,4
4,4
3,4
3,5

Answer 1

如果在将节点添加到优先级队列时跟踪每个节点的父节点，那么您可以认为队列不仅跟踪节点，而且跟踪整个路径段。队列中的每个节点代表一个可行的路径段，该路径段结束于该节点。

例如，当您到达 5,7 时，您确定这条路径是迄今为止最有希望的路径:

(0,0 0,1 0,2 0,3 0,4 0,5 1,5 1,6 1,7 2,7 3,7 4,7) [5,7]

(我已将节点放在 [brackets] 中，并将到达该节点的路径放在 (括号) 中。沿着父链向后产生路径.)

当 5,7 节点没有成功时，将其所有 5,7 的后继节点添加到队列中，然后从队列中拉出下一个节点。在这一点上，事实证明你没有得到 5,7 的后继者之一。相反，启发式函数决定尝试不同的节点:

(0,0 0,1 0,2 0,3 0,4 0,5) [0,6]

它尝试了这个，没有达到目标，然后继续。现在回到考虑 5,7 的后继者之一:

(0,0 0,1 0,2 0,3 0,4 0,5 1,5 1,6 1,7 2,7 3,7 4,7 5,7) [6,7]

等等。