Tengo un área que está representada por triangulaciones de delaunay restringidas. Estoy jugando con el problema de encontrar un camino entre dos puntos. Estoy utilizando el documento proporcionado por Marcelo Kallmann como punto de referencia para abordar este problema. Sin embargo, en lugar de utilizar el algoritmo de embudo Chazelle propuesto por Kallmann paper link, planeo usar el algoritmo de búsqueda A * que planifica la ruta en un entorno de cuadrícula de manera bastante eficiente.mejorando una * búsqueda para encontrar ruta en un entorno triangulado
Para la función de costo heurístico, estoy usando la distancia euclidiana del nodo actual al nodo objetivo y para seleccionar los nodos vecinos, estoy dibujando un segmento de línea desde el punto p actual hasta el punto medio del borde de triángulo [Esta idea fue propuesta por Kallmann] El costo para un nodo vecino también está dado por la distancia euclidiana entre ellos.
Aquí está la figura de Kallmann que demuestra el uso de la técnica del punto medio del borde para generar varias rutas hacia el triángulo que contiene el nodo objetivo.
Ahora esta técnica funciona bien cuando la densidad triángulo no es lo suficientemente grande en un área. Pero supongamos que si la triangulación generada para un conjunto de puntos se parece a esta
Me preguntaba si hay alguna manera de mejorar la eficacia del algoritmo utilizando alguna otra técnica como IDA * o ID-DFS. Se ha propuesto una Reducción de Triangulación A * (TRA *), pero no pude entenderla porque estaba definida de manera muy formal. Los detalles del método TRA * se pueden encontrar en la sección 5 de este thesis por Demyen.
Agradeceré algunas ideas al respecto. Si se requiere que se comparta algún código, editaré esta publicación.
Scott, la medida que estoy usando es el algoritmo que me da un camino, por ejemplo, 3 minutos en la triangulación descrita anteriormente. Porque si uso una búsqueda *, lleva años calcular la ruta. – chaitanya