#
# permutations; traveling salesman problem
import copy
# The array scost represents the symmetrical edge cost function for the graph,
# between all pairs of points. Only the part below the diagonal is represented,
# i.e., for j <= i.
# The function cost gives the full cost function, by using the symmetry
scost = [[0],
[633, 0],
[257, 390, 0],
[91, 661, 228, 0],
[412, 227, 169, 383, 0],
[150, 488, 112, 120, 267, 0],
[80, 572, 196, 77, 351, 63, 0],
[134, 530, 154, 105, 309, 34, 29, 0],
[259, 555, 372, 175, 338, 264, 232, 249, 0],
[505, 289, 262, 476, 196, 360, 444, 402, 495, 0],
[353, 282, 110, 324, 61, 208, 292, 250, 352, 154, 0],
[324, 638, 437, 240, 421, 329, 297, 314, 95, 578, 435, 0],
[ 70, 567, 191, 27, 346, 83, 47, 68, 189, 439, 287, 254, 0],
[211, 466, 74, 182, 243, 105, 150, 108, 326, 336, 184, 391, 145, 0],
[268, 420, 53, 239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0],
[246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157, 289, 426, 483, 0],
[121, 518, 142, 84, 297, 35, 29, 36, 236, 390, 238, 301, 55, 96, 153, 336, 0]]
def cost (i, j):
if i>=j:
return scost [i][j]
else:
return scost [j][i]
# the function tourcost returns the cost of the tour s,
# where s is a list (array) of points in the graph
def tourcost (s):
total = 0
for i in range (0, len(s)):
total = total + cost (s[i-1], s[i])
return total
seq = range(5)
cnt = 0
def allperm (i):
# allperm(i) computes the permutations of seq [i:]
# to compute cost of the associated tours
# for fixed seq [0:i-1]
# should return seq in original stat
global cnt, mintourcost, mintour
if i==len(seq)-1:
tour = tourcost (seq)
if tour < mintourcost:
mintourcost = tour
mintour = copy.copy (seq)
print "(",cnt, ")", "sec=", seq, "cost=", tour
cnt = cnt+1
else:
for j in range (i, len(seq)):
seq[i], seq[j] = seq [j], seq[i]
allperm (i+1)
seq[i], seq[j] = seq [j], seq[i]
mintour = []
mintourcost = 1000000000
print "seq = ", seq, "len =", len(seq)
allperm (0)
print "finished - mintour=", mintour, "cost=", mintourcost