:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/metody-programowania-algorytmy-zachlanne-metoda-dziel-i-zwyciezaj-programowanie-dynamiczne.md

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:

  1. własność wyboru zachłannego – dzięki lokalnym optymalnym wyborom można uzyskać globalne optymalne rozwiązanie,
  2. 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:

python
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ń:

python
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))   # 4

Programowanie 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:

python
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, natychmiast

Któ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

java
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#

csharp
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
    }
}
Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 0
rss dla komentarzy →

// brak komentarzy — bądź pierwszy

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).