Re: Implementing the Dijkstra Algorithm
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Implementing the Dijkstra Algorithm
- From: "Mark Meijer" <meijer78@...>
- Date: 2005年11月23日 12:48:56 +0000
FYI - Clicking through one of the external links given on wikipedia's A*
page, I found the following information about A* variations, including the
aforementioned D*:
http://theory.stanford.edu/~amitp/GameProgramming/Variations.html#S6
There are also some links there to related papers, and if I remember
correctly, the same paper I mentioned in my previous response is linked to
here (it's in postscript format, if you don't have a PS viewer you might
want to do a google search for ghostview). Have a look if you're interested.
Greets,
Mark
From: "Mark Meijer" <meijer78@hotmail.com>
Reply-To: Lua list <lua@bazar2.conectiva.com.br>
To: lua@bazar2.conectiva.com.br
Subject: Re: Implementing the Dijkstra Algorithm
Date: 2005年11月23日 11:03:13 +0000
On a side note, as also suggested on that wikipedia page, and depending on
what exactly you are using the algorithm for, you might want to consider
using the A* algorithm instead. Or perhaps another variant dubbed the D*
algorithm, where the shortest path found can be dynamically updated
"en-route" in real-time (i.e. while actually travelling) as circumstances
might change over time. I found a research paper about this once, I could
email it to you if you like, just let me know. The algorithm was designed
to be implemented on robots for navigation, and I'm sure it could be useful
for other applications as well, such as games and simulations.