Complete.Org: Mailing Lists: Archives: freeciv-ai: April 2003:
[freeciv-ai] Re: [RFC] Ferry code proposal v.2

[freeciv-ai] Re: [RFC] Ferry code proposal v.2

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: Freeciv AI development <freeciv-ai@xxxxxxxxxxx>
Subject: [freeciv-ai] Re: [RFC] Ferry code proposal v.2
From: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>
Date: Sun, 6 Apr 2003 22:29:09 +0100 (BST)

On Sun, 6 Apr 2003, Jason Dorje Short wrote:

> Gregory Berkolaiko wrote:
> > Here is another proposal for the ferry code.  It is influenced by Raimar's 
> > and Jason's insistence on considering all coastal tiles.
> > 2. We make a big map for U to go to all coastal tiles T1 on 1 where it
> > will spend FAM(T1) - Walk_Time(T1) turns waiting, then from each T1 we
> > calculate paths to all coastal tiles of continent 2, from all coastal
> > tiles we calculate all paths to Z.  This calculation is also O(1).
> I don't think this is O(1).  If you have to calculate the PF map from 
> every coastal tile of 1 to every coastal tile of 2, that should be O(n) 
> (n == # of coastal tiles of 1).  Unless you cache this information?

Can be done O(1).  Instead of having 1 initial position, push n initial 
positions into the priority queue at the start of the algorithm and 
calculate 1 map.


P.S. Why do we have to approve Jason's posts?  Isn't he subscribed to 

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