What kind of algorithm paradigm/algorithm design paradigm is A* (A star) pathfinding algorithm?

Question

I'm not sure about what kind of design paradigm is A* (A star) pathfinding algorithm. According of the topics of the book "Introduction to the Design & Analysis of Algorithms" by Anany Levitin, I think the design paradigm is a greedy technique, because this algorithm is a combination of Dijktra's algorithm and greedy best first which are greedy techniques. But I'm not sure if that is a good reasoning.

Edit: According Emma comment, she gave me a link of Wikipedia where it says " Dijkstra and A* are special cases of dynamic programming. A* itself is a special case of a generalization of branch and bound." link. But in this other Wikipedia link says "Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms for graph search and shortest path finding."

Answer 1

It's not greedy.

According to Wikipedia, a greedy algorithm "is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage", and that does not apply to A* (IMHO it's an error to list A* in the Examples section of that Wikipedia page).

Why?

My understanding of the above-mentioned definition is that "making the locally optimal choice at each stage" implies that we disregard the other choices possible in that state - in a greedy strategy we never reconsider a choice made previously.

And that's not true for A*, A* will eventually explore all choices made at any stage, if the previous choice at that stage no longer looks "most promising". It's true that A* will begin its exhaustive exploration with the locally optimal choice.

My argumentation is based on the straightforward, intuitive mapping that the words "stage" and "choice" from the definition map to "graph node" and "graph edge" from the A* algorithm. But if you want to map "stage" to "subgraph explored", then A* indeed qualifies as being greedy - but with such a non-intuitive mapping, even breadth-first becomes greedy.

Answer 2

I think the main paradigm of A* is exhaustive search (or branch and bound (b&b), many people consider exhaustive search and b&b as two different paradigms, but i think b&b is just a technique for implementing and improving exhaustive search), like other exhaustive search, A* will explore the entire solution space (exclude solutions determined is worst than optimal solution). Greedy is just an additional technique, used to navigate the search in the most promising direction.

Answer 3

You have a good question!

Greedy is setteld!!!

I guess it would depend and I agree with "that's a bit of apples and oranges." in the question's comment.

The answer to your specific question might be here or here.

It is considered Greedy or Dynamic Programming (DP), according to some wikipedia pages.

However, templatetypedef also has a good point in the comment: "I would have pegged it as greedy given that it’s making a locally optimal decision at each point."

---

Greedy

Dijkstra's algorithm and the related A* search algorithm are verifiably optimal greedy algorithms for graph search and shortest path finding.

---

Dynamic Programming

What sets A* apart from a greedy best-first search algorithm is that it takes the cost/distance already traveled, g(n), into account.

Some common variants of Dijkstra's algorithm can be viewed as a special case of A* where the heuristic h(n) = 0 for all nodes; in turn, both Dijkstra and A* are special cases of dynamic programming. A* itself is a special case of a generalization of branch and bound.

Reference

• A* search algorithm

• Algorithmic paradigm