Touch the firehose of ds106, the most recent flow of content from all of the blogs syndicated into ds106. As of right now, there have been 92629 posts brought in here going back to December 2010. If you want to be part of the flow, first learn more about ds106. Then, if you are truly ready and up to the task of creating web art, sign up and start doing it.

The Traveling Salesman

Posted by
|

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

ds106 in[SPIRE]