This project is to combine all of the materials that you have seen so far in lab. It will also be a more design oriented project, rather than a coding project. What this means is that the design of the project is going to make it substantially easier (or harder) to actually code.
In this project, you are forbidden to use lists. Otherwise, anything else you have learned is legal. This project will be a solo project, meaning that you will be working alone. While discussion is encouraged, direct collaboration will be considered cheating and penalized.
In this project, you will be working to write a solution to a variant of the Traveling Salesman problem. (to be rigorous, the real problem requires a cycle, we shall be doing a path.)
The traveling salesman problem is described as this: A salesman wants to reach all of the cities in an area. Cities are connected by roads and have certain distances away from each other. He wants to create a path such that he is able to visit all of the cities in the shortest distance without repeatedly visiting any cities. For more information on the problem itself, visit Wikipedia .
In our project cities will be represented as words in a sentence. Distances between cities shall be
represented with a word containing the 2 cities and the distance connected with hyphens. You may assume
that all connections go both ways (LA to NV implies that you can also go NV to LA). Note: City names
will NOT always be 2 letters long. Here is an example map:
The sentence of cities will be represented as: (LA NY NV SF) while the sentence of
distances will be represented as: (LA-NY-1000 LA-NV-50 LA-SF-150 NV-NY-200 SF-NY-300) .
Note that all cities do not have to be connected. Also, the sentence representation can be of any order. This
means that '(SF NY NV LA) is another valid representation of the same map. Likewise
'(NV-LA-50 LA-NY-1000 NY-NV-200 SF-LA-150 SF-NY-300) is another valid representation
of distance between the cities. Note that in this version, not only are the order of the distances switched,
the order of the cities in the words are switched as well.
You will write a function called travel-salesman that takes in a starting city, a sentence of all cities and another sentence of distances. This will return a number which is the shortest path in which the salesman can visit all the cities without repeatedly visiting a city. In our example graph, we would do: (travel-salesman 'LA '(SF NY NV LA) '(NV-LA-50 LA-NY-1000 NY-NV-200 SF-LA-150 SF-NY-300)). This would in turn return 550, as this is the shortest path he can take. You do not have to return the actual path, just the distance. There can be any arbitrary number of cities and connections that exist. However, you may assume that a path to all cities will always exist.
The design of the project plays a large part in the success of the overall project in general. Before coding, you definitely want to have a plan in action of how you are going to code the solution. As far as the solution itself goes, you will probably have to brute force the solution, meaning you will have to create all possible paths that someone can take and then take the minimum over all of them. While this may sound easy, it may not be as straightforward as it sounds. It may be helpful to think about the solution in 1 of 2 ways:
You may use anything you have previously learned in this class. This includes recursion, HOF's, lambda and anything else. You may not use lists on this project nor any list procedures..
This project is due one week from now, on August 2, 11:59 pm. You have 3 slip days total between all projects but use them wisely. To submit the project type "submit mp3" from unix. The filename should be called mp3.scm. Along with the file itself, you should include a test file, called mp3-tests.scm. This should be in the same format that you used in projects 1 & 2 (using the add-test-case framework).
For an automatic A in the class, solve the original traveling salesman project with an algorithm that runs in polynomial time. If you would like to learn more about complexity and running time of algorithms go here. Name your solution extra-credit.scm and include it with your submission. Include a proof of why your algorithm is polynomial time with the submission.