Najtańsza droga i najdłuższy wspólny podciąg

🎯 Po co Ci to?

Dwa problemy z tej jednostki to chleb powszedni świata: najtańsza droga (nawigacja, routing pakietów w sieci, planowanie produkcji) i najdłuższy wspólny podciąg (porównywanie wersji plików — tak działa śledzenie zmian w dokumentach, porównywanie DNA, wykrywanie plagiatów). Oba wyglądają na niepodobne; oba pękają pod tym samym uderzeniem — tabelą programowania dynamicznego. To jednostka-trening: dwie pełne rozgrywki metodą z 8.3, od podproblemu do odtworzenia rozwiązania. Po niej dynamiczne przestanie być sztuczką z reszty — stanie się Twoim narzędziem.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • znaleźć najtańszą drogę po siatce kosztów (i pokazać, że zachłanność błądzi);
  • policzyć najdłuższy wspólny podciąg dwóch napisów tabelą;
  • odtworzyć z tabeli samą drogę / sam podciąg, nie tylko ich wartość.

🔁 Przypomnij sobie

Z 8.3: podproblem → zależność → tabela → ślad decyzji; z 5.1: porównywanie tekstów znak po znaku.

📘 Wyjaśnienie

Problem 1: najtańsza droga po siatce. Plansza $m \times n$ pól, każde z kosztem wejścia. Startujesz w lewym górnym rogu, idziesz tylko w prawo lub w dół, chcesz dotrzeć do prawego dolnego rogu jak najtaniej.

3111499919991111z pola START do pola META — tylko w prawo lub w dółzachłanna: 25optymalna: 12zachłanność skusiłytanie pola górnegowiersza — i wpadław kolumnę dziewiątek
Siatka kosztów 4 na 4: trasa zachłanna (zawsze tańszy następny krok) skręca w kuszący górny wiersz i kończy z sumą 25, a trasa optymalna znaleziona tabelą schodzi drożej na starcie i kończy z sumą 12; zachłanność nie widzi drogich pól za zakrętem. · rys. własny

