Complete.Org: Mailing Lists: Archives: freeciv-dev: March 2002:
[Freeciv-Dev] Re: Priority queue for Dijkstra
Home

[Freeciv-Dev] Re: Priority queue for Dijkstra

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>
Cc: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra
From: Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>
Date: Sat, 16 Mar 2002 19:35:26 +0100
Reply-to: rf13@xxxxxxxxxxxxxxxxxxxxxx

On Sat, Mar 16, 2002 at 04:46:31PM +0000, Gregory Berkolaiko wrote:
> I am now hacking at the air route-finding functions, trying to adapt it to 
> AI needs.  As a blueprint of a "good" implementation I am using Raimar's 
> goto_agent code which uses a list and a hash table to hold reachable 
> tiles for Dijkstra algorithm.

> The list is sorted from time to time to find the next nearest tile.  

Before every get.

> This aroused my suspicions, since we really need a priority queue and the 
> naive implementation of a priority queue is just a list with a
> find_maximum_element function --- an O(n) algorithm.  Being a poorly 
> educated peasant boy, I didn't know how fast is qsort, but I went to the 
> big town and found a nice set of lecture notes:
>  http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/index.html
> where I am told that qsort is O(n log(n)), with a potentially large
> constant factor (plus genlist stuff on top of that).
> 
> The current implementation of priority queue in gotohand.c is actually
> O(1) --- as far as I can tell --- due to the limited set of possible
> priorities.  But it's a bit ugly.  Maybe there is a standard heap method 
> ( heap is O(log(n)) ) somewhere in C or hidden in freeciv code?

None that I know of. I found these (GPLed):
    223     864    5646 heap.c
     77     356    2206 heap.h

Do you think that a "real" priority queue performance or does it will
"only" increase readability?

> The list of priorities for planes can be bounded by map.xsize + map.ysize
> but with some potential problems.  If SINGLE_MOVE ever goes up from 3
> thought, the maximum priority for land move will increase too, so heap
> might be a good idea.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  A supercomputer is a computer running an endless loop in just a second


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