Consider the A* search problem shown here. The path cost g(x) is the actual dist

Question

Consider the A* search problem shown here. The path cost g(x) is the actual distance from the start state S to an intermediate state, while the heuristic h(x) is the estimated distance from an intermediate state to the goal state G. Answer the given questions. 2 points each, total 10 points] Distance (S A)-10 Distance (S ? B) = 5 Distance (S C)-8 Distance (S D)-7 Distance (SG) 25 Estimate (A ? G)-11 Estimate (B-G) 14 Estimate (09 G) = 12 Estimate (D -> G)- 15 Estimate (GG) [Obvious] 6. The function f(x) used to trace the path from start to goal in A* is a) f(x)-g(x)+h(x) cfx)hx)-gx None of these b) f(x)-g(x)-h(x) 7. Calculate f(x) for x = C: thus f (C) is: b) 20 d) 12 8. For all the intermediate states above, which state has the greatest value of f(x)? a) State A b) State B c) State C d) State D 9. Which state would A* go to, in this example, immediately after the start state? b) State B a) State A 10. If the heuristic is an underestimate, is A* complete and / or optimal? a) Only Complete c) State C d) State D b) Only Optimalc) d) Neither

Explanation / Answer

Hello Student!

I am happy to help you.

6) G(x) is a function to trace the path from start to goal A* is :

Now, to compute the cost from start to intermediate node is g(x)

To compute the cost from intermediate to goal node is h(x)

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

a) will be the answer.

Now, coming over to 7.

7. Calculate f(x) for x = C

f(x) = g(x) + h(x) = 8+12 = 20

b) will be the answer.

8. The greatest value.

For A, f(x) = g(x) + h(x) = 10 + 11 = 21

For B, f(x) = g(x) + h(x) = 5 + 14 = 19

For C, f(x) = g(x) + h(x) = 8 + 12 = 20

For D, f(x) = g(x) + h(x) = 7 + 15 = 22

For G, f(x) = g(x) + h(x) = 25 + 0 = 25

If we go through G then the cost will be maximum i.e. 25

But, G is not an intermediate state. We cannot choose G. If we don't count G then the maximum is state D.

d) will be the answer.

9. Which state should we go?

We must go to that intermediate state whose cost is least. Therefore, we will choose state B.

b) will be the answer.

10. If h(x) is underestimate, is A* complete or optimal?

A* is optimal even if the heuristic cost is underestimated. If it underestimates the costs by a bit maybe some of the routes will turn out to be useful. A* algorithm is complete and will always find a solution if the heuristic cost > e > 0 for a fixed value of e.

c) is the answer.

Thank you. Feel free to ask anything. If you like the answer. Please upvote it. It means a lot. Thank you again.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.