TSP with Message Passing

You will use MPI to simulate a parallel programming environment with n processors, where n is equal to the number of cities. Prior to the algorithm, the distances will be read by the processors. Once the algorithm starts, there will be no distribution of distances. You will decide on a suitable representation of the distances. Your program will work within a fixed time limit. This time limit is actually the second number you read from the input file, and it will be interpreted as seconds to finish. That means, if we write 30 to the second line, your algorithm will output a result in 30 seconds at most. Each processor, when it starts execution, will look for a solution to the problem. You can implement any heuristic for this purpose, in fact part of the project is that you should do some research into the TSP literature to determine a good heuristic. Make sure that the heuristic depends on the processor, so that not all the processors start exploring the same solutions. (Here is one heuristic that you can use as a baseline: Heuristic 1: Start with your city, add the closest city, and continue adding closest cities. Then try to optimize by interchanging the order of cities. This heuristic will probably not take you very far. Work on your own, and produce clever methods. We will reward original ideas.) When the deadline approaches, all the processors will send their best solutions obtained so far to the first processor, which is responsible for nicely displaying the solution to us. You can simply assume that the network of processors is fully connected. ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables): a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment. b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request. 3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement). ## Platform Windows XP Microsoft Visual Studio