[freeciv-ai] Re: (PR#10203) Greedy CM algorithm

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

<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 NP-complete or NP-hard problem, right?  With a map

I think it's NP-hard; 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 branch-and-bound.  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.