Difference between revisions of "TADM2E 1.26"

Revision as of 15:53, 23 July 2020

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