Click here to Skip to main content
15,881,172 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hi all,

This isn't homework, just an illustrative example of the sort of problem I'm trying to solve:

Suppose I had a number of pots that I wanted to paint different multi-coloured designs on, and each design involves different colours that have to be painted on in the right sequence. Some designs involve the same colour twice but because of the way the colours overlap, you can't do them both at the same time, you have to maintain the order the colours are painted on.

I am looking for an algorithm to interleave the painting operations for a number of pots so that I have to wash the brush out the least number of times, i.e. so that there are the least number of colour changes from first operation to last.

Is there a standard way to do this? I've got an aging home-grown implementation that I'm updating and I'm sure it's been done before, and better!
Posted

1 solution

You may try the Simulated Annealing[^] algorithm, it is relatively simple to implement.
 
Share this answer
 
Comments
hairy_hats 23-Apr-12 13:57pm    
I used SA during my PhD - I was hoping for something more deterministic.
CPallini 23-Apr-12 14:02pm    
There's nothing more deterministic then randomness :-D.
Well, you probably know more than me about optimization algorithms, so I'm useless.
:-)
hairy_hats 23-Apr-12 14:19pm    
You're definitely not that! Thanks anyway. :)
CPallini 26-Apr-12 9:48am    
Did you already see this?
http://en.wikipedia.org/wiki/Register_allocation

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900