Traveling Salesman: Nearest Neighbor
March 16, 2010
We represent a point as a three-slot vector with the point number (on the range 0 to n-1) in slot 0, x-coordinate in slot 1, and y-coordinate in slot 2. Here are convenience functions:
(define (n p) (vector-ref p 0))
(define (x p) (vector-ref p 1))
(define (y p) (vector-ref p 2))
A traveling salesman problem is a list of points. We make a problem with make-tsp
:
(define (make-tsp n)
(define n10 (* n 10))
(let loop ((n (- n 1)) (ps '()))
(if (negative? n) ps
(let ((p (vector n (randint n10) (randint n10))))
(if (member p ps) (loop n ps)
(loop (- n 1) (cons p ps)))))))
We compute distances as they are used, caching them in a global variable dists
, which is a two-dimensional matrix initialized in the main solving program. We store the distance twice, in both directions, because the space cost is very little (we allocate the entire matrix), and it saves us the trouble of figuring out a canonical direction:
(define dists #f)
(define (dist a b)
(define (square x) (* x x))
(when (negative? (matrix-ref dists (n a) (n b)))
(let ((d (sqrt (+ (square (- (x a) (x b)))
(square (- (y a) (y b)))))))
(matrix-set! dists (n a) (n b) d)
(matrix-set! dists (n b) (n a) d)))
(matrix-ref dists (n a) (n b)))
Given a point p and a list of unvisited points ps, function nearest
finds the nearest unvisited point:
(define (nearest p ps)
(let loop ((ps ps) (min-p #f) (min-d #f))
(cond ((null? ps) min-p)
((or (not min-d) (< (dist p (car ps)) min-d))
(loop (cdr ps) (car ps) (dist p (car ps))))
(else (loop (cdr ps) min-p min-d)))))
We are ready for the solver. Tsp
initializes the dists
matrix, then enters a loop in which it tracks both the current tour and the list of unvisited points; at each step of the loop, it calculates the nearest neighbor, adds that point to the current tour and removes it from the list of unvisited points, and loops, stopping when the tour is complete. The initial point is always the first point in the input:
(define (tsp ps)
(let ((len (length ps)))
(set! dists (make-matrix len len -1)))
(let loop ((tour (list (car ps))) (unvisited (cdr ps)))
(if (null? unvisited) tour
(let ((next (nearest (car tour) unvisited)))
(loop (cons next tour) (remove next unvisited))))))
Here we compute the cost of the tour:
(define (cost tour)
(if (or (null? tour) (null? (cdr tour))) 0
(let ((start (car tour)))
(let loop ((tour tour) (sum 0))
(if (null? (cdr tour))
(+ sum (dist (car tour) start))
(loop (cdr tour) (+ sum (dist (car tour) (cadr tour)))))))))
We use remove, make-matrix, matrix-set!, matrix-ref, rand and randint from the Standard Prelude. You can run the program, complete with an example, at http://programmingpraxis.codepad.org/tVIXh2TW.
My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/16/programming-praxis-traveling-salesman-nearest-neighbor/ for a version with comments):
[…] Praxis – Traveling Salesman: Nearest Neighbor By Remco Niemeijer In today’s Programming Praxis exercise we have to implement a significantly faster algorithm for the traveling […]
[…] data. On Programming Praxis they have proposed to resolve the problem using brute force, and using the closest neighbor (a simplification of the […]
A solution in Python, including comparison with brute force. Comments on my blog on http://wrongsideofmemphis.wordpress.com/2010/03/16/travelling-salesman/
import random
import itertools
import operator
import datetime
MAX_X = 100
MAX_Y = 100
def random_cities(number):
”’ Generate a number of cities located on random places ”’
cities = [ (random.randrange(0, MAX_X),
random.randrange(0, MAX_Y))
for i in range(number) ]
return cities
def path_lenght(path):
”’ Get the lenght of a path ”’
lenght = 0
for i in xrange(len(path) – 1):
# Add the distance between two cities
lenght += abs(complex(path[i][0], path[i][1])
– complex(path[i + 1][0], path[i + 1][1]))
return lenght
def find_path_bruteforce(cities):
”’ Find the smallest path using brute force ”’
lenghts = []
for path in itertools.permutations(cities, len(cities)):
# Get the length of the path, adding the returning point
total_path = path + (path[0],)
lenght = path_lenght(total_path)
lenghts.append((total_path, lenght))
# Get minimum
lenghts.sort(key=operator.itemgetter(1))
return lenghts[0]
def find_path_nearest(cities):
”’ Find the closest neibour ”’
lenghts = []
for city in cities:
lenght = 0
actual_cities = cities[:]
actual_city = actual_cities.pop(actual_cities.index(city))
path = [actual_city, ]
# Find nearest neibour
while actual_cities:
min_lenght = []
for next_city in actual_cities:
min_lenght.append((next_city, abs(complex(city[0], city[1])
– complex(next_city[0], next_city[1]))))
# Get closest neibor
min_lenght.sort(key=operator.itemgetter(1))
actual_city = min_lenght[0][0]
lenght += min_lenght[0][1]
actual_cities.pop(actual_cities.index(actual_city))
path.append(actual_city)
# Complete the trip with the first city
path.append(city)
lenghts.append((tuple(path), path_lenght(path)))
# Get minimum
lenghts.sort(key=operator.itemgetter(1))
return lenghts[0]
if __name__ == ‘__main__’:
for i in range(3, 10):
print ‘Number of cities: ‘, i
cities = random_cities(i)
time1 = datetime.datetime.now()
path2, lenght_neighbor = find_path_nearest(cities)
time2 = datetime.datetime.now()
print path2, lenght_neighbor
time_neighbor = time2 – time1
print ‘Time neighbor: ‘, time_neighbor
time1 = datetime.datetime.now()
path1, lenght_brute = find_path_bruteforce(cities)
time2 = datetime.datetime.now()
print path1, lenght_brute
time_brute = time2 – time1
print ‘Time brute force: ‘, time_brute
print ‘Diff: ‘, float(lenght_neighbor – lenght_brute) / lenght_brute * 100, ‘%’
Another brute force and nearest neighbor implementation in python.
hello
The algorithm I would like the C languagei
Can you help me?