English subtitles

← Breadth First without Recursion - Intro to Algorithms

Get Embed Code
3 Languages

Showing Revision 3 created 05/24/2016 by Udacity Robot.

  1. So, we're going to change this to breadth first search, but we're going to do it really easily,
  2. at least for the people version, by grabbing the first element off the open list
  3. instead of the last element off the open list.
  4. Let's take a look at how that changes things.
  5. We start off with d as the first thing added to the list and d on the open list, and now
  6. what we do is, well the first and the last element are the same, so nothing changed yet.
  7. We grab d off, we mark any unmarked neighbors of that node of d,
  8. which in this case are e and c just as before and that's done for this time through.
  9. And now, we go back up to the top and things get a little different.
  10. This time, well, actually not that different, the order was sort of
  11. arbitrary and so first and last are sort of arbitrary.
  12. We're going to grab the first thing off the list just like the instruction say and that's e,
  13. add its neighbors in, they still get added to the end of the list, so that's a little different in terms
  14. of the numbering so far, but now it's where we go back up to the top and we grab the first
  15. element of the list in which this case is c, so we're alternating.
  16. Instead of continuing in one direction, we're actually expanding outward from d,
  17. with the d and then c and e, and then b and f.
  18. And now, what happens next if we expand from f with expanded g, add it to the open list,
  19. but now, before we touch g, we're always pulling off the front of the list now, we get to b.
  20. Right now, we've visited everything.
  21. The next thing we pull off is g, we notice that it has no open neighbors, then we pull off a,
  22. we notice that it has no open neighbors, and the open list is empty, the search is finish.
  23. You can see what happens in this case is we expanded out from d and now a and g,
  24. well the sum of the a and g are 13 instead of 12, which is not a really significant or
  25. meaningful difference at this point but it is indicating that the search is proceeding differently
  26. and the way it's proceeding importantly is out from the center.
  27. All the paths that it found, all the edges that it expanded
  28. in new shortest distances it was away from the beginning state.
  29. So, this is going to give us what we need to actually find shortest paths.