ulepszenie * wyszukiwania ścieżki w triangulowanym środowisku

Question

Mam obszar reprezentowany przez ograniczone triangulacje delaunay. Rozgrywam się z problemem znalezienia ścieżki między dwoma punktami. Używam papieru dostarczonego przez Marcelo Kallmanna jako punktu odniesienia do podejścia do tego problemu. Jednak zamiast używać algorytmu ścieżki Chazelle, jak zaproponował Kallmann paper link, planuję użyć algorytmu wyszukiwania A *, który planuje ścieżkę w środowisku grid dość sprawnie.

Dla funkcji kosztów heurystycznych używam odległości euklidesowej od bieżącego węzła do węzła celu i do wyboru węzłów sąsiednich, rysuję odcinek linii od bieżącego punktu p do środkowego punktu krawędzi trójkąta. [Pomysł ten zaproponował kallmann] Koszt dla sąsiedniego węzła jest również zależny od odległości euklidesowej między nimi.

Oto figura z Kallmanna demonstrująca użycie środkowego punktu techniki krawędzi do generowania różnych ścieżek do trójkąta zawierającego węzeł celu.

Teraz ta technika działa dobrze, gdy gęstość trójkąt nie jest wystarczająco duża na danym obszarze. Ale powiedz, czy wygenerowana triangulacja dla zestawu punktów wygląda tak, jakby to była

Zastanawiam się, czy istnieje sposób na zwiększenie wydajności algorytmu za pomocą innej techniki, takiej jak IDA * lub ID-DFS? Zaproponowano redukcję triangulacji A * (TRA *), ale nie mogłem jej zrozumieć, ponieważ została ona zbyt formalnie zdefiniowana. Szczegółowe informacje na temat metody TRA * można znaleźć w sekcji 5 tego dokumentu thesis firmy Demyen.

Byłbym wdzięczny za pewne przemyślenia na ten temat. Jeśli jakiś kod jest wymagany do udostępnienia, będę edytować ten wpis.

Answer 1

Należy zauważyć, że algorytmy ID zwracają koszty księgowości poniesione przez A * przez powtarzanie pracy, co potencjalnie powoduje ich spowolnienie (ale miejmy nadzieję, że niewiele wolniej). Więc jaki środek, który próbujesz poprawić wydajność, wpłynie na to, jak będą one użyteczne.