[freecivai] (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 >
> [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 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.
>  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 34 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
 [freecivai] Re: (PR#10203) Greedy CM algorithm, (continued)
 [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
 [freecivai] (PR#10203) Greedy CM algorithm,
Jason Short <=
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/23

