CS 325 HW 7: The Travelling Salesman Problem
In this assignment you will have fun trying out ideas to solve a very hard problem: The Traveling
Salesman Problem (TSP).
You are given a set of n cities and for each pair of cities c1 and c2, the distances between them d(c1, c2).
Your goal is to find an ordering (called a tour) of the cities so that the distance you travel is minimized.
The distance you travel is the sum of the distances from the first city in the ordering to the second city,
plus the distance second city to the third city, and so on until you reach the last city, and then adding
the distance from the last city to the first city. For example if the cities are Seattle, Portland, Corvallis
and Boise. The total distance traveled visiting the cities in this order is:
d(tour) = d(Seattle,Portland) + d(Portland, Corvallis) + d(Corvallis,Boise) + d(Boise, Seattle)
In this project, you will only need to consider the special case where the cities are locations in a 2D grid
(given by their x and y coordinates) and the distance between two cities c1 = (x1, y1) and c2 = (x2, y2) is
given by their Euclidean distance. To avoid floating point precision problems in computing the
squareroot, we will always round the distance to the nearest integer. In other words you will compute
the distance between cities c1 and c2 as:
(𝑐1, 𝑐2) = nearestint (√(𝑥1 − 𝑥2)
2 + (𝑦1 − 𝑦2)
For example, if the three cities are given by the coordinates c1= (0, 0), c2 = (1, 3), c3 = (6, 0), then a tour
that visits the cities in order c1 –> c2 –> c3 – >c1 has the distance .
You will research and implement an algorithm for finding an approximate solution for the TSP problem.
You should provide pseudocode for the algorithm that is implemented and give the running time.
There is much literature on methods to “solve” TSP please cite any sources you use. TSP is not a
problem for which you will be able to easily find optimal solutions. Your goal is to find an approximate
solution or the “best solution” you can find in a reasonable amount of time. One possible algorithm
would perform a depth-first traversal on a MST for a Euclidean graph.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx