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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >

> [bhudson - Fri Nov 19 00:48:19 2004]:
> 
> 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.

> - 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?

I think this is the biggest problem.

It should be easy enough to calculate the fitness of the production
output provided by a particular tile type.  We already calculate an
*estimated* fitness.  Can we calculate a *maximum* fitness?  If so it
should be easy to filter based on that.  See PR#11156.

Attached is the savegame containing Boston.  Boston may actually be a
fairly simple city because most of its tiles are ocean.  However with a
little transformation it could be grown 3-4 more citizens providing a
possibly harder problem.  The CM preset I've given it has -20 minimal
food and gold with factor of 20/5/0/1/0/1/1.  (-20 minimum food is used
to avoid problems when a tile or two becomes polluted.  I realize this
makes pruning based on food much less useful.)

jason

cm.sav.gz
Description: Unix tar archive