[freeciv-ai] Re: (PR#10203) Greedy CM algorithm

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >

On large cities the B&B algorithm performs much worse than the DP algorithm.

I'm only talking about the client here.

For instance in the game at 
http://rt.freeciv.org/Ticket/Attachment/75375/51725/jason-game.sav.gz 
(which is actually a real game of mine, unlike all the made-up games 
I've been testing with) the DP algorithm takes 0.1 seconds to 
recalculate Boston while the B&B algo takes 0.8 seconds.  Not good!

Boston is of interest because a simple greedy algorithm would easily 
give the best results.  This should be a situation where the B&B 
algorithm is very fast, I would think.  But why isn't it?

One possible reason why the DP algo is faster is because it uses 
caching.  Because the client calls CM so much more often than is needed 
cache hits are more likely I would think.

jason