[r-t] Travelling Salesman Problem

[King, Peter R]

The problem of peal composition is,as you say, slightly different from
the classical TSP. It is more like a problem of a salesman who wants to
make a journey of a certain length and he has to work out which cities
to visit. 

Put in a more change ringing language. You have a graph of all leadheads
each of which is connected to 3 others (assuming the only calls allowed
are plain, bob or single). This is fairly standard. You then want to
find a closed loop of a certain length (eg around 160 nodes long for a
standard length peal of surprise major) subject to the constraint that
i) you never visit the same node twice and ii) visiting certain nodes
prohibits you from visiting some others (because of falseness). I don't
know but I presume most composition generators use some kind of directed
random walk but with an algorithm like simulated annealing you would
simply put down a closed loop randomly (possibly ignoring all the
constraints and apply a penalty function against them) and then anneal
away until the constraints are honoured.

You could easily add to your objective function requirements for music
(such as maximising a row count of desired combinations by giving the
nodes values corresponding to the number of musical rows in that lead).
I would have thought that this is quite doable and probably realtively
coputationally easy. I haven't done this although I have solved what I
think are harder problems quite efficiently using SA and GA methods.

> -----Original Message-----
> From: ringing-theory-bounces at bellringers.net 
> [mailto:ringing-theory-bounces at bellringers.net] On Behalf Of 
> Ian Broster
> Sent: 24 January 2007 15:32
> To: ringing-theory at bellringers.net
> Subject: Re: [r-t] Travelling Salesman Problem
> 
> 
> > There are also all sorts of other algorithms for solving 
> the travelling
> > salesman problem
> 
> Yes, I have use used one such library for composing 
> call-change sequences,  
> which is much closer to the TSP than composing peals is. Full 
> details are  
> online:
> 
http://www-users.cs.york.ac.uk/~ianb/cgi-bin/callcompose

Ian




-- 
Ian Broster

_______________________________________________
ringing-theory mailing list
ringing-theory at bellringers.net
http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net