Python Traveling Salesman Greedy Algorithm -
so have created sort traveling salesman problem , con sort x-coordinates , y-coordinates.
i trying implement greedy search, unable to.
also, each point instantiated in matrix city such [0,3,4] 0 header, 3 x coordinate, , 4 y coordinate.
here program should able run. main problem algorithm isn't working , need fixing working greedy algorithm. can find algorithm near end of code.
this text file need takes input from.
the traveling salesman problem (tsp) combinatorial optimization problem, given map (a set of cities , positions), 1 wants find order visiting cities in such way travel distance minimal.
i suggest solving tsp , solve visual stuff.
following code contains set of functions illustrate: - construction heuristics tsp - improvement heuristics constructed solution - local search, , random-start local search.
import math import random def distl2((x1,y1), (x2,y2)): """compute l2-norm (euclidean) distance between 2 points. distance rounded closest integer, compatibility tsplib convention. 2 points located on coordinates (x1,y1) , (x2,y2), sent parameters""" xdiff = x2 - x1 ydiff = y2 - y1 return int(math.sqrt(xdiff*xdiff + ydiff*ydiff) + .5) def distl1((x1,y1), (x2,y2)): """compute l1-norm (manhattan) distance between 2 points. distance rounded closest integer, compatibility tsplib convention. 2 points located on coordinates (x1,y1) , (x2,y2), sent parameters""" return int(abs(x2-x1) + abs(y2-y1)+.5) def mk_matrix(coord, dist): """compute distance matrix set of points. uses function 'dist' calculate distance between 2 points. parameters: -coord -- list of tuples coordinates of points, [(x1,y1),...,(xn,yn)] -dist -- distance function """ n = len(coord) d = {} # dictionary hold n times n matrix in range(n-1): j in range(i+1,n): (x1,y1) = coord[i] (x2,y2) = coord[j] d[i,j] = dist((x1,y1), (x2,y2)) d[j,i] = d[i,j] return n,d def read_tsplib(filename): "basic function reading tsp problem on tsplib format" "note: works 2d euclidean or manhattan distances" f = open(filename, 'r'); line = f.readline() while line.find("edge_weight_type") == -1: line = f.readline() if line.find("euc_2d") != -1: dist = distl2 elif line.find("man_2d") != -1: dist = distl1 else: print "cannot deal non-euclidean or non-manhattan distances" raise exception while line.find("node_coord_section") == -1: line = f.readline() xy_positions = [] while 1: line = f.readline() if line.find("eof") != -1: break (i,x,y) = line.split() x = float(x) y = float(y) xy_positions.append((x,y)) n,d = mk_matrix(xy_positions, dist) return n, xy_positions, d def mk_closest(d, n): """compute sorted list of distances each of nodes. each node, entry in form [(d1,i1), (d2,i2), ...] each tuple pair (distance,node). """ c = [] in range(n): dlist = [(d[i,j], j) j in range(n) if j != i] dlist.sort() c.append(dlist) return c def length(tour, d): """calculate length of tour according distance matrix 'd'.""" z = d[tour[-1], tour[0]] # edge last first city of tour in range(1,len(tour)): z += d[tour[i], tour[i-1]] # add length of edge city i-1 return z def randtour(n): """construct random tour of size 'n'.""" sol = range(n) # set solution equal [0,1,...,n-1] random.shuffle(sol) # place in random order return sol def nearest(last, unvisited, d): """return index of node closest 'last'.""" near = unvisited[0] min_dist = d[last, near] in unvisited[1:]: if d[last,i] < min_dist: near = min_dist = d[last, near] return near def nearest_neighbor(n, i, d): """return tour starting city 'i', using nearest neighbor. uses nearest neighbor heuristic construct solution: - start visiting city - while there unvisited cities, follow closest 1 - return city """ unvisited = range(n) unvisited.remove(i) last = tour = [i] while unvisited != []: next = nearest(last, unvisited, d) tour.append(next) unvisited.remove(next) last = next return tour def exchange_cost(tour, i, j, d): """calculate cost of exchanging 2 arcs in tour. determine variation in tour length if arcs (i,i+1) , (j,j+1) removed, , replaced (i,j) , (i+1,j+1) (note exception last arc). parameters: -t -- tour -i -- position of first arc -j>i -- position of second arc """ n = len(tour) a,b = tour[i],tour[(i+1)%n] c,d = tour[j],tour[(j+1)%n] return (d[a,c] + d[b,d]) - (d[a,b] + d[c,d]) def exchange(tour, tinv, i, j): """exchange arcs (i,i+1) , (j,j+1) (i,j) , (i+1,j+1). given tour 't', remove arcs (i,i+1) , (j,j+1) , insert (i,j) , (i+1,j+1). done inverting sublist of cities between , j. """ n = len(tour) if i>j: i,j = j,i assert i>=0 , i<j-1 , j<n path = tour[i+1:j+1] path.reverse() tour[i+1:j+1] = path k in range(i+1,j+1): tinv[tour[k]] = k def improve(tour, z, d, c): """try improve tour 't' exchanging arcs; return improved tour length. if possible, make series of local improvements on solution 'tour', using breadth first strategy, until reaching local optimum. """ n = len(tour) tinv = [0 in tour] k in range(n): tinv[tour[k]] = k # position of each city in 't' in range(n): a,b = tour[i],tour[(i+1)%n] dist_ab = d[a,b] improved = false dist_ac,c in c[a]: if dist_ac >= dist_ab: break j = tinv[c] d = tour[(j+1)%n] dist_cd = d[c,d] dist_bd = d[b,d] delta = (dist_ac + dist_bd) - (dist_ab + dist_cd) if delta < 0: # exchange decreases length exchange(tour, tinv, i, j); z += delta improved = true break if improved: continue dist_bd,d in c[b]: if dist_bd >= dist_ab: break j = tinv[d]-1 if j==-1: j=n-1 c = tour[j] dist_cd = d[c,d] dist_ac = d[a,c] delta = (dist_ac + dist_bd) - (dist_ab + dist_cd) if delta < 0: # exchange decreases length exchange(tour, tinv, i, j); z += delta break return z def localsearch(tour, z, d, c=none): """obtain local optimum starting solution t; return solution length. parameters: tour -- initial tour z -- length of initial tour d -- distance matrix """ n = len(tour) if c == none: c = mk_closest(d, n) # create sorted list of distances each node while 1: newz = improve(tour, z, d, c) if newz < z: z = newz else: break return z def multistart_localsearch(k, n, d, report=none): """do k iterations of local search, starting random solutions. parameters: -k -- number of iterations -d -- distance matrix -report -- if not none, call print verbose output returns best solution , cost. """ c = mk_closest(d, n) # create sorted list of distances each node bestt=none bestz=none in range(0,k): tour = randtour(n) z = length(tour, d) z = localsearch(tour, z, d, c) if z < bestz or bestz == none: bestz = z bestt = list(tour) if report: report(z, tour) return bestt, bestz if __name__ == "__main__": """local search travelling saleman problem: sample usage.""" # # test functions: # # random.seed(1) # uncomment having same behavior import sys if len(sys.argv) == 1: # create graph several cities' coordinates coord = [(4,0),(5,6),(8,3),(4,4),(4,1),(4,10),(4,7),(6,8),(8,1)] n, d = mk_matrix(coord, distl2) # create distance matrix instance = "toy problem" else: instance = sys.argv[1] n, coord, d = read_tsplib(instance) # create distance matrix # n, coord, d = read_tsplib('instances/tsp/eil51.tsp') # create distance matrix # function printing best found solution when found time import clock init = clock() def report_sol(obj, s=""): print "cpu:%g\tobj:%g\ttour:%s" % \ (clock(), obj, s) print "*** travelling salesman problem ***" print # random construction print "random construction + local search:" tour = randtour(n) # create random tour z = length(tour, d) # calculate length print "random:", tour, z, ' --> ', z = localsearch(tour, z, d) # local search starting random tour print tour, z print # greedy construction print "greedy construction nearest neighbor + local search:" in range(n): tour = nearest_neighbor(n, i, d) # create greedy tour, visiting city 'i' first z = length(tour, d) print "nneigh:", tour, z, ' --> ', z = localsearch(tour, z, d) print tour, z print # multi-start local search print "random start local search:" niter = 100 tour,z = multistart_localsearch(niter, n, d, report_sol) assert z == length(tour, d) print "best found solution (%d iterations): z = %g" % (niter, z) print tour 
Comments
Post a Comment