Zachłanność („idź tam, gdzie taniej za krok") potrafi wpaść w kanał drogich pól — lokalna oszczędność, globalna strata. Dynamiczne myśli od tyłu… albo od przodu — podproblem: $D(i, j)$ = najtańsze dojście do pola $(i, j)$. Do pola wchodzi się z góry albo z lewej, więc:

$$D(i, j) = \text{koszt}(i, j) + \min\big(D(i-1, j),\ D(i, j-1)\big)$$

Baza: $D(0, 0) = \text{koszt}(0,0)$; pola pierwszego wiersza/kolumny mają tylko jedną opcję wejścia. Wypełniasz tabelę wierszami (każda komórka sięga w górę i w lewo — już policzone ✓), a $D(m-1, n-1)$ to odpowiedź. Koszt: jedna operacja na pole, $O(mn)$ — a możliwych tras jest wykładnicznie wiele! Tabela znowu „przegląda wszystkie trasy" bez przeglądania: każda komórka podsumowuje najlepszą z wszystkich dróg do siebie.

Problem 2: najdłuższy wspólny podciąg (NWP). Podciąg napisu to jego litery w oryginalnej kolejności, niekoniecznie sąsiednie („kot" jest podciągiem „krzok pusty"). NWP dwóch napisów to najdłuższy napis będący podciągiem obu — miara ich podobieństwa. Dla „PIESEK" i „PASEK": wspólne jest „PSEK" (długość 4).

Podproblem: $L(i, j)$ = długość NWP pierwszych $i$ znaków napisu $A$ i pierwszych $j$ znaków napisu $B$. Zależność patrzy na ostatnie znaki:

  • jeśli $A[i-1] == B[j-1]$ (ostatnie znaki równe): ten znak wchodzi do podciągu — $L(i,j) = L(i-1, j-1) + 1$;
  • jeśli różne: opuszczamy ostatni znak $A$ albo ostatni znak $B$ — $L(i,j) = \max\big(L(i-1, j),\ L(i, j-1)\big)$.

Baza: $L(0, \cdot) = L(\cdot, 0) = 0$ (pusty napis — pusty podciąg). Tabela dla „PIESEK"/„PASEK" ma 7×6 komórek i wypełnia się mechanicznie; w prawym dolnym rogu wyjdzie 4. Odtwarzanie podciągu — marszem od rogu: równe znaki → weź znak i idź po skosie; różne → idź tam, skąd przyszło maksimum.

💭 Pomyśl: Ile jest wszystkich podciągów napisu długości 20? Czemu NWP „na siłę" (wypisz podciągi jednego, sprawdzaj w drugim) jest beznadziejne — i co dokładnie ratuje tabela?

Sprawdź odpowiedź

Każda litera: bierzesz lub nie — $2^{20} \approx 10^6$ podciągów (a dla 40 znaków — bilion). Tabela ma ledwie $20 \times 20 = 400$ komórek! Ratunek to obserwacja, że miliony podciągów przechodzą przez te same stany „(ile wzięto z A, ile z B)" — a stanów jest tylko $mn$. Dynamiczne nie liczy podciągów; liczy stany. Ta zamiana perspektywy (z „obiektów" na „stany") to najgłębsza idea metody — i dokładnie ona napędza porównywarki plików, które codziennie zestawiają tysiące wersji dokumentów w milisekundach.

🐞 Znajdź błąd

Uczeń liczy NWP „KOT" i „KROKODYL" i twierdzi: „wspólny podciąg to «KO», długość 2 — bo «KOT» nie mieści się w «KROKODYL» w całości". Tabela mówi co innego. Co przeoczył?

Sprawdź odpowiedź

„K-O-T": K (pozycja 1 w KROKODYL), O (pozycja 3... „KROKODYL" — tak), T?… W „KROKODYL" nie ma T! Więc NWP to „KO", długość 2 — uczeń ma rację?? Sprawdź uważniej: K-R-O-K-O-D-Y-L. Litery „KOT": K ✓, O ✓, T ✗. NWP = „KO", 2. Tabela potwierdzi. Gdzie więc błąd? W uzasadnieniu: „nie mieści się w całości" to argument o podsłowie (spójnym fragmencie), nie o podciągu — „KOT" mógłby być podciągiem mimo braku spójności (jak „KOL" — K, O, L z pominięciami ✓). Wynik trafny, rozumowanie błędne — na maturze punktowane jest oba. Rozróżnienie podciąg/podsłowo (fragment spójny) to pierwsza rzecz do sprawdzenia w każdym zadaniu tekstowym.

🛠️ Teraz Ty

Bez komputera: wypełnij tabelę NWP dla „ALGORYTM" i „LOGARYTM" (8×8) — jaka długość i jaki podciąg? Z komputerem: zaimplementuj najtańszą drogę z odtwarzaniem trasy; przetestuj na siatce z ryciny (musi wyjść 18) i na siatce, którą ułożysz tak, żeby zachłanność zbłądziła jak najdrożej.

📐 Definicje tej lekcji

  • Najtańsza droga po siatce — $D(i,j) = \text{koszt} + \min(\text{góra}, \text{lewo})$; tabela $O(mn)$ zamiast wykładniczych tras.
  • Podciąg / podsłowo — litery w kolejności z pominięciami / spójny fragment; NWP dotyczy podciągów.
  • NWP — $L(i,j)$: skos +1 przy równych ostatnich znakach, inaczej max z góry/lewa.

📌 Najważniejsze w pigułce

  • Dwa nowe kostiumy tej samej metody: stany zamiast obiektów, tabela zamiast przeglądu.
  • Droga: wchodzi się z góry lub z lewej — więc min z dwóch; NWP: równe znaki idą po skosie.
  • Wartość optimum czytasz z rogu tabeli; samo rozwiązanie — marszem po śladach decyzji.

🎒 Zadania

  1. Policz tabelą najtańszą drogę dla siatki 3×3: [[1,3,1],[1,5,1],[4,2,1]]. Podaj koszt i trasę.
Wskazówka i odpowiedź

Tabela $D$: wiersz 0: 1,4,5; wiersz 1: 2,7,6; wiersz 2: 6,8,7. Odtwarzanie od $D(2,2)=7$: przyszło z $D(1,2)=6$ (góra), to z $D(0,2)=5$? $6 = 1 + \min(5, 7) = 6$ ✓ z góry; $5 = 1 + 4$ z lewej… Trasa: (0,0)→(0,1)→(0,2)→(1,2)→(2,2), koszty 1+3+1+1+1 = 7 ✓. Zachłanność od (0,0): w prawo 3 czy w dół 1? — w dół; potem 5 czy 4 — w dół (4); potem 2, 1: razem 1+1+4+2+1 = 9 > 7. Kanał tanich jedynek na górze był niewidoczny dla zachłannego nosa.

  1. Wypełnij tabelę NWP dla „SOBOTA" i „ROBOTA". Długość? Podciąg? A czy jest nim podsłowo?
Wskazówka i odpowiedź

Wspólne „OBOTA" — długość 5 (S≠R na starcie, reszta identyczna). Tu akurat NWP jest zarazem podsłowem obu (spójny ogon „OBOTA") — tak bywa, gdy napisy różnią się tylko początkiem. Przy „SOBOTA"/„ROBOTY" NWP to „OBOT" — wciąż spójne; a przy „KAJAK"/„KAWKA"? K-A-A/K? NWP = „KAA"?… policz: KAJAK vs KAWKA — K✓A✓, potem J/W różne, A: „KAJAK" ma A na poz. 4, „KAWKA" na 5 → „KAA"? ale też „KAK" (K,A,K). Długość 3, podciągów-świadków kilka — NWP nie musi być jedyny! Tabela daje długość jednoznacznie; świadków bywa wielu.

  1. Porównywarka wersji dokumentu pokazuje „usunięte" i „dodane" linie. Wyjaśnij, jak zrobić to z NWP liczonego na liniach (nie znakach): co jest wspólnym podciągiem i czym są linie poza nim?
Wskazówka i odpowiedź

Potraktuj dokumenty jako ciągi linii i policz NWP — to linie niezmienione (wspólny szkielet obu wersji, w kolejności). Linie starej wersji spoza NWP = usunięte; linie nowej spoza NWP = dodane. Im dłuższy NWP, tym mniejszy raport zmian — dlatego narzędzia porównujące szukają najdłuższego, a nie jakiegokolwiek wspólnego podciągu. Właśnie odtworzyłeś ideę narzędzia diff, którym świat programistów żyje od 1976 roku — tabela z tej jednostki, uruchamiana miliardy razy dziennie.

🔍 Sprawdź, czy umiesz

  • Wypełnić obie tabele (droga, NWP) ręcznie dla małych danych.
  • Odtworzyć trasę/podciąg ze śladów decyzji.
  • Rozróżnić podciąg od podsłowa i wskazać, gdzie to rozróżnienie gra rolę.

Ucz się tej jednostki z asystentem