1

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

这些是已经打开的所有节点的(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
4

1 回答 1

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]和到达该节点的路径放在 . 中(parentheses)。沿着父链向后产生路径。）

当 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]

等等。

于 2012-11-17T20:50:49.170 回答