TADM2E 1.26
From Algorithm Wiki
Tests show that closest pairs heuristic generally performs better than nearest neighbour heuristic.
Here's python implementation for nearest neighbour heuristic:
import random
import matplotlib.pyplot as plot
import matplotlib.cm as cm
import numpy as np
import math
def draw_arrow(axis, p1, p2, linecolor, style='solid', text="", radius=0):
"""draw an arrow connecting point 1 to point 2"""
axis.annotate(text,
xy=p2,
xycoords='data',
xytext=p1,
arrowprops=dict(arrowstyle="-", linestyle=style, linewidth=0.8, color=linecolor,
connectionstyle="arc3,rad=" + str(radius)),)
#nearest neighbour heuristic
def nearest_neighbour(datapoints):
x, y = 0, 1
#pick random starting point and add it to path
i = random.randint(0, len(datapoints) - 1)
path = [datapoints[i]]
del datapoints[i]
i = 0
# while there are points find the closest one to datapoints[i], add it to path
while(len(datapoints) != 0):
minlen = 1e124
minind = -1
for k in range(len(datapoints)):
dist = math.hypot(datapoints[k][x] - path[i][x], datapoints[k][y] - path[i][y])
if minlen > dist:
minlen = dist
minind = k
path.append(datapoints[minind])
del datapoints[minind]
i += 1
return path
# MAIN SCRIPT
random.seed()
figure = plot.figure()
axis = figure.add_subplot(111)
n = 6
points = [(random.uniform(0.01, 0.99), random.uniform(0.01, 0.99)) for i in range(n)]
# points for line
points = [(0.3, 0.2), (0.25, 0.2), (0.5, 0.2), (0.7, 0.2), (0.6, 0.2), (0.8, 0.2)]
# find shortest path
path_points = nearest_neighbour(points)
# draw path
colors = cm.rainbow(np.linspace(0, 1, len(path_points)))
plot.scatter([i[0] for i in path_points], [i[1] for i in path_points], color=colors)
# draw shortest path from point[0] to point[n-1]:
draw_arrow(axis, path_points[0], path_points[1], colors[0], style='solid', radius=0.3)
for i in range(1, len(path_points)-1):
draw_arrow(axis, path_points[i], path_points[i + 1], colors[i], radius=0.3)
draw_arrow(axis, path_points[n - 1], path_points[0], colors[n-1], style='dashed', radius=0.3)
plot.show()
Python implementation of closest pair heuristic
import random
import matplotlib.pyplot as plot
import matplotlib.cm as cm
import numpy as np
import math
def draw_arrow(axis, p1, p2, linecolor, style='solid', text = "", radius = 0):
"""draw an arrow connecting point 1 to point 2"""
axis.annotate(text,
xy=p2,
xycoords='data',
xytext=p1,
arrowprops=dict(arrowstyle="-", linestyle=style, linewidth=0.8, color=linecolor,
connectionstyle="arc3,rad=" + str(radius)),)
#closest pair heuristic
def closest_pair(points):
distance = lambda c1p, c2p: math.hypot(c1p[0] - c2p[0], c1p[1] - c2p[1])
chains = [[points[i]] for i in range(len(points))]
edges = []
for i in range(len(points)-1):
dmin = float("inf") # infinitely big distance
# test each chain against each other chain
for chain1 in chains:
for chain2 in [item for item in chains if item is not chain1]:
# test each chain1 endpoint against each of chain2 endpoints
for c1ind in [0, len(chain1) - 1]:
for c2ind in [0, len(chain2) - 1]:
dist = distance(chain1[c1ind], chain2[c2ind])
if dist < dmin:
dmin = dist
# remember endpoints as closest pair
chain2link1, chain2link2 = chain1, chain2
point1, point2 = chain1[c1ind], chain2[c2ind]
# connect two closest points
edges.append((point1, point2))
chains.remove(chain2link1)
chains.remove(chain2link2)
if len(chain2link1) > 1:
chain2link1.remove(point1)
if len(chain2link2) > 1:
chain2link2.remove(point2)
linkedchain = chain2link1
linkedchain.extend(chain2link2)
chains.append(linkedchain)
# connect first endpoint to last one
edges.append((chains[0][0], chains[0][len(chains[0])-1]))
return chains[0], edges
# MAIN SCRIPT
random.seed()
figure = plot.figure()
axis = figure.add_subplot(111)
n = 6
points = [(random.uniform(0.01, 0.99), random.uniform(0.01, 0.99)) for i in range(n)]
# six points for a rectangle
points = [(0.3, 0.2), (0.3, 0.4), (0.501, 0.4), (0.501, 0.2), (0.702, 0.4), (0.702, 0.2)]
#find shortest path
path_points, edges = closest_pair(points)
#draw path
colors = cm.rainbow(np.linspace(0, 1, len(path_points)))
plot.scatter([i[0] for i in points], [i[1] for i in points], color=colors)
# draw shortest path from point[0] to point[n-1]:
for i in range(len(edges)):
draw_arrow(axis, edges[i][0], edges[i][1], 'black', radius=0.)
plot.show()
The minimum angle with randomised centroid heuristic solves both cases closest pair and nearest neighbour can't handle.
1. Calculate the centroid (geometric mean of x and y coordinates) of all points given. Add a little offset to centroid, that allows to solve cases when points form a line.
2. Find the point that is furthermost from centroid. Let's call it point1
3. Find point2 that comprises the smallest angle point1-centroid-point2
4. Connect point1 and point2 with an edge.
5. Repeat from step 3 with point2.
import random
import matplotlib.pyplot as plot
import matplotlib.cm as cm
import numpy as np
import math
def draw_arrow(axis, p1, p2, linecolor, style='solid', text = "", radius = 0):
"""draw an arrow connecting point 1 to point 2"""
axis.annotate(text,
xy=p2,
xycoords='data',
xytext=p1,
arrowprops=dict(arrowstyle="-", linestyle=style, linewidth=0.8, color=linecolor,
connectionstyle="arc3,rad=" + str(radius)),)
def angle_degrees(p1, center, p2):
"""angle in radians"""
distance = lambda c1p, c2p: math.hypot(c1p[0] - c2p[0], c1p[1] - c2p[1])
a = distance(center, p1)
b = distance(center, p2)
c = distance(p2, p1)
cosine = (a**2 + b**2 - c**2) / (2*a*b)
return math.acos(min(max(cosine, -1), 1))
def centroid(points):
center = (sum([point[0] for point in points])/len(points) + random.uniform(0.010, 0.015),
sum([point[1] for point in points])/len(points) + random.uniform(0.010, 0.015))
edges = []
# remember how many connections a point has. start with 0 connections
uses = dict([(point, 0) for point in points])
# start with the furthermost point
point1 = points[0]
longest = math.hypot(center[0] - point1[0], center[1] - point1[1])
for pt in points:
dist = math.hypot(center[0] - pt[0], center[1] - pt[1])
if dist > longest:
longest = dist
point1 = pt
# for every point find the other one that comprises the SMALLEST angle poin1-center-point2
while True:
if uses[point1] < 2:
min_angle = 1e34
point_to_connect = None
# point must not be used more than twice!
for point2 in [item for item in points if item is not point1]:
angle = angle_degrees(point1, center, point2)
if not (point1, point2) in edges and not (point2, point1) in edges and uses[point2] < 1 and\
angle < min_angle:
min_angle = angle
point_to_connect = point2
if point_to_connect is not None:
edges.append((point1, point_to_connect))
uses[point1] += 1
uses[point_to_connect] += 1
point1 = point_to_connect
else:
break
else:
break
# connect the last two points
last_points = [k for k, v in uses.iteritems() if v == 1]
assert(len(last_points) == 2)
edges.append((last_points[0], last_points[1]))
return edges, center
# MAIN SCRIPT
random.seed()
figure = plot.figure()
axis = figure.add_subplot(111)
n = random.randint(6, 10)
points = [(random.uniform(0.01, 0.99), random.uniform(0.01, 0.99)) for i in range(n)]
# points for line
#points = [(0.3, 0.2), (0.4, 0.2), (0.5, 0.2), (0.7, 0.2), (0.6, 0.2), (0.86, 0.2)]
# six points for a rectangle
#points = [(0.3, 0.2), (0.3, 0.4), (0.501, 0.4), (0.501, 0.2), (0.702, 0.4), (0.702, 0.2)]
edges, center = centroid(points)
# draw points
colors = cm.rainbow(np.linspace(0, 1, len(points)))
plot.scatter([i[0] for i in points], [i[1] for i in points], color=colors)
# draw lines from centroid to points
plot.scatter(center[0], center[1], color='green')
for point in points:
draw_arrow(axis, center, point, 'red', radius=0)
# draw edges of shortest path
for i in range(len(edges)):
draw_arrow(axis, edges[i][0], edges[i][1], 'black', radius=0.)
plot.show()
