English subtitles

← 15-01 Dave's Problem

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. So Alice is now super, super happy, but what about the others?
  2. So I suggest that we take a look at Dave here,
  3. and Dave, as you remember, was working on a logistics problem,
  4. so what he was trying to solve was shortest tour.
  5. And actually, last time we left off,
  6. Dave wasn't too happy,
  7. because we found out it is not very easy to find
  8. a good search tree or a pre processing strategy
  9. for his problem.
  10. On the other hand, of course, we mentioned that in practice
  11. shortest tour is usually very easy to solve,
  12. but from a theoretical perspective,
  13. maybe we were a bit lucky for Dave;
  14. if we're not looking for the best possible solution,
  15. but except an approximation,
  16. and then if we should find an approximation,
  17. Dave can get a little happier here
  18. and of course he doesn't have to be as jealous that
  19. Alice has such an NP complete problem
  20. and he seems to have a harder one.
  21. Now lucky for Dave,
  22. there is a constant factor approximation algorithm
  23. for shortest tour,
  24. but since Dave is not that proficient in theoretical computer science,
  25. I think he doesn't really stand a chance
  26. of coming up with this algorithm himself,
  27. so you will have to pay close attention now
  28. to be able to explain it to Dave.
  29. The concept that we will use is that of a
  30. spanning tree, and if you've had an algorithm course before,
  31. you will know what a spanning tree is,
  32. but I'm quickly going to explain it to you just to make sure.
  33. A spanning tree is a part of a graph
  34. or actually it's a selection of edges
  35. in a graph so that the result looks
  36. like a tree.
  37. Well, what that means is that you select edges
  38. so that you still keep the whole graph connected,
  39. but you don't have any cycles,
  40. so a cycle would be something like this
  41. where you can leave a vertex and then come back to it
  42. another way, so you select edges
  43. so that the whole graph is still connected,
  44. but there can be no cycles, so
  45. to have you figure it out, let's do a quick quiz here.
  46. This is the thing that worked 3 times.
  47. I'm going to give you 3 choices of what a spanning tree could be,
  48. and the red edges are always those that
  49. I'm selecting here.
  50. I would like you to tell me in which of these cases
  51. the red edges from a spanning tree for the graph.