[Freeciv-Dev] Re: Priority queue for Dijkstra

[Jason Short <vze2zq63@xxxxxxxxxxx>]

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.
Hmm, I have not seen this code.

> The list is sorted from time to time to find the next nearest tile.  
> 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).
quicksort is fast - O(n log n) in the average case, with a *small* 
constant factor (compared to other n log n sorts); the drawback is that 
it can be O(n^2) in the worst case (when everything is in the exact 
wrong position).  What the "wrong position" is depends on the 
implementation of the quicksort; the standard qsort() function probably 
avoids the most likely cases.
But, any kind of sort is definitely inferior to a priority queue.  A 
well-designed queue has a O(log n) insert time, and a small constant 
factor.  There is little overhead and it is ammortized well.  By 
contrast, implementing Dijkstra's correctly requires that the list 
*always* be sorted, because each element you pop off must be the 
smallest one.  So to ensure correctness you'd really need to sort the 
list *every time you popped an item*.
> 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?
No doubt there is some kind of heap or other binary-tree-type structure 
down there somewhere.  If not, I'm pretty sure somebody needs to be 
published :-).
> 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.
A heap is a good idea in any case - especially since such a structure 
has already been implemented, has it not?  Can't you just use the 
existing priotiry queue class?
As a side note, I though planes ignored SINGLE_MOVE and just took 1 unit 
of movement per tile?
jason