CS: Traveling

CS: Traveling

You and your family are planning a road trip through all of the capitals in the region and you have the job of figuring out the shortest route possible to save on the cost of fuel.

Try running one of the sample road trips by selecting Latitude, Longitude, or Random from the drop-down menu. After seeing the results, try switching to Draggable and refine the city order to one you think works best.

Now that you have had a chance to test out a few options, think about how would you explain the route you suggest your family to take? Will you provide a list of cities or is there a guiding principle like start at the west and follow it to the east?

Here are some questions to consider:

  1. Does it matter which city you start from?

  2. Would the strategy you used to develop your route (longitudinal, latitudinal, etc) apply to any country or does it depend? Try switching to another country and see if it works as well there.

  3. What are some of the reasons this problem is difficult?

This type of problem is traditionally known as the traveling salesperson problem, where the challenge is to go through each city only once and return to the city of orgin. Even though this type of problem has not been optimally solved by the community, the act of investigating the problem and developing algorithms to try and solve it (even if in a suboptimal way) has been used to improve the efficiency of many other related problems. Route planning and searching through data, like DNA and web pages, are two similar types of problems.

If you want to explore this topic further, search the Internet for: traveling salesperson problem, NP problem. Potential standards this activity could align with if used with students.