[freecivai] Re: (PR#10203) Greedy CM algorithm
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
<URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >
On Thu, Nov 18, 2004 at 05:19:50PM 0800, Jason Short wrote:
> It is close to a linear programming problem, which is easy. However
> it's actually an integer programming problem, which is hard.
LP is easy; IP in general is hard; but some IP problems are easy.
Integer network flow, for instance, is O(n^2 lg n) or somesuch
(certainly it's O(n^4); can't remember the current state of the art).
I suspect that the constraint structure of our problem makes it hard,
but I'm not sure.
I wonder if any conference would take a paper on solving the Freeciv
Tile Assignment Problem. :)
> > Things we can do to speed up the CM:
>  Call it less in the client. This is an alternative to moving it
> entirely to the server that should be feasible for 2.0.
Sending the parameters serverside is very sensical. I can see at least
one place you'd probably want the CM to be run clientside: when you set
the parameter. No point transmitting that to the server until you're
done setting.
We're already doing the CM serverside, so this seems like it should
save on total CM time, and as you point out, be far better for the
latency the user sees.
I am a strong supporter of this idea. Doubt it'll happen for 2.0 though.
> we have to decide what to do if the CM can't meet the requirements by
> placing just once citizen: does it run from scratch or give up?
There are all sorts of policy questions that I've considered:
 when to run placeone versus full
Perhaps: if the user put down the citizens, we should run
placeone ; if the user asked for the CM, we should run full.
But what do we do under placeone if the city shrank?
 under full, what if we can't meet the requirements
* just maximize the weights, ignore the requirements
* relax the requirements until we can meet them (how?)
one way: violating a constraint by x gives a charge of x^2;
you're required to minimize charge, and among solutions of
min charge, maximize fitness. (a solution that has food
surplus 2 and requirement +1 has a charge of 9, so it's
worse than a solution that has food 1 and shields
1 [charge 5]. But maybe this isn't the best idea.
But in practice it works pretty well. Another question:
how to deal with the happy requirement?)
* maybe we have a list of CM params; pick the first that we can
meet (like in auto_arrange_workers)
 under placeone, what if we can't meet the requirements
* same options as under full
* or, run full
 Benoît
 [freecivai] Re: (PR#10203) Greedy CM algorithm, (continued)
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Benoit Hudson, 2004/11/17
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Benoit Hudson, 2004/11/17
 [freecivai] Re: (PR#10203) Greedy CM algorithm, ue80@xxxxxxxxxxxxxxxxxxxxx, 2004/11/17
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/18
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Benoit Hudson, 2004/11/18
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/18
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/19
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/18
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Benoit Hudson, 2004/11/18
 [freecivai] Re: (PR#10203) Greedy CM algorithm, ue80@xxxxxxxxxxxxxxxxxxxxx, 2004/11/19
 [freecivai] Re: (PR#10203) Greedy CM algorithm,
Benoit Hudson <=
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Gregory Berkolaiko, 2004/11/19
 [freecivai] (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/22
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Benoit Hudson, 2004/11/22
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Benoit Hudson, 2004/11/22
 [freecivai] (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/23
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/23

