miglioramento di * ricerca per trovare il percorso in un ambiente triangolato

Question

Ho un'area che è rappresentata da triangolazioni delaunay vincolate. Sto giocando con il problema di trovare un percorso tra due punti. Sto usando la carta fornita da Marcelo Kallmann come punto di riferimento per affrontare questo problema. Tuttavia, invece di utilizzare l'algoritmo di canalizzazione di Chazelle come proposto da Kallmann paper link, sto pensando di utilizzare l'algoritmo di ricerca A * che pianifica il percorso in un ambiente di griglia in modo abbastanza efficiente.

Per la funzione costo euristico, sto utilizzando la distanza euclidea dal nodo corrente al nodo obiettivo e per selezionare i nodi adiacenti, sto disegnando un segmento di linea dal punto p corrente al punto medio del bordo di triangolo. [Questa idea è stata proposta da Kallmann] Il costo per un nodo vicino è dato anche dalla distanza euclidea tra di loro.

Ecco la figura di Kallmann che dimostra l'uso del punto medio della tecnica del bordo per generare vari percorsi al triangolo contenente il nodo obiettivo.

Ora questa tecnica funziona bene quando la densità triangolo non è abbastanza grande in una zona. Ma dite se la triangolazione generata per un insieme di punti assomiglia a questo

Mi chiedevo se esiste un modo per migliorare l'efficienza dell'algoritmo utilizzando altre tecniche come IDA * o ID-DFS? È stata proposta una riduzione della triangolazione A * (TRA *), ma non ho potuto comprenderla poiché è stata definita in modo troppo formale. I dettagli del metodo TRA * sono disponibili nella sezione 5 di questo thesis di Demyen.

Gradirei qualche riflessione in merito. Se è necessario condividere un codice, modifico questo post.

Answer 1

Si noti che gli algoritmi ID compensano il costo della contabilità sostenuta da A * ripetendo il lavoro, rendendolo potenzialmente più lento (ma si spera non molto più lento). Quindi, quale misura stai cercando di migliorare l'efficienza influirà sulla loro utilità.