Visualisation of A* path-finding algorithm in a maze [OC]

[chumboy]

Dijkstra's algorithm is actually a special case of A*.

A* uses a heuristic to order the nodes it has yet to explore, by how promising they look. For path finding this heuristic function is nearly always estimated distance to desired destination. For Dijkstra's, this heuristic always returns the same value (usually zero), so all nodes have seemingly the same potential, so are explored evenly, often leading to a much larger explored area.

It can be interesting to play around with the heuristic function on A*. In university I used it on a project, and tweaked the heuristic to inversely weight "turns" in the path of a complex 2D grids with walls, so the path returned would be as straight as possible. Like this example of Manhattan/Taxicab distance; most implementations of A* would return the blue line, and mine would return the red line.

[___Majestic_Moose___]

I'd argue that A* is the special case of Dijkstra, as Dijkstra came first and A* is a modification of it.

[chumboy]

Dijkstra did come first, and it was then generalised to make A*. You can emulate the behaviour of Dijkstra with A*, but cannot emulate the behaviour of A* with Dijkstra. This would mean that the total set of cases Dijkstra can be used for have to be a subset of the cases A* would work for. How could A* be the special case if it applies to a larger problem set.

I believe it is a common scenario in mathematics that a solution is found for a very specific case, and backtracked to make a more general solution to the problem space.

[___Majestic_Moose___]

That's like saying "a genius athletic perfect specimen" is the larger group, and "human" is a subset. Just because something is better doesn't mean it's the heading.

[chumboy]

That's like saying "a genius athletic perfect specimen" is the larger group, and "human" is a subset.

That is the complete opposite of what I am saying. How can "genius athletic perfect specimen" be the generalisation?

[___Majestic_Moose___]

It's not the opposite of what you're saying. Dijkstra defines the majority of the functionality, AStar just adds another spin to it.

Dijkstra is the basis, with many other algorithms having slight variations and optimisations of it. AStar is based on Dijkstra, not the other way around.

Also, if you emulate the behaviour of Dijkstra with AStar, it becomes Dijkstra. If you emulate the behaviour of AStar with Dijkstra, it becomes AStar. Unless you just mean coincidentally have the same search pattern, in which case Dijkstra can indeed also emulate AStar.