0
$\begingroup$

I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more vertices than Dijkstra's algorithm. What I'm asking however is the following. Given an A star algorithm with some heuristic which is not the heuristic returning 0, could it possibly check more vertices than Dijkstra's algorithm?

My intuition is yes, and I will show why. Consider the Figure underneath, in which we consider a large amount of discrete points in this plane, representing the vertices of the graph, and connecting arcs with cost 1 between all adjacent points, creating a grid graph. Suppose the heuristic used by A star is euclidean distance, and suppose many curved walls like the ones I drew in the middle exist in this fashion, not only the three I drew. A star in this situation would be "tricked" to go in between the walls, since the heuristic would guide it close to the point, only to find out it's a dead end (or a local optimum of some sorts if you will), and this would happen as many times as there are walls. Dijkstra would not be tricked this way. The only problem with my example here, is that Dijkstra will probably not outperform A star here. So, is my intuition wrong, or do more clever instances than this one exist in which Dijkstra can in fact outperform A star in terms of vertices checked?

enter image description here

$\endgroup$
1
$\begingroup$

No,

Dijkstra will explore all nodes with cost less than the cost of the completed path. While A* will explore all nodes with cost+heuristic less than the cost of the completed path.

Thus if the heuristic is always positive then A* will expand less or equal nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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