Algorytmy zachłanne. Już sama ta nazwa brzmi dość przerażająco, nie uważacie? Nie trzeba ich jednak stosować, bo są inne techniki służące do rozwiązywania zagadnień optymalizacyjnych.
Jedną z nich jest bez wątpienia programowanie dynamiczne. Co to za zwierzę? Czy jest drapieżne, czy gryzie? Bez obaw. Zapraszam do dalszej lektury wszystkich zainteresowanych. Niechaj czyta, kto ciekawy.
Programowanie dynamiczne
Jak już można się domyślić, programowanie dynamiczne jest techniką, albo też strategią projektowania algorytmów, najczęściej stosowaną do rozwiązywania zagadnień optymalizacyjnych. Jest to także znakomita alternatywa dla wielu spośród zagadnień rozwiązywanych przy użyciu algorytmów zachłannych – czyli takich, które przy rozwiązywaniu danego problemu dokonują zachłannego, czyli najlepiej rokującego w danym momencie rozwiązania. Za twórcę programowania dynamicznego powszechnie uważa się amerykańskiego matematyka Richarda Bellmana.
Na czym opiera się programowanie dynamiczne? W głównej mierze na podziale rozwiązywanego właśnie problemu na podproblemy, a to za sprawą wyszczególnienia kilku parametrów. Najlepiej stosować do trzech lub czterech parametrów, gdyż wykorzystanie większej ich liczby rzadko kiedy bywa praktyczne. Najczęściej też jednym z takich parametrów jest liczba elementów, które znajdują się w rozpatrywanym problemie, natomiast drugim – równie ważnym – może być pewna wartość liczbowa, która zmienia się w zakresie od zera do największej stałej występującej w problemie. Brzmi to jak czarna magia albo naukowy bełkot? Nic na to nie poradzę, zagadnienie dotyczące programowania dynamicznego łatwe ani przystępne nie jest. Niemniej jednak takie informacje zawsze są potrzebne.
Algorytmy programowania dynamicznego stosowane są najczęściej w bioinformatyce, ekonomii, informatyce, logistyce i matematyce. Najczęściej występującymi zastosowaniami programowania dynamicznego są: algorytm CYK, algorytm Viterbiego, algorytm Earleya, algorytm Floyda-Warshalla, algorytm Needlemana-Wunscha oraz algorytmy znajdujące najdłuższy wspólny podciąg, rozwiązujące zagadnienia plecakowe a także algorytm znajdujący cykl Hamiltona.
