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

## No comments:

## Post a Comment