1 """TSP solver using various method --yong27, 2005-06-03
2 """
3 import unittest
4 import random, math, time
5
6 class City:
7 ID = 0
8 def __init__(self):
9 self.x = 0
10 self.y = 0
11 self.name = City.ID
12 City.ID+=1
13 def setPosition(self, (x,y)):
14 self.x = x
15 self.y = y
16 def setRandomPosition(self):
17 self.x = random.random()
18 self.y = random.random()
19 def getPosition(self):
20 return self.x, self.y
21
22 def getDistanceBetween(self, aCity):
23 return math.sqrt((self.x - aCity.x)**2 + (self.y - aCity.y)**2)
24
25
26 class SalseMan:
27 def __init__(self):
28 self.cities = dict()
29
30 def addCity(self, aCity):
31 self.cities[aCity.name] = aCity
32
33 def getCity(self, aCityName):
34 return self.cities[aCityName]
35
36 def getNumOfCities(self):
37 return len(self.cities)
38
39 def getShortestPath(self):
40 raise NotImplementedError
41
42 def getDistanceWithCities(self, cities):
43 distance = 0
44 for i in range(len(cities)-1):
45 distance += cities[i].getDistanceBetween(cities[i+1])
46 return distance
47
48 def reportTravel(self):
49 t1 = time.time()
50 path, distance = self.getShortestPath()
51 elaspedTime = time.time() - t1
52
53 class PermutationSalseMan(SalseMan):
54 def __init__(self):
55 SalseMan.__init__(self)
56
57 def getShortestPath(self):
58 shortestDistance = 0
59 for cityNames in self.permutate(self.cities.keys()):
60 distance = self.getDistanceWithCities(
61 [self.getCity(cityName) for cityName in cityNames])
62 if shortestDistance == 0 or distance < shortestDistance:
63 shortestDistance = distance
64 shortestPath = cityNames
65 return shortestPath, shortestDistance
66
67 def permutate(self, items):
68 return self.xcombinations(items, len(items))
69
70 def xcombinations(items, n):
71 if n==0: yield []
72 else:
73 for i in xrange(len(items)):
74 for cc in PermutationSalseMan.xcombinations(items[:i]+items[i+1:],n-1):
75 yield [items[i]]+cc
76 xcombinations = staticmethod(xcombinations)
77
78
79 class TravelingCenter:
80 def __init__(self, aSalseMan, numOfCities):
81 cities = list()
82 self.salseMan = aSalseMan
83 for i in range(numOfCities):
84 city = City()
85 city.setRandomPosition()
86 aSalseMan.addCity(city)
87
88 def report(self):
89 return self.salseMan.reportTravel()
90
91 def main(numOfCities):
92 reprRecord = lambda l: '||%s||'%'||'.join(map(str,l))
93 reportTitles = ("NumOfCities", "Path", "Distance", "Time(sec)")
94 print reprRecord(reportTitles)
95 for i in range(numOfCities):
96 tc= TravelingCenter(PermutationSalseMan(),i)
97 print reprRecord(tc.report())
98 City.ID = 0
99
100 class TestTsp(unittest.TestCase):
101 def setUp(self):
102 self.sm = SalseMan()
103 self.cities=[]
104 for i in range(3):
105 self.cities.append(City())
106 self.cities[0].setPosition((1,1))
107 self.cities[1].setPosition((0,1))
108 self.cities[2].setPosition((0,0))
109
110 def testCity(self):
111 self.assertEquals((1,1),self.cities[0].getPosition())
112 self.assertEquals(1, self.cities[1].name)
113 self.assertEquals(1, self.cities[0].getDistanceBetween(self.cities[1]))
114
115 def testGetDistanceWithCities(self):
116 self.assertEquals(2 ,self.sm.getDistanceWithCities(self.cities))
117
118 def testPermutationSalseMan(self):
119 psm = PermutationSalseMan()
120 for i in range(3):
121 psm.addCity(self.cities[i])
122 self.assertEquals(([0,1,2],2) ,psm.getShortestPath())
123
124 def tearDown(self):
125 City.ID = 0
126
127 if __name__=='__main__':
128
129 main(30)