.ZIP

# CS 170 Algorithms Final Project

Problem Description Remember the traveling salesman path problem (TSP)? You are given a graph with edge weights, and you are asked to find the best TSP path, that is, overall cheapest route that visits all cities exactly once. (Unlike a tour, a TSP path doesn’t have to return to its start city). In the non-partisan travelling senator problem (NPTSP), each city also has a color, either RED or BLUE, and the path cannot visit more than three cities of the same color consecutively. You still want the cheapest such path that visits every city exactly once. More specifically, you are given a complete, undirected, weighted graph on N cities. The cities are labeled from 1 to N. The graph is given to you in adjacency matrix format, that is you will recieve an N ×N matrix, where the entry in the ith row and jth column represents the edge weight between city i and city j. You are also given a string of length N representing the colors of the cities. The ith character of the string is R if the city is red, and B otherwise. You may also assume that the number of red and blue cities are exactly the same. Constraints • The number of vertices will be an even integer between 1 and 50, inclusive. • The edge weights will be an integer between 0 and 100, inclusive. Submission instructions
Phase 1 (Input files and coding.) Due 05/01 6pm Generate three hard instances of NPTSP. Make sure to follow the input format exactly, or your file will be discarded. The input format is described in the following section. Don’t forget to start coding during this phase. You will submit your instance files through glookup. In your submission, include your three files, labeled TEAMNAME1.in, TEAMNAME2.in, TEAMNAME3.in. Also, include a README file where the first line is your team name, and the following up to 4 lines are the student ids of people in your group.