[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 08:57:16PM 0800, Benoit Hudson wrote:
>
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >
>
> On Thu, Nov 18, 2004 at 06:07:30PM 0800, Jason Short wrote:
> >
> > <URL: http://rt.freeciv.org/Ticket/Display.html?id=10203 >
> >
> > On large cities the B&B algorithm performs much worse than the DP algorithm.
> >
> > I'm only talking about the client here.
> >
> > For instance in the game at
> > http://rt.freeciv.org/Ticket/Attachment/75375/51725/jasongame.sav.gz
> > (which is actually a real game of mine, unlike all the madeup games
> > I've been testing with) the DP algorithm takes 0.1 seconds to
> > recalculate Boston while the B&B algo takes 0.8 seconds. Not good!
>
> Really? I'm surprised, because usually large cities have stringent
> demands on food, which means the vast majority of solutions the DP
> algorithm dreams up are pruned out.
>
> By the way, what's the CMA settings? The gui (gtk2) isn't very good
> about custom CMA settings: when I switch to the CMA tab, it decides to
> apply the first setting in my list. Which makes it harder to debug.
>
> > One possible reason why the DP algo is faster is because it uses
> > caching. Because the client calls CM so much more often than is needed
> > cache hits are more likely I would think.
>
> Cache hits are more likely, but that doesn't explain the dependence on
> city size. What might explain half of it  and this is a guess, is
> that under the B&B code, half the CM time is spent iterating over the
> tiles and doing base_city_get_food_tile and so on. As the city grows,
> that fraction would grow since it's doing it on more tiles whereas the
> other work in generic_city_refresh will be equal. The DP doesn't pay
> for this thanks to the cache.
>
> For small cities, the ratio of work per generic_city_refresh of DP / BB
> is about 1 / 2. We end up with BB being slightly faster because it does
> a lot less (about half as many) generic_city_refresh.
>
> For large cities, the ratio would be more like 1 / 5. This means the DP
> should be faster by a factor of two if they have the same ratio of
> generic_city_refresh calls.
>
> So I've explained why BB should be expected to take .2 or .3 seconds.
I have not looked into the code so i don't know if my following
suggestion is allready implemented.
What is about first group all tiles into the possible gains for the
city.
2/2/1 4 times
2/1/2 2 times
1/0/0 4 times
And doing the algorithm afterwards.
For a size 5 city it's possible to remove the 4 times 1/0/0 because
there is no optimal solution with it because all other tiles are
better.
And i have to think if:
max f_1 * a1 * t1_1 + f_2 * a1 * t1_1 ...
where sum a1 ... an <= citysize
a1 * t1_1 ... an* tn_1 >= needed food
... prod
... lux
with f_1 .. f_n weights for CM
a1 .. an number of fields in citymap
tx_1 .. tx_n gain for food,prod,lux
is a NP problem ... but i don't think so.
Thomas

Thomas Strub *** eMail ue80@xxxxxxxxxxxxxxxxxxxxx
jb: people are stupid, they don't want to learn.
 [freecivai] (PR#10203) Greedy CM algorithm, (continued)
 [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, 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 <=
 [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, 2004/11/23
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/23

