Massive Algorithms: Travelling Salesman Problem

Travelling Salesman Problem

The hitch is that the number of possible routes that visit n locations is enormous: n!. Why? The truck starts at the depot. From there, any of the other n locations can be the first stop. From the first stop, any of the remaining n 1 locations can be the second stop, and so there are n *(n -1)/ possible combinations for the first two stops, in order.

n! grows faster than an exponential function; it’s superexponential.
Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming) - GeeksforGeeks
Travelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Note the difference between Hamiltonian Cycle and TSP. The Hamiltoninan cycle problem is to find if there exist a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.

If size of S is 2, then S must be {1, i},
 C(S, i) = dist(1, i) 
Else if size of S is greater than 2.
 C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

There are at most O(n*2ⁿ) subproblems, and each one takes linear time to solve. The total running time is therefore O(n²*2ⁿ). The time complexity is much less than O(n!), but still exponential. Space required is also exponential. So this approach is also infeasible even for slightly higher number of vertices.

Naive Solution:
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.

Time Complexity: Ω(n!)

https://github.com/williamfiset/Algorithms/blob/master/com/williamfiset/algorithms/graphtheory/TspDynamicProgrammingRecursive.java

  private final int N;
  private final int START_NODE;
  private final int FINISHED_STATE;

  private double[][] distance;
  private double minTourCost = Double.POSITIVE_INFINITY;

  private List<Integer> tour = new ArrayList<>();
  private boolean ranSolver = false;

  public TspDynamicProgrammingRecursive(double[][] distance) {
    this(0, distance);
  }

  public TspDynamicProgrammingRecursive(int startNode, double[][] distance) {
    
    this.distance = distance;
    N = distance.length;
    START_NODE = startNode;
    
    // Validate inputs.
    if (N <= 2) throw new IllegalStateException("TSP on 0, 1 or 2 nodes doesn't make sense.");
    if (N != distance[0].length) throw new IllegalArgumentException("Matrix must be square (N x N)");
    if (START_NODE < 0 || START_NODE >= N) throw new IllegalArgumentException("Starting node must be: 0 <= startNode < N");
    if (N > 32) throw new IllegalArgumentException("Matrix too large! A matrix that size for the DP TSP problem with a time complexity of" +
                                                   "O(n^2*2^n) requires way too much computation for any modern home computer to handle");

    // The finished state is when the finished state mask has all bits are set to
    // one (meaning all the nodes have been visited).
    FINISHED_STATE = (1 << N) - 1;
  }

  // Returns the optimal tour for the traveling salesman problem.
  public List<Integer> getTour() {
    if (!ranSolver) solve();
    return tour;
  }

  // Returns the minimal tour cost.
  public double getTourCost() {
    if (!ranSolver) solve();
    return minTourCost;
  }

  public void solve() {

    // Run the solver    
    int state = 1 << START_NODE;
    Double[][] memo = new Double[N][1 << N];
    Integer[][] prev = new Integer[N][1 << N];
    minTourCost = tsp(START_NODE, state, memo, prev);
    
    // Regenerate path
    int index = START_NODE;
    while (true) {
      tour.add(index);
      Integer nextIndex = prev[index][state];
      if (nextIndex == null) break;
      int nextState = state | (1 << nextIndex);
      state = nextState;
      index = nextIndex;
    }
    tour.add(START_NODE);
    ranSolver = true;
  }

  private double tsp(int i, int state, Double[][] memo, Integer[][] prev) {
    
    // Done this tour. Return cost of going back to start node.
    if (state == FINISHED_STATE) return distance[i][START_NODE];
    
    // Return cached answer if already computed.
    if (memo[i][state] != null) return memo[i][state];
    
    double minCost = Double.POSITIVE_INFINITY;
    int index = -1;
    for (int next = 0; next < N; next++) {
      
      // Skip if the next node has already been visited.
      if ((state & (1 << next)) != 0) continue;
      
      int nextState = state | (1 << next);
      double newCost = distance[i][next] + tsp(next, nextState, memo, prev);
      if (newCost < minCost) {
        minCost = newCost;
        index = next;
      }
    }
    
    prev[i][state] = index;
    return memo[i][state] = minCost;
  }

https://algorithmcafe.wordpress.com/category/uva/problem-solving-paradigms/dynamic-programming/traveling-salesman-problem-tsp/
http://www.bubuko.com/infodetail-681303.html

Nearest neighbour algorithm - greedy
https://en.wikipedia.org/wiki/Nearest_neighbour_algorithm

start on an arbitrary vertex as current vertex.
find out the shortest edge connecting current vertex and an unvisited vertex V.
set current vertex to V.
mark V as visited.
if all the vertices in domain are visited, then terminate.
Go to step 2.

Brute force:
https://gist.github.com/westphahl/432876
routes = []

def find_paths(node, cities, path, distance):
# Add way point
path.append(node)

# Calculate path length from current to last node
if len(path) > 1:
distance += cities[path[-2]][node]

# If path contains all cities and is not a dead end,
# add path from last to first city and return.
if (len(cities) == len(path)) and (cities[path[-1]].has_key(path[0])):
global routes
path.append(path[0])
distance += cities[path[-2]][path[0]]
print path, distance
routes.append([distance, path])
return

# Fork paths for all possible cities not yet used
for city in cities:
if (city not in path) and (cities[city].has_key(node)):
find_paths(city, dict(cities), list(path), distance)

