by [Theo Verelst]

In short, the traveling salesman problem is a good mathematical and practical example in network or graph optimization, where one imagines a salesman, maybe with a car or a horse which 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.



[http://195.241.128.75/wiki/travsal1.jpg]

This picture is a graph in the works, which is wrong, altough 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 and increasing number, possible 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 non symmetrical 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)


----

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.

See also [Hidden Forces in the Information Technology world]