Shortest Path through Points (connect the dots)

Hi all!
I’ve hit a roadblock in trying to find the shortest path through a list of points. So far I’ve been able to connect the path in order of distance away from the control point (0,0) which essentially works, but the overall distance traveled is much greater than what the minimum can be, isn’t efficiency all we really want?

Graph so far:

The idea I’ve been messing around with is finding the minimum of DistanceTo (control point for the first one) and draw a line from start point to end point. Where I’m getting stuck here is using the min distant point found from the first pass as the base point to finding the next closest without referencing the point it just came from as that will technically be the closest, just in the opposite direction.

i.e:
point 1 = base point,
point 10 = closest distance to point 1
point x = closest distance to point 10
point y = closest distance to point x

Polycurve result from above mentioned graph: (ideal path started in red)

Any insight is greatly appreciated! :v:

Have you tried the “Shortest path by curve” node from the Sastrugi package. The run time to calculate the shortest path might be longer due to all the variations to consider. :wink:

1 Like

Thank you for the lead @Ewan_Opie! I’ll be trying this out as soon as possible! :grinning:

I guess this might be a little more complex than just find the shortest distance between the point and the next one…
If you want to go deep on learning about really modern tools, I think you should take a look at Optimo package, it is about AI. It is not that hard to understand and I really think it would help you. You would just need to create a custom node to be the “Fitness Function”…
There are some references:

http://dynamobim.org/optimo/

1 Like

Sounds like the traveling salesman problem. Did a quick google search, blatantly copied all the code from here:

did a few quick changes to adapt it to Dynamo and came up with the below result:

import System
import sys
pf_path = System.Environment.GetFolderPath(System.Environment.SpecialFolder.ProgramFilesX86)
sys.path.append('%s\IronPython 2.7\Lib' % pf_path)

import math
import random
from cStringIO import StringIO

sys.stdout = StringIO()

def distL2((x1,y1), (x2,y2)):
    """Compute the L2-norm (Euclidean) distance between two points.

    The distance is rounded to the closest integer, for compatibility
    with the TSPLIB convention.

    The two points are located on coordinates (x1,y1) and (x2,y2),
    sent as parameters"""
    xdiff = x2 - x1
    ydiff = y2 - y1
    return int(math.sqrt(xdiff*xdiff + ydiff*ydiff) + .5)


def distL1((x1,y1), (x2,y2)):
    """Compute the L1-norm (Manhattan) distance between two points.

    The distance is rounded to the closest integer, for compatibility
    with the TSPLIB convention.

    The two points are located on coordinates (x1,y1) and (x2,y2),
    sent as parameters"""
    return int(abs(x2-x1) + abs(y2-y1)+.5)


def mk_matrix(coord, dist):
    """Compute a distance matrix for a set of points.

    Uses function 'dist' to calculate distance between
    any two points.  Parameters:
    -coord -- list of tuples with coordinates of all points, [(x1,y1),...,(xn,yn)]
    -dist -- distance function
    """
    n = len(coord)
    D = {}      # dictionary to hold n times n matrix
    for i in range(n-1):
        for j in range(i+1,n):
            (x1,y1) = coord[i]
            (x2,y2) = coord[j]
            D[i,j] = dist((x1,y1), (x2,y2))
            D[j,i] = D[i,j]
    return n,D

def read_tsplib(filename):
    "basic function for reading a TSP problem on the TSPLIB format"
    "NOTE: only works for 2D euclidean or manhattan distances"
    f = open(filename, 'r');

    line = f.readline()
    while line.find("EDGE_WEIGHT_TYPE") == -1:
        line = f.readline()

    if line.find("EUC_2D") != -1:
        dist = distL2
    elif line.find("MAN_2D") != -1:
        dist = distL1
    else:
        print "cannot deal with non-euclidean or non-manhattan distances"
        raise Exception

    while line.find("NODE_COORD_SECTION") == -1:
        line = f.readline()

    xy_positions = []
    while 1:
        line = f.readline()
        if line.find("EOF") != -1: break
        (i,x,y) = line.split()
        x = float(x)
        y = float(y)
        xy_positions.append((x,y))

    n,D = mk_matrix(xy_positions, dist)
    return n, xy_positions, D


def mk_closest(D, n):
    """Compute a sorted list of the distances for each of the nodes.

    For each node, the entry is in the form [(d1,i1), (d2,i2), ...]
    where each tuple is a pair (distance,node).
    """
    C = []
    for i in range(n):
        dlist = [(D[i,j], j) for j in range(n) if j != i]
        dlist.sort()
        C.append(dlist)
    return C


def length(tour, D):
    """Calculate the length of a tour according to distance matrix 'D'."""
    z = D[tour[-1], tour[0]]    # edge from last to first city of the tour
    for i in range(1,len(tour)):
        z += D[tour[i], tour[i-1]]      # add length of edge from city i-1 to i
    return z


