Return to Video

22x-06 Tour Processing

  • 0:00 - 0:04
    Now we've seen how useful preprocessing can be for a variety of problems.
  • 0:04 - 0:08
    So, let's look at some possible preprocessing rules
  • 0:08 - 0:10
    that we could use for the shortest tour problem.
  • 0:10 - 0:14
    Now what I'd like you to tell me about each of the preprocessing rules
  • 0:14 - 0:16
    is whether they are correct;
  • 0:16 - 0:19
    that is, they don't change the solution outcome to something different
  • 0:19 - 0:22
    than they would be if you didn't apply the rule,
  • 0:22 - 0:27
    and are they effective, meaning they don't increase the size of the input
  • 0:27 - 0:29
    and actually make your job harder.
  • 0:29 - 0:32
    So the first possibility is that we could calculate the shortest path
  • 0:32 - 0:35
    from each vertex to each other vertex,
  • 0:35 - 0:37
    and then we remove all of the unused edges.
  • 0:37 - 0:40
    The second possibility is that, as long as the graph stays connected,
  • 0:40 - 0:45
    we could just remove the heaviest edges and repeat until the graph disconnects
  • 0:45 - 0:47
    and don't remove that one.
  • 0:47 - 0:51
    The third possibility is remove any edge that has a larger weight
  • 0:51 - 0:54
    than the minimum spanning tree's weight.
  • 0:54 - 1:00
    Finally, we could replace long paths by a single edge that has equal weight.
  • 1:00 - 1:03
    So, go ahead and check which ones you think are correct
  • 1:03 -
    and which rules you think are also effective.
タイトル:
22x-06 Tour Processing
Team:
Udacity
プロジェクト:
CS313 - Theoretical Computer Science
Duration:
01:07
Amara Bot added a translation

English subtitles

改訂