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

# [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 Cc: freeciv-dev@xxxxxxxxxxx Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra From: Raimar Falke 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]