[Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
<URL: http://bugs.freeciv.org/Ticket/Display.html?id=12734 >
Per I. Mathisen wrote:
> <URL: http://bugs.freeciv.org/Ticket/Display.html?id=12734 >
>
> I was tired of slow AI games, so I decided to handle the root of all evil
> - the city management code. I wrote my own CM from scratch, and stuffed it
> in the bottom of city.c. At approx 300 lines of code, it is not very big.
Putting it into city.c is the wrong thing I think. It should stay in
cm.c, safely hidden behind the CM interface. If we need to change that
interface, we should. We should already change the interface a bit to
allow partial placements (placement of one new worker without
redistributing any existing ones).
> In a very difficult, very large savegame that I used for reference, CM did
> 26% better in finding optimal solutions according to the scoring test I
> made. The greedy function was, however, 154 times faster.
The current CM is exponential, more or less. A simple greedy algorithm
would be linear I think. So it will be particularly faster on large
cities. And if you can find an even larger city it will be much faster
than that.
> If you want to measure for yourself, change "#if 0" to "#if 1" in
> server/cityturn.c; if you want more comments on the design, see the huge
> function header comment on the greedy function itself.
You've made some interface changes to other parts of the code too, I
notice. Are these changes related or separate?
-jason
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation,
Jason Short <=
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation, Vasco Alexandre da Silva Costa, 2005/04/06
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation, Benoit Hudson, 2005/04/06
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation, Benoit Hudson, 2005/04/06
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation, Jason Short, 2005/04/06
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation, Per I. Mathisen, 2005/04/07
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation, Per I. Mathisen, 2005/04/07
- [Freeciv-Dev] Re: (PR#12734) A new, fast and greedy CM implementation, Per I. Mathisen, 2005/04/10
- [Freeciv-Dev] (PR#12734) calculate city's lux need, Per I. Mathisen, 2005/04/11
- [Freeciv-Dev] (PR#12734) calculate city's lux need, Per I. Mathisen, 2005/04/11
- [Freeciv-Dev] (PR#12734) quick&dirty CM v5, Per I. Mathisen, 2005/04/11
|
|