Path Finding algorithm help..

[XA04]

Got an exam on Monday which is probably going to have this in it. However I'm having a problem understanding part of my lecturers slides.. now I could ask him but it's now the weekend!

Heres whats from the slides:

A commonly used algorithm is a simplified
A* algorithm
This simplified A* algorithm uses a cost
function f(x) based on distance:
f(x) = g(x) + h(x)
where g(x) is the distance travelled from start node to node x
where h(x) is the distance from node x to end node

Algorithm:
1. Compare f(x) for all possible initial nodes
2. Select best node as the lowest distance cost
f(x)
3. Travel to next node(s) from the lowest
distance cost f(x) node
4. Compare f(x) for all of these nodes and that
from the other possible routes already
calculated
5. Repeat from 2 until reached end node

I think I understand most of it, but I don't understand how the middle dashed line is calculated? the distance that is 4.5... I would have thought you'd have to stick on the given paths?

Thanks!

[mikemikemi]

A*'s just a search algorithm to determine least cost path from one node to another.

In your example above h(x) isn't calculated, it's given to enable you to answer the question as it's the cost heuristic used as part of f(x) to determine the next node to search. Obviously, outside of the question someone would have to determine an admissible heuristic, for routing it'll probably be straight line distance. Therefore, I think your dashed line is a visual example of h(a), but does not represent a path on the graph.

Hope that makes sense.

[XA04]

A*'s just a search algorithm to determine least cost path from one node to another.

In your example above h(x) isn't calculated, it's given to enable you to answer the question as it's the cost heuristic used as part of f(x) to determine the next node to search. Obviously, outside of the question someone would have to determine an admissible heuristic, for routing it'll probably be straight line distance. Therefore, I think your dashed line is a visual example of h(a), but does not represent a path on the graph.

Hope that makes sense.

Providing that h(x) is provided... then I think I'll be fine!. I think you could be right, at least I hope you are.

Thanks very much