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: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Priority queue for Dijkstra
From: Jason Short <vze2zq63@xxxxxxxxxxx>
Date: Sat, 16 Mar 2002 12:06:50 -0500
Reply-to: jdorje@xxxxxxxxxxxx

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


[Prev in Thread] Current Thread [Next in Thread]