[FreecivDev] Re: Priority queue for Dijkstra
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
Gregory Berkolaiko wrote:
I am now hacking at the air routefinding 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
welldesigned 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 binarytreetype 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
 [FreecivDev] Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra,
Jason Short <=
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16

