import math
import random
def euclid(p,q):
Copyright By PowCoder代写 加微信 powcoder
x = p[0]-q[0]
y = p[1]-q[1]
return math.sqrt(x*x+y*y)
class Graph:
# Complete as described in the specification, taking care of two cases:
# the -1 case, where we read points in the Euclidean plane, and
# the n>0 case, where we read a general graph in a different format.
# self.perm, self.dists, self.n are the key variables to be set up.
def __init__(self,n,filename):
# Complete as described in the spec, to calculate the cost of the
# current tour (as represented by self.perm).
def tourValue(self):
# Attempt the swap of cities i and i+1 in self.perm and commit
# commit to the swap if it improves the cost of the tour.
# Return True/False depending on success.
def trySwap(self,i):
# Consider the effect of reversiing the segment between
# self.perm[i] and self.perm[j], and commit to the reversal
# if it improves the tour value.
# Return True/False depending on success.
def tryReverse(self,i,j):
def swapHeuristic(self,k):
better = True
while better and (count < k or k == -1):
better = False
count += 1
for i in range(self.n):
if self.trySwap(i):
better = True
def TwoOptHeuristic(self,k):
better = True
while better and (count < k or k == -1):
better = False
count += 1
for j in range(self.n-1):
for i in range(j):
if self.tryReverse(i,j):
better = True
# Implement the Greedy heuristic which builds a tour starting
# from node 0, taking the closest (unused) node as 'next'
# each time.
def Greedy(self):
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com