Posted: November 3rd, 2015

Computer

Computer

use a dynamic programming (DP) solution to solve the individual TSP subproblems.
Generate a set of points (x,y pairs); come up with the distances between the points and create a distance matrix. Use a distance threshold (user input) to decide whether the edge will be present or not i.e if distance between any two points is greater than the threshold there is no edge between them make the distance infinity. This generates the adjacency matrix for your undirected graph.

Serial TSP
The traveling salesman problem A traveling salesman is getting ready for a big sales tour. Starting at his hometown, suitcase in hand, he will conduct a journey in which each of his target cities is visited exactly once before he returns home. Given the pairwise distances between cities, what is the best order in which to visit them, so as to minimize the overall distance traveled?

Denote the cities by 1,…,n, the salesman’s hometown being 1, and let D = (dij) be the matrix of intercity distances. The goal is to design a tour that starts and ends at 1, includes all other cities exactly once, and has minimum total length. The figure below shows an example involving five cities.
Let’s dive right into the DP. So what is the appropriate sub-problem for the TSP? In this case the most obvious partial solution is the initial portion of a tour. Suppose we have started at city 1 as
required, have visited a few cities, and are now in city j. What information do we need in order to extend this partial tour? We certainly need to know j, since this will determine which cities are most convenient to visit next. And we also need to know all the cities visited so far, so that we don’t repeat any of them. Here, then, is an appropriate sub-problem.

For a subset of cities S ? {1,2,…,n} that includes 1, and j ? S, let C(S,j) be the length of the shortest path visiting each node in S exactly once, starting at 1 and ending at j.
When |S| > 1, we define C(S, 1) = 8 since the path cannot both start and end at 1.
Now, let’s express C(S,j) in terms of smaller sub-problems. We need to start at 1 and end at j; what should we pick as the second-to-last city? It has to be some i ? S, so the overall path length is the distance from 1 to i, namely, C(S – {j}, i), plus the length of the final edge, dij. We must pick the best such i:
C(S,j)=mini?S;i?jC(S-{j},i)+dij
The sub-problems are ordered by |S|. Here’s the code.

C({1},1) = 0
for s = 2 to n:
for all subsets S ? {1,2,…,n} of size s and containing 1:
C(S,1) = 8
for all j?S, j?1:
C(S, j) = min{C(S-{j},i)+dij: i?S, i?j}
return minjC({1,…,n},j)+dj1
There are at most 2n.n sub-problems, and each one takes linear time to solve. The total running time is therefore O(n2.2n).

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT 🙂