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

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

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

Here's the branch-and-bound cm, now with auto_arrange_workers rejiggered to use 
find_first_feasible, which is essentially the greedy search, except we 
guarantee finding 
a feasible solution if there is one.  Finding the first feasible takes about a 
quarter the 
time of finding the optimal.

It includes moving cm.c to cm-old.c ; if you set COMPARE_OLD to TRUE, then 
every 
call to cm_query_result will use the branch-and-bound algorithm, but then also 
make 
sure that the dynamic programming algorithm returns an equally good solution.  
In 
normal usage, of course, this would slow you down a bunch, so you wouldn't do 
that, 
but it's very helpful for debugging.

The branch-and-bound is inconsistently faster than dynamic programming: 
sometimes
it's slightly slower, sometimes it's much faster.  It seems to do especially 
well when 
there is no way to make enough food, and on large cities.  Dynamic programming 
does especially well when the constraints are easy to achieve.  In the savegame 
attached, I see a factor of almost two time difference in favour of 
branch-and-bound.
So in the late game, branch-and-bound is a lot faster; in the early game, 
dynamic
programming seems slightly faster.  But in the early game, we don't spend much 
time
in CM.

This code prunes based on insufficient food or shields to meet the requirement, 
but
not on insufficient luxury.  That would probably speed it up a bunch.  The 
reason I
don't do it is that I don't especially want to tie the CM code too tightly in 
with the 
default ruleset, and I'm not sure how to elegantly find the required lux 
without lots
of ruleset-specific hackery.

cm_branch_bound.diff
Description: Binary data

civgame+1995.sav.gz
Description: GNU Zip compressed data