[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 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!
Boston is of interest because a simple greedy algorithm would easily
give the best results. This should be a situation where the B&B
algorithm is very fast, I would think. But why isn't it?
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.
jason
 [freecivai] (PR#10203) Greedy CM algorithm, (continued)
 [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, 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 <=
 [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, 2004/11/23
 [freecivai] Re: (PR#10203) Greedy CM algorithm, Jason Short, 2004/11/23

