A* algorithm on a directed graph [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

Hello Can anyone help me understand how the A* algorithm works on this graph?

I want to find the lowest cost path from 1 to 7.

Here is how I solved the problem: From 1 -> 7:

{1,2}f = 2+7=9
 {1,3}f = 11+0=11
 {1,4}f = 1+11=12

EXPAND 2

{1,3}f = 11+0=11
 {1,4}f = 1+11=12
 {1,2,5}f = (2+3)+5=10

EXPAND 5

{1,3}f = 11+0=11
 {1,4}f = 1+11=12
 {1,2,5,3}f = (2+3+5)+0=10
 {1,2,5,7}f = (2+3+7)+0=12

EXPAND 3

{1,3}f = 11+0=11
 {1,4}f = 1+11=12
 {1,2,5,7}f = (2+3+7)+0=12
 {1,2,5,3,7}f = (2+3+5+1)+0 = 11
 {1,2,5,3,6}f = (2+3+5+1)+1=12

So the correct answer is {1,2,5,3,7}f = (2+3+5+1)+0 = 11. Am I write?

Answer 1

I'm going to assume that the numbers in the brackets are the estimated distances from a given node to the goal using some heuristic (at first glance they seem to be consistent with an admissible heuristic function). If this is the case, then this is the h(x) in the cost equation:

f(x) = g(x) + h(x)

g(x) would be the actual cost of the path from the source to node x. Starting from node 1, we have 3 outgoing edges: 2, 3 and 4.

f(2) = g(2) + h(2)
f(3) = g(3) + h(3)
f(4) = g(4) + h(4)

Filling in the numbers from your graph we get:

f(2) = 2 + 7 = 9
f(3) = 11 + 0 = 11
f(4) = 1 + 11 = 12

f(2) is the lowest cost, so we choose node 2. The next step isn't very instructive (since we can only go to node 5) except to note that g(x) is the actual cost to reach node x from the source node, that is, the cost of edge 1->2 plus the cost of edge 2->5:

g(5) = 2 + 3 = 5

And from there g(3) and g(7) will add their edge costs to g(5). Hopefully you see how this is going now and can complete the path.

Edit:

There is some confusion about he example in A* Search Algorithm. I'll try to translate between the notation used there and what I've used.

Take as an example the decision to be made in the other question where we have chosen the path from S to A. We must either continue the path to node X or Y. They show:

{S,A,X} f = (1+4)+5=10
{S,A,Y} f = (1+7)+8=16

In the notation that I've been using, this is equivalent to:

f(X) = (1+4)+5=10, where g(X) = (1+4) and h(X) = 5
f(Y) = (1+7)+8=16, where g(Y) = (1+7) and h(Y) = 8

As you can see in both cases, when you are trying to decide what node to select next (X or Y), you have to add the actual cost of reaching that node, g(x), to the estimated cost of going from that node to the goal, h(x).