tsp.py 3.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130
  1. import sys
  2. import copy
  3. import math
  4. from heapq import heappush, heappop
  5. from random import randint
  6. import matplotlib.pyplot as plt
  7. distances = []
  8. n = 0
  9. # returns hueristic value
  10. def heuristic(source, target, dist):
  11. #return 0
  12. for i in range(0, min(n * 2, n ** 2)):
  13. if (dist <= distances[i]):
  14. return 0
  15. return dist
  16. # returns weight(distance) between 2 vertices
  17. def weight(city1, city2):
  18. return math.sqrt((city1[1] - city2[1]) ** 2 + (city1[2] - city2[2]) ** 2)
  19. # returns if going to city i from curnode is okay
  20. def valid(curnode, cities, i):
  21. # can't revisit a city
  22. if (i in curnode[2]):
  23. return False
  24. # if curnode hasn't visited everything else and we are going to the gaol
  25. elif (len(curnode[2]) != (len(cities) - 1) and i == (len(cities) - 1)):
  26. return False
  27. else:
  28. return True
  29. # returns the count of child states. updates frontier
  30. def explore(curnode, frontier, cities):
  31. children = 0
  32. for i in range(1, len(cities)):
  33. # can we go here?
  34. if (valid(curnode, cities, i)):
  35. children += 1
  36. # add to frontier
  37. dist = weight(curnode[1], cities[i])
  38. metric = dist + heuristic(curnode[1], cities[i], dist)
  39. heappush(frontier, [curnode[0] + metric, cities[i], copy.deepcopy(curnode[2])])
  40. return children
  41. # A* solver for TSP
  42. def solve(frontier, cities):
  43. # number of child states
  44. newnodes = 0
  45. curnode = heappop(frontier)
  46. # while we are not on the goal node
  47. while (curnode[1] != cities[-1]):
  48. newnodes += explore(curnode, frontier, cities)
  49. curnode = heappop(frontier)
  50. curnode[2].append(cities.index(curnode[1]))
  51. return newnodes + 1
  52. def tsp(filename):
  53. # import map
  54. #prob = "instance_10.txt"
  55. prob = filename
  56. with open(prob) as file:
  57. prob = file.read().splitlines()
  58. global n
  59. n = int(prob[0])
  60. cities = prob[1:]
  61. counter = 0
  62. # convert to list of list of ints
  63. for l in cities:
  64. temp = l.split()
  65. temp[1] = int(temp[1])
  66. temp[2] = int(temp[2])
  67. temp.append(counter)
  68. counter += 1
  69. cities[cities.index(l)] = temp
  70. global distances
  71. distances = []
  72. for i in range(0, len(cities) - 1):
  73. for j in range(i, len(cities)):
  74. dist = weight(cities[i], cities[j])
  75. distances.append(dist)
  76. distances.sort()
  77. # add in goal state
  78. cities.append(copy.deepcopy(cities[0]))
  79. cities[-1][0] = "Goal"
  80. # create frontier
  81. frontier = []
  82. # add start state, list of visited, and distancesofar to frontier
  83. heappush(frontier, [0, cities[0], [0]])
  84. print(solve(frontier, cities))
  85. def main():
  86. plt.ioff()
  87. plt.switch_backend('agg')
  88. averages = []
  89. for i in range(1, 13):
  90. average = 0
  91. for j in range(1, 11):
  92. filepath = "tsp_problems/" + str(i) + "/instance_" + str(j) + ".txt"
  93. average += tsp(filepath)
  94. averages.append(average / 10.0)
  95. figure, axes = plt.subplots(1, 1, True)
  96. axes.plot(range(1, 13), averages, label='TSP Solver (Heuristic)')
  97. axes.legend()
  98. plt.xlabel("Number of Cities")
  99. plt.ylabel("Average Number of Nodes Generated in 10 Runs")
  100. plt.savefig("graph.pdf")
  101. main()