def randtour(n):
    """Construct a random tour of size 'n'."""
    sol = range(n)      # set solution equal to [0,1,...,n-1]
    random.shuffle(sol) # place it in a random order
    return sol


def nearest(last, unvisited, D):
    """Return the index of the node which is closest to 'last'."""
    near = unvisited[0]
    min_dist = D[last, near]
    for i in unvisited[1:]:
        if D[last,i] < min_dist:
            near = i
            min_dist = D[last, near]
    return near


def nearest_neighbor(n, i, D):
    """Return tour starting from city 'i', using the Nearest Neighbor.

    Uses the Nearest Neighbor heuristic to construct a solution:
    - start visiting city i
    - while there are unvisited cities, follow to the closest one
    - return to city i
    """
    unvisited = range(n)
    unvisited.remove(i)
    last = i
    tour = [i]
    while unvisited != []:
        next = nearest(last, unvisited, D)
        tour.append(next)
        unvisited.remove(next)
        last = next
    return tour



def exchange_cost(tour, i, j, D):
    """Calculate the cost of exchanging two arcs in a tour.

    Determine the variation in the tour length if
    arcs (i,i+1) and (j,j+1) are removed,
    and replaced by (i,j) and (i+1,j+1)
    (note the exception for the last arc).

    Parameters:
    -t -- a tour
    -i -- position of the first arc
    -j>i -- position of the second arc
    """
    n = len(tour)
    a,b = tour[i],tour[(i+1)%n]
    c,d = tour[j],tour[(j+1)%n]
    return (D[a,c] + D[b,d]) - (D[a,b] + D[c,d])


def exchange(tour, tinv, i, j):
    """Exchange arcs (i,i+1) and (j,j+1) with (i,j) and (i+1,j+1).

    For the given tour 't', remove the arcs (i,i+1) and (j,j+1) and
    insert (i,j) and (i+1,j+1).

    This is done by inverting the sublist of cities between i and j.
    """
    n = len(tour)
    if i>j:
        i,j = j,i
    assert i>=0 and i<j-1 and j<n
    path = tour[i+1:j+1]
    path.reverse()
    tour[i+1:j+1] = path
    for k in range(i+1,j+1):
        tinv[tour[k]] = k


def improve(tour, z, D, C):
    """Try to improve tour 't' by exchanging arcs; return improved tour length.

    If possible, make a series of local improvements on the solution 'tour',
    using a breadth first strategy, until reaching a local optimum.
    """
    n = len(tour)
    tinv = [0 for i in tour]
    for k in range(n):
        tinv[tour[k]] = k  # position of each city in 't'
    for i in range(n):
        a,b = tour[i],tour[(i+1)%n]
        dist_ab = D[a,b]
        improved = False
        for dist_ac,c in C[a]:
            if dist_ac >= dist_ab:
                break
            j = tinv[c]
            d = tour[(j+1)%n]
            dist_cd = D[c,d]
            dist_bd = D[b,d]
            delta = (dist_ac + dist_bd) - (dist_ab + dist_cd)
            if delta < 0:       # exchange decreases length
                exchange(tour, tinv, i, j);
                z += delta
                improved = True
                break
        if improved:
            continue
        for dist_bd,d in C[b]:
            if dist_bd >= dist_ab:
                break
            j = tinv[d]-1
            if j==-1:
                j=n-1
            c = tour[j]
            dist_cd = D[c,d]
            dist_ac = D[a,c]
            delta = (dist_ac + dist_bd) - (dist_ab + dist_cd)
            if delta < 0:       # exchange decreases length
                exchange(tour, tinv, i, j);
                z += delta
                break
    return z


def localsearch(tour, z, D, C=None):
    """Obtain a local optimum starting from solution t; return solution length.

    Parameters:
      tour -- initial tour
      z -- length of the initial tour
      D -- distance matrix
    """
    n = len(tour)
    if C == None:
        C = mk_closest(D, n)     # create a sorted list of distances to each node
    while 1:
        newz = improve(tour, z, D, C)
        if newz < z:
            z = newz
        else:
            break
    return z


def multistart_localsearch(k, n, D, report=None):
    """Do k iterations of local search, starting from random solutions.

    Parameters:
    -k -- number of iterations
    -D -- distance matrix
    -report -- if not None, call it to print verbose output

    Returns best solution and its cost.
    """
    C = mk_closest(D, n) # create a sorted list of distances to each node
    bestt=None
    bestz=None
    for i in range(0,k):
        tour = randtour(n)
        z = length(tour, D)
        z = localsearch(tour, z, D, C)
        if z < bestz or bestz == None:
            bestz = z
            bestt = list(tour)
            if report:
                report(z, tour)

    return bestt, bestz



"""Local search for the Travelling Saleman Problem: sample usage."""

coord = [(p.X, p.Y) for p in IN[0] ]
n, D = mk_matrix(coord, distL2) # create the distance matrix
instance = "toy problem"

