## Traveling Salesman: Minimum Spanning Tree

### April 13, 2010

We represent the problem slightly differently than we have in the past; the input to the `tsp`

function is a list of three-slot lists with the vertex name (a number from 0 to *n*-1) in the first slot, the *x*-coordinate in the second slot, and the *y*-coordinate in the third slot. Our `make-tsp`

returns a random traveling salesman problem and fixes a bug in the earlier versions:

`(define (make-tsp n)`

(let loop ((k n) (zs '()))

(if (zero? k) zs

(let ((z (list (- k 1) (randint (* n 10)) (randint (* n 10)))))

(if (member (cdr z) (map cdr zs)) (loop k zs)

(loop (- k 1) (cons z zs)))))))

`Dist`

computes the euclidean distance between two points:

`(define (dist a b)`

(define (square x) (* x x))

(sqrt (+ (square (- (cadr a) (cadr b)))

(square (- (caddr a) (caddr b))))))

`Make-vertices`

extracts a list of vertices from a list of points; its implementation is trivial. `Make-edges`

uses a list comprehension to form the list of edges that connect all the points to each other:

`(define (make-vertices ps) (map car ps))`

`(define (make-edges ps)`

(list-of (list (dist a b) (car a) (car b))

(a in ps) (b in ps) (< (car a) (car b))))

We’re ready now to compute the traveling salesman tour. We use Kruskal’s algorithm to compute the minimum spanning tree; Prim’s algorithm would work equally well. The basic algorithm is depth-first search starting from vertex 0:

`(define (tsp ps)`

(let loop ((es (map cdr (kruskal (make-vertices ps) (make-edges ps))))

(vs (list 0)) (zs (list 0)))

(cond ((null? es) zs)

((find (car vs) es) =>

(lambda (edge)

(let ((v (if (equal? (car vs) (car edge)) (cadr edge) (car edge))))

(loop (remove edge es) (cons v vs) (cons v zs)))))

(else (loop es (cdr vs) zs)))))

Here, `es`

is the list of edges that form the minimum spanning tree; an edge is removed when it is added to the tour. `Vs`

is the stack of vertices that we accumulate as we move down the depth-first search, and `zs`

is the list of vertices that form the tour. The `find`

function returns the next edge in the depth-first search, or `#f`

if the current vertex has no unvisited children:

`(define (find x xs)`

(cond ((null? xs) #f)

((or (equal? x (caar xs)) (equal? x (cadar xs))) (car xs))

(else (find x (cdr xs)))))

Here’s an example:

`> (define ps '((0 88 24) (1 11 92) (2 58 26)`

(3 99 69) (4 14 28) (5 15 81) (6 47 15)

(7 96 90) (8 78 11) (9 88 74)))

> (tsp ps)

(1 5 4 6 2 8 7 9 3 0)

We stole a lot of code to write this program. Random numbers, hash tables, list comprehensions and sorting come from the Standard Prelude, as do the `remove`

and `identity`

functions. We also used Kruskal’s algorithm, which in turn calls disjoint sets. You can run the assembled code at http://programmingpraxis.codepad.org/ffuo6IzG.

Pages: 1 2