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]

 To: jdorje@xxxxxxxxxxxx Cc: freeciv-dev@xxxxxxxxxxx Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra From: Gregory Berkolaiko Date: Sat, 16 Mar 2002 17:43:36 +0000 (GMT)

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

```