[r-t] Travelling Salesman Problem

King, Peter R peter.king at imperial.ac.uk
Thu Jan 25 19:21:00 UTC 2007



Suppose lead L1 has musical score 4 whilst leads L2, L3 and L4 each have
musical score 2. It follows that attempting to include L1 would seem to be a
smart move. If, however, L1 is false with each of L2, L3 and L4 then the
inclusion of L1 adds 4 to the overall music score whilst ruling out the
score of 6 that could be contributed in total by L2, L3 and L4. If,
furthermore, the latter three leads are mutually true then the *exclusion*
of L1 is a better move.



But this is how a simulated annealing algorithm would work. You choose a sequence of leads from the graph that visits each lead once only (actually you could even ignore this and put it in by the same method of penalty functions). You then need to check for that sequence whether or not it is true. If true then give a penalty of 0 otherwise some (large no for each incidence of falseness). Now deform the sequence and repeat. If the new sequence has a lower "score" accept it  if not then only accept with a probability (which gets lower as the process continues), this way, in pricniple, you should end up with only true touches (and then use the musical score in much the same way). The point is nto to do it sequentially but rather to put forward candidate solutions for the whole sequence. I guess what I should do is write this down properly and see if it works, one day I might get the time.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 3850 bytes
Desc: not available
URL: <http://bellringers.net/pipermail/ringing-theory/attachments/20070125/d109e73a/attachment-0001.bin>


More information about the ringing-theory mailing list