English 字幕

← 15-07 Algorithm For Shortest Tour



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

  1. Enough with introducing new words to you.
  2. What is the algorithm that I propose that Dave should use?
  3. It's a very simple one actually.
  4. The algorithm is now quite simple to describe.
  5. Of course it takes a bit more effort to actually implement it.
  6. Given any graph, the first step that we do is we calculate
  7. a minimum spanning tree for that graph.
  8. That is something if you have had an algorithms class you know to be doable in polynomial time.
  9. That can be done in O(n²) time for an in vertext graph.
  10. Then you take a walk along the tree, and you can guess that
  11. that can be done in polynomial time as well.
  12. The running time of this alogirthm here in total---so it's a polynomial time algorithm.
  13. Now where I probably need to convince you is that this is actually
  14. a good approximation algorithm, because it sounds so simple again doesn't it?
  15. My claim now is, as I've written here, that this is an approximation algorithm for shortest tour.
  16. Actually it's a constant factor approximation algorithm for that problem.
  17. So how come?
  18. Well, since you already saw one constant factor approximation algorithm,
  19. I am actually going to let you figure this out.
  20. Let's start out by taking 2 numbers and comparing them.
  21. The first number is the weight of the minimum spanning tree,
  22. and by weight I simply mean if you take the sum over all edges that are in the spanning tree,
  23. that's what I will call the weight of the spanning tree.
  24. The second one is going to be the length of the shortest tour for the network.
  25. Now first of all I would like you to tell me what you can say about these 2 numbers.
  26. How do they compare?
  27. Is the weight of the tree smaller than the length of the shortest tour?
  28. Is it smaller than or equal to the length of the shortest tour?
  29. Are both the same value?
  30. Or is the weight of the tree larger than or equal to the length of the shortest tour?
  31. Or is it always larger than the length of the shortest tour?
  32. Please select which one is correct here.