I’ve implmented several TSP heuristics in Python too.

Here the source code is:

https://github.com/ntrifunovic/TSP

Screenshots of program are availabale at: http://ntrifunovic.github.io/projekti/tsp/

]]> Maximize Z = 2(X1) – (X1)^2 +3(X2) – 3(X2)^2

subject to:

x1 + x2 ≤ 0.75

and each variable is restricted to take the following values: 1/2, 1/3, 1/4, 1/5

This is a discrete nonlinear problem.

I see after my previous comment was posted, that it was formatted such that my path diagram didn’t show up right. The path should form the outline of a block letter ‘m’.

]]>One interesting caveat of all four equations is that they cannot find the optimum path for a 6×6 square of points, where the points are laid out in a square so that the minimum distance between each point and it’s nearest neighbors is 1. When you try to find a route via your intuition, it’s shorter than any of the 4 listed:

My Path (‘x’ is a point, ‘-‘ or ‘|’ are connections)

x – x – x – x – x – x

| |

x x – x x – x x

| | | | | |

x x x x x x

| | | | | |

x x x x x x

| | | | | |

x x x x x x

| | | | | |

x – x x – x x – x

(Value from my math)

Intuitive Distance*: 1900

(Value From Applet)

Next neighbor: 2058

nearest Insert: 1926

Farthest Insert: 2222

Cheapest Insert: 1968

I’m not really a phenomenal mathematics guy, so I probably violated one of the rules of the problem; but I think it’s still an interesting result.

Thanks for publishing the applet! It’s really cool!

– Anonymous Student

]]>thanks for the code.

]]>in mathematic you would do it making the distance between these points infinite. but how do you do it in your library?¿ ]]>

No I have not. This is my first blog and I so far I have not posted in other blogs. ]]>