[Freeciv-Dev] Re: Priority queue for Dijkstra

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Hi Jason,

On Sat, 16 Mar 2002, Jason Short wrote:

> 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.

It is not in a fully working condition, as far as I can tell, and I run 
into some problems with it because of qsort, but it's design is quite 
interesting.  I am sure Raimar can forward you the latest copy, or I can 
share the on he sent me.

> 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.

Mmm, the one on my computer seems to be broken.  I sort an array, than 
apply compare function to few neighbours and it changes sign!
Or maybe my head is broken...

> 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*.

that's right.
it wasn't very right of me to call it "from time to time".
the easiest alternative is to run find_minimal function, which is O(n).

> > 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 :-).

I found one implementation...

> > 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?

where is _the_ existing priority queue class?
are you talking about 
  add_to_mapqueue
  get_from_mapqueue
routines?  They are just priority-indexed arrays of LILO queues (with a 
weird implementation).  This is a solid O(1) solution, unless you have too many 
indices.

> As a side note, I though planes ignored SINGLE_MOVE and just took 1 unit 
> of movement per tile?

In the SINGLE_MOVE sentence I was talking about land move.
The idea is that if you make railroads cost 1/10, the number of possible 
movecosts will be multiplied by 10 !

G.