Metody programowania: Algorytmy zachłanne, metoda „dziel i zwyciężaj”, programowanie dynamiczne
Postanowiłem przygotować dla Was artykuł na temat trzech moim zdaniem dość ważnych metod programowania czyli algorytmach zachłannych, metodzie „dziel i zwyciężaj” oraz programowaniu dynamicznym. W tym wpisie skupię się na omówieniu ich koncepcji związanych z projektowaniem algorytmów. Bez niepotrzebnego przedłużania przejdźmy więc do konkretów…
Algorytmy zachłanne
Idea działania algorytmów zachłannych jest bardzo prosta do zrozumienia. Opiera się ona na jednej bardzo prostej zasadzie: w danym momencie wybieramy lokalną najbardziej optymalną możliwość rozwiązania problemu w nadziei, że doprowadzi ona do najlepszego globalnego rozwiązania. Poważną wadą podejścia „zachłannego” w projektowaniu algorytmów jest to, że tak skonstruowana aplikacja nie zawsze poradzi sobie z zadanym problemem.
Strategia algorytmów zachłannych oparta jest o dwie podstawowe cechy:
- własność wyboru zachłannego – dzięki lokalnym optymalnym wyborom można uzyskać globalne optymalne rozwiązanie,
- optymalna podstruktura – optymalne rozwiązanie jest funkcją optymalnych rozwiązań problemów.
Przykład
Dobre wykorzystanie:
Przykładem dobrze wykorzystywanego algorytmu zachłannego jest „problem wyboru zajęć”. Polega on na przyporządkowaniu n proponowanym zajęciom odpowiednich zasobów (czyli sal lekcyjnych). Założenie jest takie, że w danej chwili w danej sali mogą odbywać się tylko jedne zajęcia.
Algorytm więc bierze dane zajęcia i przyporządkowuje je do odpowiedniej wolnej w danej chwili sali. Procedura ta powtarzana jest do momentu przejścia przez wszystkie planowane zajęcia.
Złe wykorzystanie:
Drugim przykładem tym razem złego wykorzystania algorytmu zachłannego jest „problem kolorowania grafu”. Kolorowanie wierzchołkowe to nic innego jak przypisanie wszystkim wierzchołkom w danym grafie konkretnego koloru w taki sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru.
Algorytm więc bierze dany wierzchołek i przyporządkowuje mu pierwszy możliwy do przypisania kolor. W zależności więc od przyjętej kolejności wierzchołków problem ten może zostać rozwiązany w sposób nieoptymalny tzn. każdy wierzchołek będzie miał inny kolor, podczas gdy do pokolorowania całego grafu wystarczyły by np. dwa kolory.
Metoda „dziel i zwyciężaj”
Metoda „dziel i zwyciężaj” w dużym skrócie polega na rekurencyjnym podziale danego problemu na mniejsze podproblemy co ma prowadzić do szybszego rozwiązania zadania. Strategia ta polega na podziale rekurencyjnym problemu na dwa lub więcej mniejszych podproblemów tego samego typu (lub podobnego) do momentu w którym fragmenty staną się wystarczająco proste do rozwiązania. Kolejnym krokiem jest scalenie otrzymanych rozwiązań podproblemów aby uzyskać rozwiązanie całego zadania.
Przykładem wykorzystania metody dziel i zwyciężaj jest algorytm sortowania przez scalanie.
Programowanie dynamiczne
Programowanie dynamiczne to koncepcja projektowania algorytmów polegająca na podziale danego problemu na mniejsze zależne od siebie podproblemy. W przeciwieństwie do metody „dziel i zwyciężaj” tutaj rozwiązania mniejszych podproblemów zapisujemy w tablicy i wykorzystujemy je do rozwiązań większych podproblemów. Różnica w porównaniu z algorytmami „zachłannymi” jest taka, że w algorytmach „zachłannych” wybieramy najlepsze możliwe rozwiązanie w danej chwili. W programowaniu dynamicznym tak nie musi być – sprawdzamy wszystkie rozwiązania podproblemów aby wyznaczyć końcowy wynik.
Przykładem algorytmu opartego o ideę programowania dynamicznego jest jest algorytm CYK (Cocke’a-Youngera-Kasamiego) sprawdzający czy dane słowo należy do danego języka bezkontekstowego.
