[freeciv-ai] Re: (PR#6595) Optimize/reimplement CM

["Raimar Falke" <i-freeciv-lists@xxxxxxxxxxxxx>]

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

On Mon, Nov 10, 2003 at 08:40:39PM -0800, Benoit Hudson wrote:
> 
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=6595 >
> 
> I've been looking at the CM code the past couple days, trying to get it
> to do my bidding.  While I failed at that, I can say the following:
> 
> (1) The current implementation of the CMA uses a dynamic programming
> formulation.  This is a standard optimization technique.  Also, it
> prunes the solution space fairly aggressively (while still guaranteeing
> a correct answer).
> 
> (2) Integer programming is NP-hard, while linear programming is
> poly-time.  Solving an IP by LP rounding is a very common approximation
> technique; probably we can (with a bit of work) discover it's a 2-approx
> or the like in this case.
> 
> Basically, it seems to me that the CMA is fast enough at the moment that
> I'm willing to occasionally wait a little (on my 500 MHz Pentium III)
> for it to get the optimal answer (for a weak definition of optimal).

> It should be possible to speed it up using the caches: cache3 could be
> an array indexed by city id; and we could start off with a check of
> whether the city has changed in any way since we last optimized (are all
> production values the same, and all the land is the same, same number of
> citizens, same tiles open, ...).  If so, start from scratch.  This would
> speed up buying buildings, for instance.

Yes it is possible. It will however increase the memory usage. Note
that cache3 is 705kb.

> Doing an incremental update of the CMA solution would probably be rather
> harder, but might allow for even more speedup.

Improvements are always welcome.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Python is executable pseudocode. Perl is executable line noise"
    -- Bruce Eckel