[FreecivDev] Re: Priority queue for Dijkstra
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
On Sat, Mar 16, 2002 at 04:46:31PM +0000, Gregory Berkolaiko wrote:
> I am now hacking at the air routefinding 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
 [FreecivDev] Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra,
Raimar Falke <=

