[FreecivDev] Re: Priority queue for Dijkstra
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
Hi Jason,
On Sat, 16 Mar 2002, Jason Short wrote:
> 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.
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
> 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*.
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 binarytreetype 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 priorityindexed 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.
 [FreecivDev] 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 <=
 [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

