[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 12:49:53PM 0800, Jason Short wrote:
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >
> I would like to try getting a truly huge city to see if the CM is even
> feasible. This is an NPcomplete or NPhard problem, right? With a map
I think it's NPhard; I have no proof. It is close to an assignment
problem, which is easy, but it's not exactly an assignment problem.
Things we can do to speed up the CM:
 A* rather than branchandbound. This requires more space 
potentially lots more. May or may not help.
 a better lower bound on the requirements vector. Currently, we
get most of the pruning from knowing how much food we need; solutions
that can't produce enough food get pruned very early. This is
essentially what makes the BB approach faster than the DP approach in
the default ruleset. A lower bound on luxuries would also help quite
a bit on medium and large cities, but as discussed previously, this is
more complicated, so I haven't implemented it.
 a better upper bound on the quality of a solution. I have no good
ideas here. The current upper bound is that the most food you can
produce is what you'd get from taking all the best food tiles; the
most shields is what you'd get from taking all the best shields
tiles, etc. Surely we can do better?
 use the current city setup, if it's valid, as an initial solution.
I doubt this would be a major help, because of the previous point.
Currently, pretty much every solution comes up as being potentially
better than the best known: if you have one idle worker, then a real
solution can only get either 2 gold OR 2 science, whereas the upper
bound says it can get 2 gold AND 2 science.
 faster generic_city_refresh equivalent. It currently spends more than
half its time summing up the production from tiles, and half the
remainder figuring out the bonuses. But the former is already known
by the CM, and the latter is fixed within a CM invocation.
 being smarter about not calling the CM. The CM appears to get called:
1. for every changed city tile in auto_arrange_workers (multiple
times, if any invocation fails), for every changed city.
2. every time you click on a city (to get that city's dialog)
3. every time you change tab in the city's dialog
4. every time you buy a building
Least palatable:
 use an approximation: choose the first feasible solution, for example.
Or, time out after 1 second and take the best so far.
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Benoit Hudson, 2004/11/13
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Vasco Alexandre da Silva Costa, 2004/11/13
 [freecivai] (PR#10203) Greedy CM algorithm, Vasco Alexandre da Silva Costa, 2004/11/13
 [freecivai] (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/16
 [freecivai] (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/17
 [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 <=
 [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, 2004/11/19
 [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

