Programowanie dynamiczne (dojść z (0,0) do (a,b) najkrótszą drogą n wektorami)

Witam,
Mam do rozwiązania problem za pomocą programowania dynamicznego, w którym to...

Startuję z miejsca (0,0) i mam dojść do miejsca (a,b), gdzie a=b, czyli np. do miejsca (2,2) lub (3,3) lub (4,4) lub (5,5) itd...

Moje ruchy są zdefiniowane poprzez określone przez użytkownika n dowolnych wektorów np. dla n=3 mam:
v1 = (1,3)
v2 = (2,1)
v3 = (3,1)
Każdy wektor ruchy może być wykorzystany dowolną ilość razy byle osiągnąć punkt (a,b) - dokładnie punkt (a,b) !

I przykładowo aby dojść do punktu (4,4) muszę wykonać następujące ruchy wektorami v1 i v3, bo
Startuję z (0,0). Przemieszczam się o wektor v1 i jestem w (1,3). Przemieszczam się o wektor v3 i jestem w (4,4) czyli w miejscu oczekiwanym.

Algorytm może zwrócić brak rozwiązania jeżeli nie można dojść do celu przy pomocy dostępnych wektorów ruchu. Algorytm ma zwrócić możliwie najkrótszą drogę i ilość możliwych dojść do celu.

Znalazłem w sieci podobne algorytmy, ale żaden nie pasował do tego problemu. Sam próbowałem to rozwiązać, ale nawet nie wyszło mi ułożenie tablicy stosowanej w programowaniu dynamicznym, gdzie o definicji rekurencyjnej nawet nie wspomnę, proszę o nakierowanie mnie w odpowiednim kierunku...

Dziękuje i pozdrawiam,
Michał Zabielski

1. Tworzysz sobie tablicę [n][n] list przechowujących informacje o poprzedniku oraz o ilości skoków do początku
2. Startujesz z pola (0,0) i rozlewasz się po wszystkich sąsiadach których możesz osiągnąć z tego pola za pomocą wektorów i do listy dla danego sąsiada dopisujesz pole z którego przyszedłeś plus licznik tego skąd przyszedłeś + 1. Jeśli na liście wcześniej tego pola nie było, to rozlewasz się dalej, z tego pola które właśnie osiągnąłeś (rozlewasz się na zasadzie BFS), jeśli pole z którego przyszedłeś tam już było to nie robisz nic.
3. Liczymy aż dojdziemy do sytuacji ze nic nowego się już nie pojawia, wtedy liczymy trasę optymalną "od końca".

• wiesz z jakiego pola przyszedłeś na pole docelowe, i wiesz jak doszedłeś to tamtego pola etc, więc cofasz się aż trafisz na pole źródłowe.

Tworzysz kwadratową macierz rozmiaru (a + 1, b + 1), numerujesz wiersze od 0 i kolumny od 0. Wartość komórki (u, v) niech oznacza ilość dróg od (u, v) do (0, 0). Zakładając, że dostępne wektory mają nieujemne składowe (co jest praktycznie warunkiem koniecznym) to wystarczy, że liczysz kolumny, albo wiersze po kolei, od pierwszej kolumny/ pierwszego wiersza.

M(u, v) = M(u - v1.x, v - v1.y) + .... + M(u - vn.x, v - vn.y), gdzie u, v to indeksy w macierzy, v1, ..., vn to kolejne wektory. M(x, y) == 0 jeżeli x < 0 lub y < 0.

Możesz zrobić wersję ze spamiętywaniem, różni się tylko tym, że obliczasz elementy na bieżąco, a wyniki zapamiętujesz w tablicy. Szkielet funkcji rekurencyjnej:

typ funkcja(parametry) {
  if (można łatwo obliczyć wartość dla parametrów) {
    zwróć wynik natychmiast
  } else if (tablica nie zawiera obliczonej wartości dla parametrów) {
    oblicz tą wartość i zapisz w tablicy
  }
  zwróć wartość z tablicy dla parametrów
}

Wadą funkcji ze spamiętywaniem jest potencjalnie zbyt duży poziom rekurencji, a co za tym idzie przepełnienie stosu.</del>

Edit:
Źle zrozumiałem pytanie. Algo Shaloma (czyli wariacja Dijkstry) jest OK, więc nie będę się ponownie rozpisywał.

Dziękuje Wam za pomoc!

Algorytm faktycznie działa w taki sposób, ale co jeżeli wektor będzie posiadał 3 zmienne lub więcej, czyli np.
v1 = (2,3,1)
v2 = (6,2,1)
v3 = (8,2,1)

I tak samo, mamy dojść do punktu (a,b,c) gdzie a=b=c, czyli np. (8,8,8).

Czy ten algorytm ma prawo działać ? Działa dobrze, ale dla tablicy dwuwymiarowej. Nie sadzę jednak, że aby to zaimplementować trzeba korzystać z tablicy większej niż 2-wymiarowa, ale pomysłu nie mam :)

Przepraszam, że zapomniałem o tym wspomnieć...

jeśli poruszasz się w przestrzeni to tablica trójwymiarowa, a algorytm taki sam

krwq napisał(a)

jeśli poruszasz się w przestrzeni to tablica trójwymiarowa, a algorytm taki sam

Dziękuje Ci za odpowiedz.

Algorytm wg. założenia ma obsługiwać wektory od dwóch do pięciu zmiennych czyli możliwy jest także taki wektor:
v = (4,2,1,5,7)
I tak samo jak w poprzednich przypadkach... zaczynam od (0,0,0,0,0) i mam osiągnąć punkt (a,b,c,d,e), gdzie a=b=c=d=e, czyli np. (12,12,12,12,12).

Co wtedy ?

Pozdrawiam,
Michał Zabielski

Tablica pięciowymiarowa albo tablica asocjacyjna (hashtable).

@Michał Zabielski algorytm uogólnia się do N wymiarów :P ale jeśli przestrzeń będzie bardzo "rzadka" to optymalne pamięciowo będzie użycie HashMapy zamiast tablicy (spadek wydajnościowy będzie, ale teoretycznie w średnim przypadku asymptotycznie nadal będziesz miał tą samą złożoność)

Czy w polach tablicy muszę przechowywać wszystkie pola, z których TAM wchodzę ?

Z tego co zauważyłem na kilku przykładach to wystarczy pierwsza wpisana do tablicy współrzędna, bo wychodzi na to samo, czy mam rację ?

zastanów się jak to działa to będziesz umiał sobie sam odpowiedzieć.