I tried to implement the TSP -2Opt algorithm, follwong these steps here : https://en.wikipedia.org/wiki/2-opt
it is working so far(no line crossings), its just not returning to te start position.
private void RunScript(List<Point3d> pts, int its, ref object A)
{
List<Point3d> existingRoute = new List<Point3d>(pts);
existingRoute.Add(pts[0]);
for (int it = 0; it < its; it++)
{
double bestDistance = getDistance(existingRoute);
for (int i = 1; i < existingRoute.Count - 1; i++)
{
for (int k = i + 1; k < existingRoute.Count; k++)
{
List<Point3d> newRoute = swap(existingRoute, i, k);//swap
double newDistance = getDistance(newRoute);
if(newDistance < bestDistance)
{
existingRoute = newRoute;
bestDistance = newDistance;
}
}
}
}
A = existingRoute;
}
// <Custom additional code>
public double getDistance (List<Point3d> pts)
{
double d = 0;
for (int i = 0; i < pts.Count - 1 ; i++)
{
double newDist = pts[i].DistanceTo(pts[i + 1]);
d += newDist;
}
return d;
}
public List<Point3d> swap(List<Point3d> route, int i, int k)
{
var swapped = new List<Point3d>();
//1. take route[0] to route[i-1] and add them in order to new_route
for (int c = 0; c < i - 1; c++)
swapped.Add(route[c]);
// 2. take route[i] to route[k] and add them in reverse order to new_route
for ( int c = k; c-- > i - 1 ; )
swapped.Add(route[c]);
// 3. take route[k+1] to end and add them in order to new_route
for ( int c = k; c < route.Count; c++ )
swapped.Add(route[c]);
return swapped;
}
Maybe someone sees the error.
Also any tips about optimizing are welcome.
File:20200614_TSP.gh (5.9 KB)
Thanks everybody!
private void RunScript(List<Point3d> pts, int its, ref object A)
{
var existingRoute = new Polyline(pts){pts[0]};
for (var it = 0; it < its; it++)
{
var bestDistance = existingRoute.Length;
for (var i = 1; i < existingRoute.Count - 1; i++)
for (var k = i + 1; k < existingRoute.Count; k++)
{
var newRoute = swap(existingRoute, i, k);
var newDistance = newRoute.Length;
if (newDistance >= bestDistance) continue;
existingRoute = newRoute;
bestDistance = newDistance;
}
}
A = existingRoute;
}
// <Custom additional code>
Polyline swap(Polyline route, int i, int k)
{
var swapped = new Polyline();
//1. take route[0] to route[i-1] and add them in order to new_route
for (int c = 0; c < i - 1; c++)
swapped.Add(route[c]);
// 2. take route[i] to route[k] and add them in reverse order to new_route
for ( int c = k; c-- > i - 1 ; )
swapped.Add(route[c]);
// 3. take route[k+1] to end and add them in order to new_route
for ( int c = k; c < route.Count; c++ )
swapped.Add(route[c]);
swapped.Add(swapped[0]);
return swapped;
}
// </Custom additional code>
private void RunScript(List<Point3d> pts, int n, ref object A)
{
pts.Add(pts[0]);
var route = pts.ToArray();
var shortest = Length(route);
for (var k = 0; k < n; k++)
for (var i = 1; i < route.Length - 1; i++)
for (var j = i + 1; j < route.Length; j++)
route = Swap(route, ref shortest, i, j);
A = route;
}
// <Custom additional code>
double Length(Point3d[] route)
{
var d = 0.0;
for(var i = 0; i < route.Length - 1; i++)
d += route[i].DistanceTo(route[i + 1]);
return d;
}
Point3d[] Swap(Point3d[] route, ref double shortest, int i, int j)
{
var swapped = (Point3d[]) route.Clone();
Array.Reverse(swapped, i, j - i);
var len = Length(swapped);
if (len < shortest)
{
shortest = len;
return swapped;
}
return route;
}
// </Custom additional code>
Python:
def length(pts):
d = 0.0
for i in range(len(pts) - 1):
d += pts[i].DistanceTo(pts[i + 1])
return d
def swap(route, shortest, i, j):
swapped = route[:i]+route[i:j][::-1]+route[j:]
len = length(swapped)
if len < shortest:
return swapped, len
return route, shortest
pts.append(pts[0])
route = pts
shortest = length(route)
for k in range(n):
for i in range(1, len(route) - 1):
for j in range(i+1, len(route)):
route, shortest = swap(route, shortest, i, j)
a = route
