(PR#10203) Greedy CM algorithm

"Benoit Hudson" <bh-0/DuvcfrMH9wGe/[email protected]>
Newsgroups gmane.games.freeciv.ai
Message-ID <[email protected]>
<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 (application/octet-stream, 163.5 KB) - not displayed
civgame+1995.sav.gz (application/x-gzip, 122.5 KB) - not displayed
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.