Quote:The Travelling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science. It is focused on optimization. In this context better solution often means a solution that is cheaper. The travelling salesman’s problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one (eg home town) and returning to the same city. The challenge of the problem is that the travelling salesman wants to minimize the total length of the trip. For example, the distance between each city is given – From town A to town B, the distance is 20km – From town B to town C, the distance is 30km – From town C to town D, the distance is 12km etc. The objective to minimize the distance travelled by the salesman from town 1 (his home town) to all the other town and back home. You are expected to write a program, that (i) Allows the user to enter the number of cities and generate the positions randomly on a Cartesian plane. The Cartesian plane, named after the mathematician Rene Descartes, is a plane with a rectangular coordinate system that associates each point in the plane with a pair of numbers. Cartesian coordinates can be used to pinpoint where you are on a map or graph. Using Cartesian Coordinates we mark a point on a graph by how far along and how far up it is. Example: Point (2,3) is 2 units across (in the x direction), and 3 units up (in the y direction) So (2,3) means: Go along 2 and then go up 3 then "plot the dot". [10 marks] (i) Calculate the distance between each city [should be stored in a 2-D array] Distance between any two points is given by finding the square root of [ (x1 – x2)2 + (y1 – y2)2] [15 marks] (ii) Calculate the optimal (the shortest) route that the salesman should travel from his hometown (position (0,0) on the Cartesian plane) – to all the cities and back to his hometown.
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)