The-rectilinear-traveling-salesperson-problem

CPSC 335 Project 3: The rectilinear traveling salesperson problem Prof. Doina Bein, CSU Fullerton dbein@fullerton.edu

Introduction In this project you will design, implement, and analyze two algorithms for the same problem, the rectilinear traveling salesperson problem in Euclidean (2D) space. As you might expect, it is a special case of the classical traveling salesman problem (TSP) where the input is a rectilinear graph. For this problem, you will design two algorithms, describe the algorithms using clear pseudocode, analyze them mathematically, implement your algorithms in C/C++/Java, measure their performance in running time, compare your experimental results with the efficiency class of your algorithms, and draw conclusions. The hypotheses

This experiment will test the following hypotheses:

Exhaustive search algorithms are feasible to implement, and produce correct outputs. Approximation algorithms are reasonably fast and produce reasonably good outputs.

The rectilinear traveling salesperson problem (RTSP) Remember that a coordinate is a number x∈ℜ, and in the plane, a point is a pair (x, y)∈ℜ2. A rectilinear graph is a complete, weighted, undirected graph G=(V,E) where V is a set of points V⊂ℜ2,E is the set of all possible edges between distinct points E=p,q∈V, p≠q{ {p,q} }, And the weight w(p,q) of an edge between p and q is the rectilinear distance (also called Manhattan distance or city-block metric), defined as follows w( (xp,yp), (xq, yq) ) = abs(xp-xq)+abs(yp-yq)

A rectilinear graph is complete, so it may be defined entirely by the points comprising its vertices. There is no need to explicitly store a set of edges, since every pair of distinct vertices is connected, and the weight of such an edge is computed using the rectilinear distance function.

The rectilinear traveling salesperson problem is: input: a positive integer n and a list P of n distinct points representing vertices of a rectilinear graph output: a list of n points from P representing a Hamiltonian cycle of minimum total weight for the graph. We developed an exhaustive search algorithm that solves the TSP problem on general graphs. Its time complexity is O(n⋅n!), which is even slower than factorial, so theory predicts that an implementation of this algorithm will be extremely slow.

Dirac’s theorem states that:

If each vertex of a connected graph with 3 or more vertices is adjacent to at least half of the remaining vertices, then the graph has a Hamilton Circuit. Two vertices are ADJACENT if there is an edge connecting them.

In Euclidean space, every node is connected to the rest of the nodes, so the RTSP problem will always have a solution.

The Exhaustive Optimization Algorithm (EOA)

The exhaustive optimization algorithm will list all possible Hamiltonian cycles (leaving out the exact reversals, if you wish), find the weight of each cycle, and choose the one with the smallest weight.

A Hamiltonian cycle is a Hamiltonian path in which the first vertex is added at the end. Since all vertices are connected in a Euclidean space, once you have a Hamiltonian path one can always obtain the Hamiltonian cycle from it by appending the first vertex.

To generate all possible Hamiltonian paths is equivalent to generating all permutations of vertices. There are several algorithms for generating permutations, including Heap’s algorithm presented in class. It is up to you to choose such an algorithm, provided that it will generate all permutations, so it is not a random permutation algorithm, that generate some random permutations.

Steps of the EOA:

1. Initially the best solution has infinite length (or a very large number). One way of calculating this large number is to calculate the farthest pair of vertices. Let us consider A and B to be such vertices and DIST to be the distance. Then the large number will be N*DIST, where N is the total number of vertices.
2. Generate all permutations. For each permutation, calculate the length of the Hamiltonian cycle generated by the permutation and compare it with the best solution found so far. If a shortest cycle is found, store it as the current best solution. When calculating the length of the Hamiltonian cycle, do not forget to include the edge between the last vertex and the first vertex of the Hamiltonian path.
3. Output the best solution.

EOA always works, given enough time to find the optimal result. But it can only be used for relatively small graphs. For a computer doing 10,000 cycles/second, it would take about 18 seconds to handle 10 vertices, 50 days to handle 15 vertices, 2 years for 16 vertices, 193,000 years for 20 vertices. Unfortunately, the exhaustive optimization algorithm is the ONLY method known that is guaranteed to produce an optimal solution.

Mathematicians have not been able to prove that another such method exists nor have they been able to prove that one doesn’t exist.

This is one of the most important and famous unsolved problems in mathematics.

Improved Nearest Neighbor Algorithm (INNA)

Although we do not have an efficient algorithm for solving ETSP, we do have several algorithms that produce results that may not be optimal. In this respect, we are willing to give up our requirement for an optimal solution in the interest of time and settle for a "good" solution which may not be optimal. We call this class of algorithms approximate algorithms.

For approximate algorithms, we will be interested in a quantity called the relative error.

Relative Error = Difference between the Solution and the Optimal SolutionOptimal Solution

The relative error tells us how close the approximate solution is to the optimal solution. The Relative Error is important but one will be able to calculate the Optimal Solution only for simple cases. A complete discussion of evaluating the performance of an approximate algorithm is beyond the scope of this course. But in summary, two important factors are: (1) worst-case performance and (2) average performance.

A recent result (from 2015) regarding RTSP is available at http://arxiv.org/abs/1512.06649 .

Steps of the INNA:

1. Calculate the farthest pair of vertices. Let us consider A and B to be such vertices.
2. Start at a vertex A.
3. Let us consider a generic node V which is the current node. Starting from node V, travel to the vertex that you haven’t been to yet but is the closest to V. If there is a tie, pick randomly the next vertex.
4. Continue until you travel to all vertices
5. Travel back to your starting vertex A.
6. Output the solution.

The resulting path is a Hamiltonian Cycle.

What you need to do

1. Write clear pseudocode for each algorithm.
2. Analyze your pseudocode mathematically and write its efficiency class using Big-Oh notation. (You need to compute the total number of steps of the algorithm.)
3. Type these notes (electronically or on paper) and submit it as a PDF report.
4. Implement your algorithm in C/C++/Java. You may use the templates provided at the end of this file.
5. Compile and execute the program.
6. Create a file with the output of the program for an input value and submit it together with the program. Note, the output can be redirected to a file (for easy printing). For example, the following command line will create an output file in Linux-based operating system called a1out.txt by re-directing the output from the screen (display) to the file a1out.txt: K:\cpsc335> a.out > a3out.txt