Complete.Org: Mailing Lists: Archives: freeciv-ai: November 2003:
[freeciv-ai] Re: (PR#6595) Optimize/reimplement CM

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: undisclosed-recipients: ;
Subject: [freeciv-ai] Re: (PR#6595) Optimize/reimplement CM
From: "Raimar Falke" <i-freeciv-lists@xxxxxxxxxxxxx>
Date: Mon, 10 Nov 2003 23:15:00 -0800
Reply-to: rt@xxxxxxxxxxx

<URL: >

On Mon, Nov 10, 2003 at 08:40:39PM -0800, Benoit Hudson wrote:
> <URL: >
> 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.


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

[Prev in Thread] Current Thread [Next in Thread]