Strategie mistrzów: zachłanność i programowanie dynamiczne
Wstęp do działu
Dotąd algorytmy odpowiadały na pytania „znajdź", „posortuj", „policz". Ten dział wchodzi piętro wyżej — do problemów optymalizacyjnych: nie „znajdź jakieś rozwiązanie", ale „znajdź najlepsze". Najmniej monet w reszcie. Najcenniejszy załadunek plecaka. Najtańsza trasa. Najdłuższe wspólne dopasowanie. Takie pytania zadaje logistyka, finanse, medycyna i każda nawigacja świata — a naiwna odpowiedź „sprawdź wszystkie możliwości" umiera wykładniczo, zanim wystartuje.
Poznasz dwie wielkie strategie. Zachłanność — bierz to, co lokalnie najlepsze, i nie oglądaj się — bywa genialna i bywa pułapką; nauczysz się odróżniać jedno od drugiego. Programowanie dynamiczne — zapamiętuj rozwiązania podproblemów, żeby nigdy nie liczyć niczego dwa razy — to lekarstwo na wykładnicze eksplozje, obiecane jeszcze przy Fibonaccim. A na deser zobaczysz, że te same idee („ucz się z zapamiętanych przykładów") prowadzą wprost do algorytmu, którym maszyny uczą się klasyfikować — i policzysz na kartce swój pierwszy algorytm uczenia maszynowego.
Mapa pojęć działu
PROBLEMY OPTYMALIZACYJNE („znajdź NAJLEPSZE")
|
┌─────────────────────┴──────────────────────┐
ZACHŁANNOŚĆ [R] PROGRAMOWANIE DYNAMICZNE
bierz lokalnie najlepsze zapamiętuj podproblemy
reszta polskimi nominałami ✓ Fibonacci ze spamiętywaniem
[R] plecak ✗ (zdradza!) reszta DOWOLNYMI nominałami
| najtańsza droga w tablicy
kiedy wolno być zachłannym? najdłuższy wspólny podciąg
| podciągi (Kadane)
[R] UCZENIE Z PRZYKŁADÓW: k-NN
(zapamiętaj dane, klasyfikuj po sąsiadach)
Jednostki w tym dziale
- 8.1 Wydawanie reszty — kiedy zachłanność jest bezpieczna
- 8.2 Plecak — gdy zachłanność zdradza (rozszerzenie)
- 8.3 Programowanie dynamiczne — pamiętaj, co policzyłeś (rozszerzenie)
- 8.4 Najtańsza droga i najdłuższy wspólny podciąg (rozszerzenie)
- 8.5 Podciągi o własnościach (rozszerzenie)
- 8.6 Maszyna, która się uczy — klasyfikacja k-NN (rozszerzenie)