The following code snippets provide a means of solving the traveling salesman problem in the clojure programming language.

Don’t know what it is? Look here: traveling salesman

The code (currently heavily lacks comments, will do some in time):

; we use permute to find the x-th permutation of a list, a, in lexicographic order.

(defn permute [x a]

(if (= (count a) 1 ) a

(letfn [(fact [num] (if (< num 2) 1 (* num (fact (- num 1)))))]

(let [p (mod(/ x (fact (- (count a) 1))) (count a))]

(vec(cons (nth a p)(permute (mod x (fact (- (count a) 1))) (vec (concat (subvec a 0 p) (subvec a (inc p) (count a)))))))))))

; figure out the possible routes with routes()

; n is the start point

; i.e. (routes 0, [1 2 3 4]) gives all routes starting with 1

; starting from [1 2 3 4] in the order.

(defn routes [n, myList] (if (< n (/(factorial (count myList)) (count myList)))

(vec(cons (permute n myList) (routes (inc n) myList)))))

;list out the distances – this is for testing purposes.

(def dists [[0,21,41,30,43],[21,0,21,19,24],[41,21,0,20,20],[30,19,20,0,36],[43,24,20,36,0]])

; this is a helper factorial function

(defn factorial [n] (if (< n 2) 1 (* n (factorial (dec n)))))

; calculate the distance

(defn distance [route]

;finished going through route, figure out distance to the start

(if (= (count route) 1) (nth (nth dists (first route)) 0)

;get the first and second portions of the route

(let [f (first route), s (first(rest route))]

;keep total using distances [f][s]

;recur with (rest route)

;(println (nth (nth dists f)s))

(+ (nth (nth dists f) s) (distance (rest route))))))

;iterate through routes find the shortest distance, and return the route.

(defn find-best [toCheck best dist]

(if (= (count toCheck) 0) [dist, best]

(if (< (distance (first toCheck)) dist)

;then

(find-best (rest toCheck) (first toCheck) (distance (first toCheck)))

;else

(find-best (rest toCheck) best dist))))

;the test – define a list of routes

(def route-list(routes 0 [0 1 2 3 4]))

; find the best one via brute force.

(find-best (rest route-list)(first route-list)(distance (first route-list)))

the end result of my test:

[115, [0 1 4 2 3]].

Checked. It was right. Others were equal in distance, but still.

It was right.

Spent all day on this.

Mind = blown.

## Add a comment