[freeciv-ai] Re: (PR#6595) Optimize/reimplement CM
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
<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.
"Python is executable pseudocode. Perl is executable line noise"
-- Bruce Eckel
- [freeciv-ai] Re: (PR#6595) Optimize/reimplement CM,
Raimar Falke <=