CODEWITHSUNDEEP
algorithmmathematical-optimizationa-star
Sharikov Vladislav
Sharikov Vladislav

Reputation: 7269

What heuristic cost is correct? Why my is incorrect? Finding optimal path on graph

I have simple graph and I need to find heuristic costs for this graph.

Graph is (matrix representation):

0 1 2 0 0 0 0
1 0 0 3 3 2 0
3 0 0 2 0 0 0
0 3 1 0 1 0 0
0 3 0 1 0 6 0
0 2 0 0 6 0 2
0 0 0 0 0 2 0

Image:

graph

Values in brackets means heuristic costs of the vertex for current goal vertex.

Green vertex is start and red vertex is goal.

I created this heristic costs matrix: 

0 2 6 3 1 9 5
9 0 2 4 6 4 1
1 3 0 5 2 9 4
3 1 5 0 1 7 8
0 6 2 1 0 10 14
2 1 6 3 7 0 5
1 4 3 2 1 3 0

I have to explain this. This matrix represents this: for example goal vertex is 7; we find 7th row in matrix; value in 1st col means heuristic cost from 1 vertex to 7 vertex (7 is goal); value in 5nd col means heurisitc cost from 5 vertex to 7 vertex (7 is goal); if 5 is goal, we will work with 5 row, etc...

This heusristic costs based on nothing. I don't know how to find good heuristic costs. That is the question.

To summarize:

Firstly, my algorithm found wrong path (because of wrong heuristics probably). It found 1-3-4-5 (length 5), but best is 1-2-5 (length 4).

Also, teacher said, that my heuristic costs prevents the algorithm to find good path, but not helps him. I have problems with translating what he said into english, but he said somethink like: "your heuristic mustn't overestimate best path". What does it mean?

So the question: how to find good heuristic costs in my case?

Upvotes: 0

Views: 868

Answers (1)

amit
amit

Reputation: 178431

I am going to wrap my comments as an answer.

First, note that "overestimate best path" means that your shortest path from some node v to the goal is of length k, but h(v)=k' such that k'>k. In this case, the heuristic is overestimating the length of the path. A heuristic that does it for 1 or more nodes is called "inadmissible", and A* is not guaranteed to find the shortest path with such a heuristic.

An admissible heuristic function (never overestimating) is guaranteed to provide the optimal path for A*. The simplest admissible heuristic is h(v) = 0 for all v. Note that in this case, A* will actually behave like Dijsktra's Algorithm (which is basically an uniformed A*).

You can find more informative heuristics, one example is to first pre-process the graph and find the shortest unweighted path from each node to the goal. This can be done efficiently by BFS. Denote this unweighted distance from some v to the goal as uwd(v).
Now, you can create a heuristic which is uwd(v) * MIN_WEIGHT, where MIN_WEIGHT is the smallest edge weight in the graph.

Upvotes: 1

Related Questions