![]() |
Algorithms and Data Structures | ||||
|
The
Travelling Salesman Problem (tsp)
Given a set of locations, each with an x-y coordinate, produce a tour that visits all cities once only, and returns to the starting city. Find this tour such that distance travelled is a minimum. Instances of the tspEuclidean and Manhattan. Single machine scheduling, with setups Control of a x-y drilling machine ...ComplexityFind all permutations. Assume only 4 cities, ABCD then may have to considerABCD, ABDC, ACBD, ACDB, ADBC, ADCB BACD, BADC, BCAD, BCDA, BDAC, BDCA CABD, CADB, .... DABC, DACB, ....There will be 24 to consider. More generally, given n we may have to consider n! to find optimal. The growth of n! is shown below n n! 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800It appears that in order to find the best tour we must consider many different possible solutions, and examine them in turn to decide which is best. That is, we must explore many possibilities. These possibilities can be viewed/considered as a tree, to be explored (or searched, but don't confuse this with earlier definition of search as in searching and sorting!). Decision ProblemThe TSP is often described as a decision problem: Is there a tour of cost less than or equal to k? We can express the optimisation problem as a sequence of decision problems.1. Is there a tour of cost <= k? yes! 2. <= k-1? yes! 3. <= k-2? no! 4. k-1 is the optimal tour length PermutationsThe scheme code below produces all permutations of objects in the list x(define (perm x) (let ((all-perms '())) (define (perm' source sink) ;(display source) (display sink) (newline) (cond ((null? source) (set! all-perms (append all-perms (list sink)))) (t (do ((y' source (cdr y'))) ((null? y')) (let ((e (car y'))) ;You can also see the java equivalent Branch and Bound (BnB)Assume we have a 6 city TSP with cities ABCDEF, and the tours are built up systematically, such that we extend a partial tour as in the above function perm.- Assume that the best solution found so far had a cost of 100 - the current partial tour isThat is, in the process of searching for a solution we can put bounds on what is acceptable. If the current partial tour cannot meet those bounds we can abondon it, thus pruning the search space. The more effort we put into computing a lower bound the more pruning we do, with less search as a result. But this might not be economical Branch and bound is a systematic search, and is a complete algorithm. HeuristicsA heuristic is a rule of thumb. That is, a heuristic is generally a good idea but some times iyt doesn't work. An example of a heuristic for packing a suitcase might be, put in the big objects first such as your shoes, then put the small items in using up the remaining fragmented space. For the tsp we might have heuristics for selecting the next city to visit. Maybe go to the nearest?Some Engineering DecisionsThe cost matrix, where C[i,j} is the cost of going from i to j. Should we precompute this? Is the cost matrix symmetric? Is the cost always distance, Manhattan or Euclidean? (By the way, what is Manhattan and Euclidean?)Greedy and Stochastic SearchComplete search may be impossible when n gets large, and we may resort to incomplete methods, not guaranteed to find the best solution. Examples may be 2-opt as a move operator1. given a tour S and a cost of that tour cost(S) 2. generate a neighbouring tour S' from S 3. if cost(S') < cost(S) then S <- S' 4. if still time remaining go to step 2. 5. S is the best tour foundThe best tour found (step 5) does not mean the very best. How do we extend the above? - good neighbourhood moves, such as 2-opt NOTE: do not need to re-evaluate entire tour! - above is hill descending/climbing - steepest descent, generate entire neighbourhood in step 2, and select best from neighbourhood. (question: how big is the neighbourhood?) - allow occassional uphill move |