Given a grid, would best first search jump to a ce

问题:

I am currently implementing the Greedy Best First Search with a 2D array to represent a grid. My implementation right now returns the opened nodes. I am using a PriorityQueue. When I return the traversed path/opened nodes and take a look at the the nodes it appears that the algorithm jumps from one side of the grid to another some times. Is it supposed to do this? It doesn't make sense for a player when traversing the grid to jump to a cell on the other side of the grid just because the heuristics over there are better and then jump back. I am using this grid:

These are the (y, x) coordinates of all the nodes that have been opened (note that it is y, x to represent a 2D array):

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

回答1:

If you track each node's parent when you add them to the priority queue then you can think of the queue as tracking not just nodes, but entire path segments. Each node in the queue represents a viable path segment that ends at that node.

For example, at the point you reach 5,7 you've determined that this path is the most promising so far:

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

(I've put the node in [brackets] and the path to get to that node in (parentheses). Following the chain of parents backwards yields the path.)

When the 5,7 node doesn't pan out, you add all of its successors of 5,7 to the queue, then you pull the next node from the queue. At this point it turns out you don't get one of 5,7's successors. Instead the heuristic function decides to try a different node:

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

It tries this, doesn't reach the goal, and continues on. Now it goes back to considering one of 5,7's successors:

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

And so on.