2

I am working through an example of best-first search on a graph, and I'm having some trouble understanding exactly what the process should be.

This is the graph I have:

enter image description here

The heuristic values are in the boxes next to the applicable nodes. So from my understanding from the textbook I'm working through, calculating the path from node a to node x is as follows:

Node b has a cost value of 6 (actual cost 3 + heuristic value 3). Node c has a cost value of 5 (actual cost 2 + heuristic value 3). Thus, the next node from node a would be node c

Node e has a cost value of 12 (actual cost 2 + 4, + heuristic value 6). As there are no other nodes from node c, the next node would be node e

Node x has a cost value of 8 (actual cost 2 + 4 + 2, + heuristic value 0). As x is the goal node, the next node would be node x

This seems a bit weird to me though. Shouldn't node b also be explored at some point? Or does the best-first search algorithm just select the next best node until it reaches the goal node, ignoring any other paths?

Any insights would be appreciated, thanks!

2 Answers 2

4

Node e has a cost value of 12 (actual cost 2 + 4, + heuristic value 6). As there are no other nodes from node c, the next node would be node e

This depends a bit on what type of 'best first' search you are talking about. In a 'greedy best first', then yes, you would just make locally optimal decisions on the path to take. But this is not guaranteed to result in the shortest possible path.

If you want the global optimal path you would need to consider all previous candidates as well. See for example A* for the typical optimal path finding algorithm. All the candidate nodes are kept in a priority queue, often a 'min heap', and is usually called the 'open set'.

So in this case 'b' would have a lower cost than 'e', so should be processed before 'e'.

After you have visited b you will find that you can reach 'e' by multiple paths, where the b->e route offers a lower cost. Ofc, the 'd' node should offer an ever lower cost, so would be the next node to consider.

You might also want to take a look at Admissibility of your heuristic. If the heuristic is higher than the actual remaining cost you are not guaranteed to find the best path. This seem to be a problem for your 'e' node, since 6 is higher than the actual remaining cost of 2. So while the best path is a-b-e-x, you would find a-b-d-x.

2

"Best-first" means locally best first. You choose c over b because it is cheaper at that point, but b remains on the search agenda. After you've found a path with actual cost 8, you've still got a path with estimated cost at least 6, but partial actual cost only 3, so you'd continue the algorithm with looking for an alternative going via b. And if that road finds a cheaper complete path, then that would be the result. (But in this case the alternative also has actual cost 8, so choosing c was in fact the right move.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.