algorithm - recorrido - camino mas corto grafos java
¿Dónde puedo encontrar información sobre el algoritmo de determinación de ruta D*o D*Lite? (5)
Aquí hay enlaces a algunos documentos en D *, pero son demasiado matemáticos para mí. ¿Hay alguna información sobre D * / D * Lite más orientada a los principiantes?
Bueno, si el pseudocódigo es difícil para ti (no tienes que leer teoremas y pruebas, el pseudocódigo es bastante directo si conoces los algoritmos estándar) y te quejas de los códigos C y C ++ publicados, entonces supongo que tendrás que irte. haciendo otra cosa :-)
En serio, no esperes que alguien te pueda enseñar un algoritmo de máxima calidad en algunos párrafos web. Tome un bolígrafo y papel y escriba, dibuje y siga en papel lo que está sucediendo. Puede que tenga que leer algo dos veces y buscar en Google una o dos referencias para conocer algunos conceptos a su alrededor, y no hay necesidad de profundizar en los teoremas y pruebas, a menos que espere probar que el autor está equivocado :-) )
No puedo seguir adelante sin un poco más de matemáticas - c''est la vie. Imagina que le pides a alguien que te enseñe qué es la inversión de matrices, pero no sabes qué son vectores. Nadie podría ayudarlo hasta que haya aprendido lo suficiente sobre el contexto matemático primero.
Habiendo dicho eso, ¿por qué no agregar algunos documentos más? Sí, también tienen matemática :-) pero intentaré obtener algunas más recientes. La gente generalmente mejora al explicar su propio trabajo a medida que pasa el tiempo, por lo que el foco está en Stentz, Likhachev y Koenig.
- Stentz, 2007 - Campo D * - dice ser mejor que D * Lite :-)
- Stentz, 2010 - Imitación de Lerning : habla principalmente sobre la combinación de Field D * y LEARCH
- Ratliff, 2009 - LEARCH - también habla de combinar con Field D * - sí, una referencia cíclica :-)
- Likhachev, 2005 - En cualquier momento D * - con Stentz también
- Yanyan, 2009 - Dinámico A basado en BDD *
- Koenig, 2008 - Comparación de búsqueda heurística incremental y en tiempo real
Se me ocurrió esto
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf y esto
http://www.cs.cmu.edu/~maxim/docs/dlitemap_iros02.pdf
Espero que ese enlace te ayude :)
Editar: Después de publicar noté que los enlaces que te di estaban en el enlace que también indicaste. Sin embargo, los encontré directamente en Google. De todos modos los he buscado un poco y no parecen ser tan complicados. Si conoces bien A *, también debes entender D *.
Por experiencia, puedo decirte que A * también puede usarse para lo que quieras.
Wikipedia tiene un artículo sobre el tema: http://en.wikipedia.org/wiki/D*
También una implementación D * Lite en C está disponible en la página de Sven Koenig: http://idm-lab.org/code/dstarlite.tar Sin embargo, encuentro que la matemática impenetrable es mucho más fácil de leer que el código fuente C ;-)
Otra implementación de D * Lite (en C ++) está disponible aquí: http://code.google.com/p/dstarlite/
D * Lite Explicación para el Laico
D * comienza con un camino idealista entre el Start y el Goal ; maneja los obstáculos solo cuando los encuentra (usualmente moviéndose a un nodo adyacente). Es decir: D * Lite no tiene conocimiento de ningún obstáculo hasta que comienza a moverse a lo largo de ese camino ideal.
El Santo Grial con cualquier implementación de pathfinding es hacer que sea rápido al obtener el camino más corto, o al menos un camino decente (así como el manejo [todas sus diversas condiciones especiales aquí - para D * Lite se trata de un mapa desconocido como un Mars Rover podría hacer]).
Entonces, uno de los grandes desafíos de D * Lite es adaptarse a los obstáculos a bajo costo a medida que se alcanzan. Encontrarlos es fácil: simplemente verifica el estado del nodo de los vecinos mientras te mueves. Pero, ¿cómo adaptamos las estimaciones de costos del mapa existente sin recorrer todos los nodos ... lo que podría ser muy costoso?
LPA * usa un ingenioso truco para adaptar los costos, un truco que D * Lite ha dado buen uso. El nodo actual pregunta a sus vecinos: usted me conoce mejor, ¿cree que soy realista acerca de mí mismo? Específicamente, pregunta esto sobre su valor g , que es el costo conocido de obtener desde el nodo inicial a sí mismo, es decir, el nodo actual. Los vecinos miran su propio g , miran dónde está el nodo actual en relación con ellos, y luego ofrecen una estimación de lo que creen que debe ser su costo. El mínimo de estas ofertas se establece como el valor rhs del nodo actual, que luego se usa para actualizar su valor g ; al estimar, los vecinos toman en cuenta el (los) obstáculo (s) recientemente descubierto (s) (o espacios libres), de modo que cuando las actualizaciones actuales g usan rhs , lo hacen con los nuevos obstáculos (o espacios libres) contabilizados.
Y una vez que tenemos valores realistas de g todos los ámbitos, por supuesto, aparece una nueva ruta más corta.