Traveling Salesman

I wrote a computer program that tries to find a Hamilton Circuit , which is given a bunch of "cities" try to find a path that visits every city and ends back up where you start. Each city is connected to some of the other cities with roads. So to start out with your map might look like this:

It's kind of a mess, right? You might be able to tell from looking at it the path that solves the problem but it's one of those things that is easier for a human than a computer. So I wrote this program that as step 1 randomly puts these cities on a circle evenly spaced all around. Like so:

You can see that 7 is not connected to it's immediate neighbors so what my algorithm does is it goes through point by point and tries to move each point towards the other points it's connected to, and away from the ones that it's not connected to. So imagine that these points are going around the circle in different directions trying to get away from the ones they're not connected too and towards the ones that they are connected to. 

It finally reaches equilibrium where it can't seem to do any better and that is this final graphic...

 When the program is finished the points aren't evenly spaced around the circle like above but it was too hard trying to get it to output exactly like the program does. So imagine they are in this order but a little bit randomly spaced around the circle. Anyway the thing to notice is now there is a path all the way through all the points that visits every one and ends up back at the beginning (it's drawn as a circle). You can sort of tell by looking at it that paths all the way across the circle are unfavorable.

The interesting thing is this program does this really fast, it only had to move each point on the circle a certain amount 50 times, which sounds like a lot if you're doing it by hand but it is nothing to the computer. 

 Here is the source code to the program: 

import math

def distance(posa, posb):

    delta = posa-posb

    delta2 = posb + 360-posa

    

    if delta2 < delta:

        delta = -delta2

    if abs(delta) == 180:

        return 0

    if delta <= 0:

        if delta < -180:

            return delta%180

        else:

            return delta

            

    else:

        if delta > 180:

            return delta%180

        else:

            

            return delta

def potential(point, graph, pos):

    sum = 0

    for i in range(0, len(graph[point])):

        sum+= distance(pos[graph[point][i]], pos[point])

    all = set(range(0, len(graph)))

    n = set(graph[point])

    nc = list(all - n)

    for i in range(0, len(nc)):

        d = distance(pos[nc[i]], pos[point])

        if d < 0:

            d = 180+d

        else:

            d = 180-d

        sum-= d

    return sum    

def move(steps, graph, pos):

    for s in range(0, steps):

        for i in range(0, len(graph)):

            p = potential(i, graph, pos)

            

            if p > 0:

                if (pos[i]+int(round(p/10.0))) <360:

                    pos[i] +=int(round(p/10.0))

                else:

                    pos[i] += int(round(p/10.0))

                    pos[i] -= 360

            if p < 0:

                if (pos[i]+int(round(p/10.0))) >= 0:

                    pos[i] +=int(round(p/10.0))

                else:

                    pos[i] += int(round(p/10.0))

                    pos[i] = 360+pos[i]

def main():

    graph = [[1,2,5,8,9],[0,2,7],[0,1,3, 9], [2,4, 5, 6], [3, 6, 7], [0,3, 6, 8], [3, 4, 5, 8], [1,4], [0,5,6,9], [0,2,8]]

    pos = [0, 36, 72, 108, 144, 180, 216, 252, 288, 324]

    move(50, graph, pos)

    print(pos) 

main()