Najszybsza ścieżka z przyspieszeniem w punktach

Question

To jest po prostu coś, co wymyśliłem sam, ale wydaje się, że jest to zabawny problem i to mnie zaskoczyło.

Masz zestaw punktów w przestrzeni dwuwymiarowej, z jednym punktem oznaczonym "Start" i jednym "Koniec". Każdy punkt ma współrzędne (w metrach od początku), ale także "numer przyspieszenia" (w metrach/sekundę delta-V). Po osiągnięciu punktu (łącznie z początkiem) możesz przyspieszyć do tego punktu liczbę przyspieszeń w dowolnym kierunku. Koszt krawędzi zależy od aktualnej prędkości, ale musisz też poruszać się we właściwym kierunku.

Czy istnieje skuteczny algorytm znajdowania najszybszej ścieżki do punktu końcowego? Nie wymyśliłem niczego lepszego niż "Wypróbuj każdą ścieżkę i sprawdź wyniki". Djikstry i inne proste algorytmy nie działają, ponieważ nie można łatwo powiedzieć, że jedna ścieżka do punktu pośredniego jest lepsza lub gorsza od innej, jeśli przybyliście z różnymi prędkościami początkowymi.

Jeśli to zbyt łatwe, a co jeśli dodasz wymóg, aby zatrzymać się w punkcie końcowym? (to znaczy, musisz mieć mniej niż wartość przyspieszenia, gdy osiągniesz koniec).

EDYCJA: Aby było jasne, kierunek ma znaczenie. Utrzymujesz wektor prędkości podczas przemierzania wykresu, a przyspieszanie oznacza dodawanie do niego wektora, którego wielkość jest ograniczona do liczby przyspieszenia tego punktu. Oznacza to, że są sytuacje, w których budowanie ogromnej prędkości jest szkodliwe, ponieważ będziesz jechać zbyt szybko, aby "sterować" w kierunku innych cennych punktów/miejsca docelowego.

Answer 1

Myślę, że wymóg, aby użyć tylko przyspieszenia z każdego punktu raz sprawia, że ​​problem NP jest kompletny w ogólnym przypadku. Rozważyć wejście, które wygląda tak:

Jeśli „ogromny dystans” między punktem końcowym a resztą punktów jest wystarczająco duża, aby zdominować koszt ostatecznego rozwiązania, znalezienie optymalnego rozwiązania będą sprowadzić się do znalezienia sposobu na pobranie jak największej liczby przyspieszeń od początku wykresu. Jeśli zezwolisz na przekazywanie tylko jednego punktu, będzie to równoznaczne z problemem ścieżki Hamiltonian, który jest NP zupełny.

Powiedziałeś, że twój problem zawiera dodatkowe zasady (odległości są euklidesowe, wykres jest zawsze kompletny), co może w końcu sprawić, że problem będzie łatwiejszy.

Answer 2

Możesz spróbować rozwiązać ten problem wstecz, rekurencyjnie śledząc ścieżki od końca do każdego innego węzła, a następnie wyznacz maksymalną prędkość wzdłuż linii, aby móc skręcić z tego węzła do dowolnego innego. Reguła usuwania będzie istniała, jeśli istnieje ścieżka od bieżącego do następnego węzła, z mniejszą prędkością i mniejszym czasem spędzonym od końca, co oznacza, że ​​druga ścieżka jest bardziej optymalna, ponieważ może dotrzeć do większej liczby węzłów i zajmuje mniej czasu. Gdy ścieżka dotrze do węzła początkowego, powinna zostać ponownie obliczona w oparciu o maksymalną prędkość możliwą do osiągnięcia na początku i przechowywaną. Potem zbierasz ścieżkę, tracąc mniej czasu.

Musisz wyszukać tutaj dowolną dostępną ścieżkę, ponieważ dostępne ścieżki na wykresie zależą od stanu przeszłego z pośrednią mechaniką, użycie mniejszej szybkości pozwala na większy wybór.