Traveling Salesman Problem

by Theo Verelst

In short, the traveling salesman problem is a good and classical mathematical and practical example in network or graph optimization, where one imagines a salesman, maybe with a car or a horse, who needs to visit a set of customers, and wants to take the shortest route.

We could take a map, draw circles around every destination city, draw lines between all reasonable adjacent or all next cities, and look up or measure the distance between pairs of cities, and write them in kilometers along all connecting lines.

Then we give the thus constructed graph to computer wizard, and tell him or her to solve the problem.

This picture is a graph in the works, which is wrong, although it is getting there. Can you spot the error in the code?

I agree this is like motherfucking code together, but so what; it is fun and relevant.

This procedure generates a list of names made of a base name prepended with an increasing number, possibly with an offset:

 proc gennames {{name proc} {n 10} {imin 0}} {set o {} ; for {set i $imin} {$i < $imin + $n} {incr i} {append o " $name$i"} ; return $o }

The blocks were made in Bwise like this:

 set bls {}; append bls [eval [pro_args newproc "{in {[gennames i 5]}} {out {[gennames o 5]}}"]]

 append bls " " [eval [pro_args newproc "{in {[gennames i 5]}} {out {[gennames o 5]}}"]] 

The last line is repeated 5 times, to generate 6 blocks in total.

I arranged the blocks in circular order, with a bit of an initial angle offset to make the graph nonsymmetrical by moving the blocks:

 set j 0; for {set i [expr 0.0+2.0*3.14159/24.0]} {$i < [expr 2*3.14159]} {set i [expr $i + 2.0*3.14159/6]} {$mc move [lindex $bls $j] [expr (200+150*cos($i))] [expr (200-150*sin($i))] ; incr j}

This is how the connections were drawn in:

 set wi 0; set oo 0 ;foreach i [lrange $bls 1 end] {set oi 0; foreach j $bls { if {$i != $j} {connect ww[incr wi] $j o$oo $i i$oi ; incr oi} } ; incr oo}

(Which is at this moment wrong)

Still in this wrongly (or imcompletely) connected version, we get the following connections from inspecting the graph structure through the netlistout Bwise command:

 % netlistout
 {Proc1 o0 Proc2 i0} {Proc1 o1 Proc3 i0} {Proc1 o2 Proc4 i0} {Proc1 o3 Proc5 i0} {Proc1 o4 Proc6 i0}
 {Proc2 o1 Proc3 i1} {Proc2 o2 Proc4 i1} {Proc2 o3 Proc5 i1} {Proc2 o4 Proc6 i1} {Proc3 o0 Proc2 i1}
 {Proc3 o2 Proc4 i2} {Proc3 o3 Proc5 i2} {Proc3 o4 Proc6 i2} {Proc4 o0 Proc2 i2} {Proc4 o1 Proc3 i2}
 {Proc4 o3 Proc5 i3} {Proc4 o4 Proc6 i3} {Proc5 o0 Proc2 i3} {Proc5 o1 Proc3 i3} {Proc5 o2 Proc4 i3}
 {Proc5 o4 Proc6 i4} {Proc6 o0 Proc2 i4} {Proc6 o1 Proc3 i4} {Proc6 o2 Proc4 i4} {Proc6 o3 Proc5 i4}

The idea is overseeable enough: that each block connects one of its outputs to some input of all other blocks, so we get all possible routes by taking different outputs every time, and progressing through the graph.

For a graph with N nodes, there are N-1 other nodes for each node, which require N-1 connections and N-1 outputs, and because one can arrive at every node from N-1 other nodes, there are also N-1 inputs. The number of connections for N nodes is thus N * (N-1), in this case 6 * 5 = 30. Currently, there are 25, this suggests we miss the 'wrapping around' from node 5 to 0 or something.

Note that the 'connect' command (see bwise page) can easily be reversed: connecting any two pins twice the same way unconnects them again. So by calling the last command to create the links twice, the (wrong) links are removed again.

I scaled the above block spreading lines and set the circular angle offset to zero, this is not so hard when one gives the two scaling transforms a minus sign and actives them again, then the blocks end up back in the upper left corner again, after which they can be scaled and put in circle again.

Then I used GIMP to scale down a windowdump of the result:

which clearly shows the familiar fully connected structure as overall idea of this all-routes connection diagram.

Is there a point? Of course, it is at least a definition of the tsm problem in correct bwise blocks, and it might draw me to make some more fire rules in bwise, and make some more network/graph related procedures.

And it is fun to put certain parties in place with. The complexity of the problem is of order faculty N, which leaves us in major computational problems even for all names on the first page of the phonebook.