Complete.Org: Mailing Lists: Archives: freeciv-ai: November 2004:
[freeciv-ai] Re: (PR#10203) Greedy CM algorithm

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: per@xxxxxxxxxxx
Subject: [freeciv-ai] Re: (PR#10203) Greedy CM algorithm
From: "Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>
Date: Thu, 18 Nov 2004 18:07:30 -0800
Reply-to: rt@xxxxxxxxxxx

<URL: >

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 
(which is actually a real game of mine, unlike all the made-up 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.


[Prev in Thread] Current Thread [Next in Thread]