ABCD, 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!).
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 (also see /home/s7/pat/scheme/pub/perm.scm)(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'))) ;
(perm' (remove e source) (append sink (list e)))))))) (perm' x '()) all-perms)) ;;; Produce all permutations of the list x. ;;; This corresponds to all possible ordering of the elements in x. ;;; ;;; For the tsp a permutation corresponds to a tour ;;; We can explore all permutations and choose the best ;;; Alternatively we can make the recursive call to perm' ;;; conditionally. That is, if the current partial tour in ;;; sink costs less than the best so far we might extend it. ;;; ;;; We can now go 1 step further and look at a lower bound on extending ;;; the partial tour in sink ... can you think of some of these? ;;;
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.
and has a cost of 90. - the minimum cost of going from D->E is 12 - the minimum cost D->F is 10 - there is no way to extend ACBD at a cost less than 100. - Consequently we can abandon the partial tour ACBD.
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