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. użyjemy znacznie większej liczby kolorów niż potrzeba, podczas gdy do pokolorowania całego grafu wystarczyłyby 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 algorytm CYK (Cocke’a-Youngera-Kasamiego) sprawdzający czy dane słowo należy do danego języka bezkontekstowego.
Trzy metody w kodzie
Koncepcje mamy omówione, zobaczmy więc każdą metodę w działaniu na krótkim, kompletnym przykładzie w Pythonie.
Algorytm zachłanny: wydawanie reszty
Klasyka podejścia zachłannego: wydajemy resztę jak najmniejszą liczbą monet, zawsze biorąc największy możliwy nominał. Dla polskich nominałów strategia zachłanna daje wynik optymalny:
def wydaj_reszte(kwota, nominaly=[500, 200, 100, 50, 20, 10, 5, 2, 1]):
wynik = []
for nominal in nominaly: # od najwiekszego...
while kwota >= nominal: # ...bierz, dopoki sie miesci
kwota -= nominal
wynik.append(nominal)
return wynik
print(wydaj_reszte(287)) # [200, 50, 20, 10, 5, 2] - 6 monet (grosze)Pamiętajmy o wadzie opisanej wyżej: dla wymyślnych zestawów nominałów (np. 1, 3, 4) zachłanne branie największego zawodzi, bo dla kwoty 6 wybierze 4+1+1 zamiast 3+3.
Dziel i zwyciężaj: szukanie binarne
Najkrótsza ilustracja dzielenia problemu na mniejsze: szukanie w POSORTOWANEJ tablicy. W każdym kroku odrzucamy połowę danych, dzięki czemu w tablicy z miliona elementów wystarczy około 20 porównań:
def szukaj_binarnie(tablica, szukana):
lewy, prawy = 0, len(tablica) - 1
while lewy <= prawy:
srodek = (lewy + prawy) // 2
if tablica[srodek] == szukana:
return srodek # znaleziona, zwracamy indeks
if tablica[srodek] < szukana:
lewy = srodek + 1 # szukamy w prawej polowie
else:
prawy = srodek - 1 # szukamy w lewej polowie
return -1 # brak w tablicy
print(szukaj_binarnie([1, 3, 8, 12, 40, 77, 90], 40)) # 4Programowanie dynamiczne: Fibonacci ze spamiętywaniem
Naiwna rekurencja liczy te same podproblemy miliony razy. Programowanie dynamiczne robi to raz i zapamiętuje wynik (ang. memoization). Różnica jest dramatyczna: fib(40) naiwnie to ponad miliard wywołań, ze spamiętywaniem 40:
def fib(n, pamiec={}):
if n <= 1:
return n
if n not in pamiec: # liczymy tylko RAZ
pamiec[n] = fib(n - 1, pamiec) + fib(n - 2, pamiec)
return pamiec[n]
print(fib(40)) # 102334155, natychmiastKtóra metoda do którego problemu?
- Zachłanna - gdy lokalnie najlepszy wybór prowadzi do globalnie najlepszego (wydawanie reszty, plan zajęć, kodowanie Huffmana). Najszybsza w implementacji, ale wymaga dowodu, że działa.
- Dziel i zwyciężaj - gdy problem dzieli się na NIEZALEŻNE podproblemy (szukanie binarne, sortowanie przez scalanie, quicksort).
- Programowanie dynamiczne - gdy podproblemy się POWTARZAJĄ i można ich wyniki spamiętać (Fibonacci, problem plecakowy, najkrótsze ścieżki).
Te same przykłady w Javie
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main {
// zachlanny: wydawanie reszty
static List<Integer> wydajReszte(int kwota) {
int[] nominaly = {500, 200, 100, 50, 20, 10, 5, 2, 1};
List<Integer> wynik = new ArrayList<>();
for (int nominal : nominaly)
while (kwota >= nominal) {
kwota -= nominal;
wynik.add(nominal);
}
return wynik;
}
// dziel i zwyciezaj: szukanie binarne
static int szukajBinarnie(int[] tab, int szukana) {
int lewy = 0, prawy = tab.length - 1;
while (lewy <= prawy) {
int srodek = (lewy + prawy) / 2;
if (tab[srodek] == szukana) return srodek;
if (tab[srodek] < szukana) lewy = srodek + 1;
else prawy = srodek - 1;
}
return -1;
}
// dynamiczne: Fibonacci ze spamietywaniem
static Map<Integer, Long> pamiec = new HashMap<>();
static long fib(int n) {
if (n <= 1) return n;
if (!pamiec.containsKey(n)) pamiec.put(n, fib(n - 1) + fib(n - 2));
return pamiec.get(n);
}
public static void main(String[] args) {
System.out.println(wydajReszte(287)); // [200, 50, 20, 10, 5, 2]
System.out.println(szukajBinarnie(new int[]{1, 3, 8, 12, 40}, 12)); // 3
System.out.println(fib(40)); // 102334155
}
}Te same przykłady w C#
using System;
using System.Collections.Generic;
class Program
{
// zachlanny: wydawanie reszty
static List<int> WydajReszte(int kwota)
{
int[] nominaly = {500, 200, 100, 50, 20, 10, 5, 2, 1};
var wynik = new List<int>();
foreach (int nominal in nominaly)
while (kwota >= nominal)
{
kwota -= nominal;
wynik.Add(nominal);
}
return wynik;
}
// dziel i zwyciezaj: szukanie binarne
static int SzukajBinarnie(int[] tab, int szukana)
{
int lewy = 0, prawy = tab.Length - 1;
while (lewy <= prawy)
{
int srodek = (lewy + prawy) / 2;
if (tab[srodek] == szukana) return srodek;
if (tab[srodek] < szukana) lewy = srodek + 1;
else prawy = srodek - 1;
}
return -1;
}
// dynamiczne: Fibonacci ze spamietywaniem
static Dictionary<int, long> pamiec = new();
static long Fib(int n)
{
if (n <= 1) return n;
if (!pamiec.ContainsKey(n)) pamiec[n] = Fib(n - 1) + Fib(n - 2);
return pamiec[n];
}
static void Main()
{
Console.WriteLine(string.Join(" ", WydajReszte(287))); // 200 50 20 10 5 2
Console.WriteLine(SzukajBinarnie(new[] {1, 3, 8, 12, 40}, 12)); // 3
Console.WriteLine(Fib(40)); // 102334155
}
}


// brak komentarzy — bądź pierwszy