# function for printing best found solution when it is found
from time import clock
init = clock()
def report_sol(obj, s=""):
    print "cpu:%g\tobj:%g" % \
          (clock(), obj)


print "*** travelling salesman problem ***"

# random construction
print "random construction + local search:"
tour = randtour(n)     # create a random tour
z = length(tour, D)     # calculate its length
print "random:", z, '  -->  ',   
z = localsearch(tour, z, D)      # local search starting from the random tour
print z

# greedy construction
print "greedy with nearest neighbor + local search:"
for i in xrange(5):
    tour = nearest_neighbor(n, i, D)     # create a greedy tour, visiting city 'i' first
    z = length(tour, D)
    print "nneigh attempt %i:" % i, z, '  -->  ',
    z = localsearch(tour, z, D)
    print z
print

# multi-start local search
print "random start local search:"
niter = 10
tour,z = multistart_localsearch(niter, n, D, report_sol)
assert z == length(tour, D)
print "best found (%i iterations): z = %g" % (niter, z)

sys.stdout.seek(0)
OUT = tour, sys.stdout.read()
16 Likes

You can also use nodeCurves.ShortestWalk from Lunchbox package which works pretty well (I supose that using dijkstra’s algorithm). See this link where something similar was also discussed.

@Dimitar_Venkov if I am not mistaken, the Traveking Salesman Problem finds the shortest path that goes through all points just once, rather than finding the shortest path from one point to another wihtin a given network of connected egdes.

2 Likes

This is actually closer to what I had pictured as the path of travel!
Thank you so much for your help! :grinning:

Oh wow this looks like it’ll be my next venture!

regards
Can I control the start and end point?

1 Like

Hi all,

I have had some great success using the above solution/python, but now I am trying to iterate the code over a list of spaces with objects in each space. It seems I cannot easily use levels to trick the python code to run separately for each space. Anyone know of a way to use loops in Dynamo to run the python code for each space in the 2D list I am passing? See attached screen shot.

See if this code inspired by the Greedy Algorithm works for you. The four paths in the example below are generated simultaneously. May not be the most efficient though.
The first point of the input list will be the starting point.

travellingSalesmanProblem.dyn (14.1 KB)

// Check for Self Intersection
def pgnInt (pts:var[]..[],pnt:var)
{
	//Edges with existing points
	pg01 = Polygon.ByPoints(pts).Explode();
	in01 = 1..List.Count(pg01);
	//Distance to New point
	ds01 = pnt.DistanceTo(pg01);
	//Index of closest edge to new point
	in02 = List.SortByKey(in01,ds01)["sortedList"];
	//Shift indices of points list
	pt01 = List.ShiftIndices(pts,List.FirstItem(-in02));


	return [Imperative]
	{
		bl01 = true;
		n = -1;
		pt11 = [];

		while (bl01)
		{
			// Shift insertion index
			pt10 = List.ShiftIndices(pt01,n);
			//Add new point to top of list
			pt11 = List.AddItemToFront(pnt,pt10);
			pg11 = Polygon.ByPoints(pt11);
			//Check Self Intersection
			it11 = pg11.SelfIntersections();
			n = n + 1;
			bl01 = List.Count(it11) != 0;
		}
		return pt11;
	}
};

// Add Closest Neighbour
def clsNgh (pnt:var[]..[])
{
	occ = pnt[0];
	avl = pnt[1];
	pg01 = Polygon.ByPoints(occ);
	ds01 = pg01.DistanceTo(avl);
	pt01 = List.SortByKey(avl,ds01)["sortedList"];
	pt02 = List.FirstItem(pt01);
	pt03 = List.RestOfItems(pt01);
	pt04 = pgnInt (occ,pt02);
	return [pt04,pt03];
};

// Repeat until all points are included
def tsp (pt01:var[]..[])
{
	ds01 = List.FirstItem(pt01).DistanceTo(pt01);
	pt02 = List.SortByKey(pt01,ds01)["sortedList"];
	pt11 = [List.TakeItems(pt02,3),List.DropItems(pt02,3)];
	return [Imperative]
	{
		a = [];
		c = List.Count(pt11[1]);
		while (c > 0)
		{
			a = clsNgh (pt11);
			pt11 = a;
			c = c - 1;
		}
		return a[0];
};
};


// Implementation on lists of Random points
n = [25,50,75,100];

pt01 = Point.ByCoordinates
(Math.RandomList(n)*8000,Math.RandomList(n)*6000);

pt02 =tsp(pt01<1>);
[pt02[0],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[0]),Color.ByARGB(255,255,0,0))];
[pt02[1],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[1]),Color.ByARGB(255,0,255,0))];
[pt02[2],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[2]),Color.ByARGB(255,0,0,255))];
[pt02[3],GeometryColor.ByGeometryColor
(Polygon.ByPoints(pt02[3]),Color.ByARGB(255,255,0,250))];
4 Likes

Thanks for this. It has worked for my script. However, how would you control which point is start point?

Use node List.ShiftIndices
image