Chotkos's Blog

Programowanie i informatyka

Programowanie Dynamiczne

Być może nie powinno się to znaleźć w kategorii algorytmy, ale jest to jedna z podstawowych strategii w programowaniu, o której bardzo źle byłoby zapomnieć.

Programowanie dynamiczne da się streścić krótkim zdaniem – rozwiązywanie dużego problemu za pomocą wyników dla problemów mniejszych. Najlogiczniej będzie przedstawić to na jakimś przykładzie: wyobraź sobie, że musisz zaplanować trasę dla samochodu od twojego domu do stolicy Maroka – Rabatu. Oczywiście wziąć ogromną mapę i zacząć na niej zaznaczać ścieżkę jest prostym rozwiązaniem, ale niekoniecznie ścieżka którą w ten sposób wybierzesz będzie najszybsza, a poza tym cała ta ogromna mapa byłaby potrzebna w trakcie podróży – i powiedzmy szczerze – dosyć niewygodna. Rozwiązaniem tego programu jest właśnie programowanie dynamiczne. Zacznijmy od wyjechania z naszego miasta – określmy najkrótszą ścieżkę do opuszczenia miasta i ominięcia korków 😉 trasę zaznaczmy na planie miasta, następnie wyznaczmy sobie inny cel, który nie będzie zbyt daleko – powiedzmy naszą zachodnią granicę, wyznaczamy ścieżkę, zapisujemy na małej mapce Polski i przechodzimy do mapy Niemiec, gdzie będziemy udawali się do Francji…

W ten oto sposób mamy w podręcznym bagażu kilka niewielkich, poręcznych mapek z których każda prezentuje najkrótszą ścieżkę – rozwiązanie jest szybkie, wygodne i co najważniejsze – optymalne.

Jak to przełożyć na programowanie? Miałem ostatnio na kółku Mazowieckich Talentów takie zadanie:

http://chomikuj.pl/chotkos/Programowanie/materia*c5*82y/sci.pdf

z tym że robiliśmy je tak aby bezwzględnie zawsze zaczynać od pola [1,1]

Jak to zrobić? Ano właśnie tutaj również mamy programowanie dynamiczne. Nasz program powinien sprawdzać który ruch bardziej mu się opłaca – w prawo, w lewo, czy w dół.

Zaczynamy od pola 1,1 i stajemy w następnym polu które się bardziej opłaca. Trzeba tylko pamiętać, żeby na krawędziach ustawić naprawdę małe liczby typu -1000001; abyśmy nigdy nie wyszli poza naszą pamięć przeznaczoną na tablicę 😉

W tym rozwiązaniu cały czas korzystamy z poprzednich obliczeń i to właśnie jest dynamika.

oczywiście mam rozwiązanie tego zadania, ale prosiłbym go nie czytać bo będzie ono zadaniem do tego tematu 😉

Tak więc zapraszam do sprawdzarki.

Luty 4, 2010 Posted by | Algorytmy, Programowanie | | Dodaj komentarz