|
|
| Line 1: |
Line 1: |
| − | Tests show that closest pairs heuristic generally performs better than nearest neighbour heuristic.<br/>
| |
| − | Here's python implementation for <b>nearest neighbour</b> heuristic:
| |
| − | <pre>
| |
| − | 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()
| |
| − | </pre>
| |
| − |
| |
| − | <br/>Python implementation of <b>closest pair</b> heuristic<br/>
| |
| − | <pre>
| |
| − | 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()</pre>
| |
| − | <br/>The <b>minimum angle with randomised centroid heuristic</b> solves both cases closest pair and nearest neighbour can't handle.<br/>
| |
| − | 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.<br/>
| |
| − | 2. Find the point that is furthermost from centroid. Let's call it point1<br/>
| |
| − | 3. Find point2 that comprises the smallest angle point1-centroid-point2<br/>
| |
| − | 4. Connect point1 and point2 with an edge.<br/>
| |
| − | 5. Repeat from step 3 with point2.<br/>
| |
| − | <pre>
| |
| − | 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()</pre>
| |
