Blog Archives

Tour the T (ITA Archived Puzzle, Analyzed)

9/2/2011

Please refer to the Tour the T problem on this page.

Analysis

This is an instance of the Traveling Salesman Problem. We can model the entire subway as a weighted graph G=(V,E) where V is a station and E is an edge that connects two stations and w is the weight of the edge that represents the travel time between the two stations.

Algorithm

Build the weighted graph of the subway, while collecting those stations that are hubs connecting multiple lines. For example, Park St is a hub.
Now find the minimum spanning tree and do a depth first traversal of the tree.
Find the shortest path between the successive vertices sorted in depth first order. This will build a route that traverses all the stations at least once.
Now on the route, find out the hubs where line has been changed and add the waiting time for such line changes.
If your start station is not Kendall square, then find the shortest route between the penultimate station on the route and Kendall square, to build the final route.

0 Comments

Word Rectangle (ITA Archived Puzzle, Archived)

Tour the T (ITA Archived Puzzle, Analyzed)

Analysis

Algorithm

Me

Archives

Categories

Word Rectangle (ITA Archived Puzzle, Archived)

Tour the T (ITA Archived Puzzle, Analyzed)

Analysis

Algorithm

﻿Me﻿

Archives

Categories

Me