# 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()