if __name__ == '__main__':
cities = {
'RV': {'S': 195, 'UL': 86, 'M': 178, 'BA': 180, 'Z': 91},
'UL': {'RV': 86, 'S': 107, 'N': 171, 'M': 123},
'M': {'RV': 178, 'UL': 123, 'N': 170},
'S': {'RV': 195, 'UL': 107, 'N': 210, 'F': 210, 'MA': 135, 'KA': 64},
'N': {'S': 210, 'UL': 171, 'M': 170, 'MA': 230, 'F': 230},
'F': {'N': 230, 'S': 210, 'MA': 85},
'MA': {'F': 85, 'N': 230, 'S': 135, 'KA': 67},
'KA': {'MA': 67, 'S': 64, 'BA': 191},
'BA': {'KA': 191, 'RV': 180, 'Z': 85, 'BE': 91},
'BE': {'BA': 91, 'Z': 120},
'Z': {'BA': 120, 'BE': 85, 'RV': 91}
}

print "Start: RAVENSBURG"
find_paths('RV', cities, [], 0)
print "\n"
routes.sort()
if len(routes) != 0:
print "Shortest route: %s" % routes[0]
else:
print "FAIL!"
https://code.google.com/p/travelling-salesman/source/browse/trunk/HM/src/org/hm/backtracking/Backtracking.java?r=4
https://github.com/Bjoern/Traveling-Salesman/blob/master/src/net/blinker/tsm/TravelingSalesmanBruteForce.java

DP:
https://sites.google.com/site/indy256/algo/dynamic_tsp

http://www.sanfoundry.com/java-program-implement-traveling-salesman-problem-using-nearest-neighbour-algorithm/
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that there are much better tours. Another check is to use an algorithm such as the lower bound algorithm to estimate if this tour is good enough.

In the worst case, the algorithm results in a tour that is much longer than the optimal tour. To be precise, for every constant r there is an instance of the traveling salesman problem such that the length of the tour computed by the nearest neighbour algorithm is greater than r times the length of the optimal tour. Moreover, for each number of cities there is an assignment of distances between the cities for which the nearest neighbor heuristic produces the unique worst possible tour.^[1]

The nearest neighbour algorithm may not find a feasible tour at all, even when one exists.

```
public class TSPNearestNeighbour
```
```
{
```
```
    private int numberOfNodes;
```
```
    private Stack<Integer> stack;
```
```
 
```
```
    public TSPNearestNeighbour()
```
```
    {
```
```
        stack = new Stack<Integer>();
```
```
    }
```
```
 
```

    public void tsp(int adjacencyMatrix[][])

```
    {
```

        numberOfNodes = adjacencyMatrix[1].length - 1;

        int[] visited = new int[numberOfNodes + 1];

```
        visited[1] = 1;
```
```
        stack.push(1);
```
```
        int element, dst = 0, i;
```
```
        int min = Integer.MAX_VALUE;
```
```
        boolean minFlag = false;
```
```
        System.out.print(1 + "\t");
```
```
 
```
```
        while (!stack.isEmpty())
```
```
        {
```
```
            element = stack.peek();
```
```
            i = 1;
```
```
            min = Integer.MAX_VALUE;
```
```
            while (i <= numberOfNodes)
```
```
            {
```

                if (adjacencyMatrix[element][i] > 1 && visited[i] == 0)

```
                {
```

                    if (min > adjacencyMatrix[element][i])

```
                    {
```

                        min = adjacencyMatrix[element][i];

```
                        dst = i;
```
```
                        minFlag = true;
```
```
                    }
```
```
                }
```
```
                i++;
```
```
            }
```
```
            if (minFlag)
```
```
            {
```
```
                visited[dst] = 1;
```
```
                stack.push(dst);
```

                System.out.print(dst + "\t");

```
                minFlag = false;
```
```
                continue;
```
```
            }
```
```
            stack.pop();
```
```
        }
```
```
    }
```
```
 
```

    public static void main(String... arg)

```
    {
```
```
        int number_of_nodes;
```
```
        Scanner scanner = null;
```
```
        try
```
```
        {
```

            System.out.println("Enter the number of nodes in the graph");

            scanner = new Scanner(System.in);

            number_of_nodes = scanner.nextInt();

            int adjacency_matrix[][] = new int[number_of_nodes + 1][number_of_nodes + 1];

            System.out.println("Enter the adjacency matrix");

            for (int i = 1; i <= number_of_nodes; i++)

```
            {
```

                for (int j = 1; j <= number_of_nodes; j++)

```
                {
```

                    adjacency_matrix[i][j] = scanner.nextInt();

```
                }
```
```
            }
```

            for (int i = 1; i <= number_of_nodes; i++)

```
            {
```

                for (int j = 1; j <= number_of_nodes; j++)

```
                {
```

                    if (adjacency_matrix[i][j] == 1 && adjacency_matrix[j][i] == 0)

```
                    {
```

                        adjacency_matrix[j][i] = 1;

```
                    }
```
```
                }
```
```
            }
```

            System.out.println("the citys are visited as follows");

            TSPNearestNeighbour tspNearestNeighbour = new TSPNearestNeighbour();

            tspNearestNeighbour.tsp(adjacency_matrix);

        } catch (InputMismatchException inputMismatch)

```
         {
```

             System.out.println("Wrong Input format");

```
         }
```
```
        scanner.close();
```
```
    }
```
```
}
```

Read full article from Travelling Salesman Problem | Set 1 (Naive and Dynamic Programming) - GeeksforGeeks

Travelling Salesman Problem

Labels

Popular Posts