Assignment based on factor-2 approximation algorithm for metric-TSP.

视频信息

答案文本 复制

视频字幕 复制

The Traveling Salesman Problem asks: given a set of cities, what is the shortest route that visits each city exactly once and returns to the starting point? For Metric-TSP, distances satisfy the triangle inequality, meaning the direct path between two cities is never longer than going through an intermediate city. The factor-2 approximation algorithm provides an efficient solution that guarantees the tour length is at most twice the optimal. The first step of our factor-2 approximation algorithm is to construct a Minimum Spanning Tree from the complete graph of cities. The MST connects all vertices using the minimum total edge weight, creating a tree structure with no cycles. This MST provides a crucial lower bound: its total weight is always less than or equal to the optimal TSP tour cost, since removing any edge from the optimal tour gives us a spanning tree. In step two, we perform a Depth-First Search traversal of our MST. Starting from vertex A, we traverse to D, then to C, then to B. Since B is a leaf, we backtrack to C, then to D, then to E, and finally back to A. This creates a walk that visits every edge of the MST exactly twice - once in each direction. The total length of this walk is exactly twice the MST cost, which gives us an upper bound for our approximation. In the final step, we create our approximation tour by short-circuiting the DFS walk. Instead of following the complete walk A-D-C-B-C-D-E-A, we skip repeated vertices to get A-D-C-B-E-A. The key insight is the triangle inequality: going directly from B to E is never longer than the path B-C-D-E. This short-circuiting process ensures our final tour has cost at most twice the MST cost, which is at most twice the optimal TSP cost. Let's analyze why this algorithm guarantees a factor-2 approximation. First, the MST cost is always less than or equal to the optimal TSP cost, since removing any edge from the optimal tour gives us a spanning tree. Second, our DFS walk visits every MST edge exactly twice, so its cost is exactly twice the MST cost. Third, short-circuiting never increases the total cost due to the triangle inequality. Therefore, our final tour cost is at most twice the optimal cost. The algorithm runs in O(n²) time and space, making it efficient and practical for real-world applications.