Heuristic and A* algorithm

Question

I was reading about dijkstra algorithm and A* star algorithm. I know that the difference is the heuristic used. But what is a heuristic and how this influence the algorithms? Heuristic is just an way to measure the distance? But dijkstra considers the distance too? Sorry, but my question is about heuristic and what it means and why to use them... (I had read about it, but don't understant) Other question: When should be used each one?

Thank you

Answer 1

A heuristic basically means an idea or an intuition! Any strategy that you use to solve a hard problem is a heuristic! In some fields (like combinatorial problems) it refers to the strategy that can help you solve a NP hard problem suboptimally within a polynomial time.

Answer 2

In this context, a heuristic is a way of providing the algorithm with some form of extra evaluative information, so that the algorithm can find a 'good enough' solution, without exhaustively searching every possible solution.

Dijkstra's Algorithm does not use a heuristic. It expands outwards from the start node, and examines every node in the graph in order to find the shortest path. While this is accurate, it can be computationally expensive.

By comparison, the A* algorithm uses a distance + cost heuristic, to guide the algorithm in its choice of the next node to explore. This means that the algorithm finds a possible search solution without examining every node on the graph. It is therefore much cheaper to run, but at a loss of complete accuracy. It works because the result is usually close enough to the optimal solution, and is found cheaper than an exhaustive search of the entire graph.

As to when you should use each, it really depends on the application. However, using the A* algorithm requires an admissible heuristic, so this may not be applicable in situations where such information is unavailable to the algorithm.

Answer 3

Dijkstra solves the single-source routing problem, i.e. it gives you the cost of going froma single point to any other point in the space.

A* solves a single-source single-target problem. It gives you a minimum distance path from a given point to another given point.

A* is usually faster than Dijkstra provided you give it an admissible heuristic, this is, an estimate of the distance to the goal, that never overestimates said distance. Contrary to a previous answer given here, if the heuristic used is admissible, A* is complete and will give you the optimal answer.