English subtitles

← 02-31 A Search 4

Unit 2, Topic 27, A-Star Fifth Question

Get Embed Code
19 Languages

Showing Revision 1 created 11/28/2012 by Amara Bot.

  1. So let's expand the node at Pitesti.
  2. We have to go down this direction, up,
  3. then we reach a path we've seen before,
  4. and we go in this direction.
  5. Now we reach Bucharest, which is the goal,
  6. and the h value is going to be 0
  7. because we're at the goal, and the g value works out to 418.
  8. Again, we don't stop here just because we put a path onto the front tier,
  9. we put it there, we don't apply the goal test next,
  10. but, now we go back to the front tier,
  11. and it turns out that this 418 is the lowest-cost path on the front tier.
  12. So now we pull it off, do the goal test,
  13. and now we found our path to the goal,
  14. and it is, in fact, the shortest possible path.
  15. In this case, A-star was able to find the lowest-cost path.
  16. Now the question that you'll have to think about,
  17. because we haven't explained it yet,
  18. is whether A-star will always do this.
  19. Answer yes if you think A-star will always find the shortest cost path,
  20. or answer no if you think it depends on the particular problem given,
  21. or answer no if you think it depends on the particular heuristic estimate function, h.