Komiwojażer z przeszkodami

Witam.

Poszukuję pomysłów na algorytm, który wyznaczy optymalną trajektorię dla robota który ma dotrzeć do n zadanych punktów (najlepiej w przestrzeni), tyle że po drodze mogą znajdować się przeszkody.

Algorytmów na wyznaczanie najkrótszej trasy z jednego punktu do drugiego z przeszkodami po drodze jest sporo, więc można by wyznaczyć takie trasy między wszystkimi punktami i potem rozwiązywać problem komiwojażera, z tym że uzyskany zbiór torów nie będzie grafem (bo tory nie będą prostoliniowe), więc może okazać się np: że mimo że teoretycznie optymalny jest ruch z punktu n₁ do punktu n₂ to tak naprawdę tor omijający przeszkodę zbliża się bardzo do punktu n₃ i należało by go odwiedzić.

Postępowanie odwrotne (najpierw komiwojażer, potem omijanie przeszkód) budzi podobne zastrzeżenia.

Jedynym w miarę sensownym rozwiązaniem do jakiego doszedłem to próba użycia "koloni mrówek", ale obawiam się, że złożoność obliczeniowa tego algorytmu dla przedstawionego problemu będzie nieadekwatna do jakości otrzymanego wyniku (który, może okazać się zupełnie nieoptymalny.

Będę wdzięczny za wszelkie wskazówki, pomysły, linki... jakąkolwiek radę :)

Pozdrawiam

zastanów się w jaki sposób będą podane przeszkody, warto by te przeszkody ominąć w bezpiecznej odległości, więc wyszukanie najkrótszej drogi nie koniecznie musi się sprawdzić

możesz np. w uproszczeniu wygenerować siatkę punktów w równo oddalonych odstępach i po prostu nie dorzucać punktu do grafu jeśli znajduje się wewnątrz przeszkody. wierzchołki grafu to te punkty, połączenia między wierzchołkami są zawsze z sąsiednimi punktami + punktami po skosie, do znalezienia połączeń dijikstra, jak będzie za wolne to zwiększasz odległości między punktami.

wg. mnie najpierw zaimplementuj, żeby te wierzchołki przeszedł w podanej kolejności a potem kombinuj z komiwojażerem.

Najlepiej byłoby zrobić z tego graf ważony(wydaje mi się że można wtedy pominąć fakt znajdowania się przeszkody, gdyż ta informacja ma znaczny Wplyw na odleglosc czyli nasza wage) i spróbować podać rozwiazanie np. za pomocą takiego algorytmu: edu.i-lo.tarnow.pl/inf/utils/002_roz/ol027.php
niestety ten algorytm ma złożoność wykładnicza.