Algorytmy zachłanne są szeroko stosowane w informatyce i matematyce, ponieważ oferują proste i szybkie rozwiązania wielu skomplikowanych problemów optymalizacyjnych. Zachłanne podejście polega na podejmowaniu serii lokalnie optymalnych decyzji, które są najlepsze w danym momencie, bez uwzględniania przyszłych konsekwencji. Choć algorytmy te nie zawsze gwarantują uzyskanie globalnie optymalnych rozwiązań, w wielu przypadkach są wystarczająco efektywne, a ich implementacja jest prostsza niż w przypadku bardziej zaawansowanych technik, takich jak programowanie dynamiczne. W tej lekcji omówimy kilka popularnych przykładów strategii zachłannych, analizując ich działanie, zastosowania oraz przypadki, w których mogą zawodzić.

Wprowadzenie do zachłannych strategii

Podstawowym założeniem algorytmów zachłannych jest to, że wybór lokalnie najlepszego rozwiązania prowadzi do optymalnego rozwiązania całego problemu. Aby algorytm zachłanny był skuteczny, problem musi spełniać określone warunki, takie jak:

• Właściwość zachłanna: Podzbiór optymalnego rozwiązania powinien również być optymalny. Innymi słowy, podejmowanie lokalnie optymalnych decyzji musi prowadzić do globalnie optymalnego rozwiązania.
• Właściwość prefiksowa: Algorytm zachłanny nigdy nie zmienia swojej decyzji. Raz podjęta decyzja nie może zostać cofnięta.

Jeśli problem spełnia te warunki, algorytm zachłanny może być efektywnym rozwiązaniem. Jeśli jednak warunki nie są spełnione, algorytm zachłanny może prowadzić do suboptymalnych rozwiązań.

Przykłady strategii zachłannych

1. Problem minimalnego drzewa rozpinającego (MST)

Jednym z najbardziej znanych zastosowań algorytmów zachłannych jest znajdowanie minimalnego drzewa rozpinającego (MST) w grafie. Minimalne drzewo rozpinające to podzbiór krawędzi grafu, który łączy wszystkie węzły, nie tworząc cykli, a suma wag tych krawędzi jest minimalna. Dwa najpopularniejsze algorytmy do rozwiązania tego problemu to algorytm Kruskala i algorytm Prima.

Algorytm Kruskala

Algorytm Kruskala działa w sposób zachłanny, wybierając krawędzie o najmniejszej wadze, które nie tworzą cyklu, aż wszystkie węzły zostaną połączone. Proces ten można podzielić na następujące kroki:

1. Posortuj wszystkie krawędzie grafu według wag w porządku rosnącym.
2. Inicjalizuj zbiór podzbiorów, aby śledzić, które węzły są już połączone.
3. Iteruj przez posortowane krawędzie i dodaj krawędź do drzewa rozpinającego, jeśli nie tworzy cyklu.
4. Powtarzaj, aż wszystkie węzły zostaną połączone.

#include <iostream>
#include <vector>
#include <algorithm>

struct Edge {
    int u, v, weight;
    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

bool compareEdges(Edge a, Edge b) {
    return a.weight < b.weight;
}

int findParent(int node, std::vector<int>& parent) {
    if (parent[node] == node) return node;
    return parent[node] = findParent(parent[node], parent);
}

void unionNodes(int u, int v, std::vector<int>& parent, std::vector<int>& rank) {
    int pu = findParent(u, parent);
    int pv = findParent(v, parent);
    if (rank[pu] > rank[pv]) {
        parent[pv] = pu;
    } else if (rank[pu] < rank[pv]) {
        parent[pu] = pv;
    } else {
        parent[pv] = pu;
        rank[pu]++;
    }
}

void kruskalMST(int n, std::vector<Edge> edges) {
    std::sort(edges.begin(), edges.end(), compareEdges);
    std::vector<int> parent(n);
    std::vector<int> rank(n, 0);
    for (int i = 0; i < n; ++i) parent[i] = i;
    
    int mstWeight = 0;
    for (Edge e : edges) {
        if (findParent(e.u, parent) != findParent(e.v, parent)) {
            mstWeight += e.weight;
            unionNodes(e.u, e.v, parent, rank);
        }
    }
    
    std::cout << "Weight of MST: " << mstWeight << std::endl;
}

int main() {
    int n = 4;
    std::vector<Edge> edges = {
        Edge(0, 1, 10), Edge(0, 2, 6), Edge(0, 3, 5), Edge(1, 3, 15), Edge(2, 3, 4)
    };
    kruskalMST(n, edges);
    return 0;
}

Algorytm Prima

Algorytm Prima działa inaczej, wybierając węzeł startowy i dodając do drzewa krawędź o najmniejszej wadze, która łączy nowy węzeł z istniejącym drzewem. Proces jest powtarzany, aż wszystkie węzły zostaną połączone. Algorytm Prima jest bardziej efektywny w przypadku grafów gęstych.

Problem plecakowy (Knapsack Problem)

Problem plecakowy to klasyczny problem optymalizacyjny, w którym mamy plecak o określonej pojemności i zestaw przedmiotów, z których każdy ma określoną wartość i wagę. Celem jest maksymalizacja całkowitej wartości przedmiotów w plecaku, nie przekraczając jego pojemności. Zachłanne podejście działa dobrze w wersji ułamkowej problemu plecakowego, gdzie możemy dzielić przedmioty na części.

Rozwiązanie ułamkowego problemu plecakowego

Algorytm zachłanny wybiera przedmioty na podstawie stosunku wartości do wagi, zaczynając od tych, które mają najwyższy stosunek, aż plecak zostanie zapełniony. Jeśli pozostałe miejsce nie wystarcza na cały przedmiot, dodajemy ułamek przedmiotu.

#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
    int value, weight;
    Item(int value, int weight) : value(value), weight(weight) {}
};

bool compareItems(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

double fractionalKnapsack(int capacity, std::vector<Item> items) {
    std::sort(items.begin(), items.end(), compareItems);
    double totalValue = 0.0;
    
    for (Item item : items) {
        if (capacity >= item.weight) {
            capacity -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * ((double)capacity / item.weight);
            break;
        }
    }
    
    return totalValue;
}

int main() {
    int capacity = 50;
    std::vector<Item> items = {
        Item(60, 10), Item(100, 20), Item(120, 30)
    };
    std::cout << "Maximum value in Knapsack: " << fractionalKnapsack(capacity, items) << std::endl;
    return 0;
}

Zastosowania algorytmów zachłannych

Algorytmy zachłanne są szeroko stosowane w praktyce, szczególnie w sytuacjach, gdzie szybkość jest kluczowa, a dokładność może być poświęcona na rzecz efektywności. Inne przykłady zachłannych strategii obejmują:

1. Problem optymalizacji trasy

W problemie optymalizacji trasy, takim jak problem komiwojażera, algorytmy zachłanne mogą być używane do znajdowania przybliżonych rozwiązań poprzez wybór najbliższego sąsiada w każdym kroku. Choć rozwiązanie zachłanne nie zawsze jest optymalne, może być wystarczająco dobre dla praktycznych zastosowań.

2. Kodowanie danych

Kodowanie Huffmana, które omawialiśmy wcześniej, jest przykładem zachłannej strategii w kompresji danych. Algorytm ten wybiera symbole o najmniejszej częstotliwości, aby zminimalizować całkowitą długość zakodowanego strumienia.

Podsumowanie

Algorytmy zachłanne są potężnym narzędziem w arsenale programisty, szczególnie w sytuacjach, gdzie szybkość działania jest kluczowa. Choć nie zawsze prowadzą do optymalnych rozwiązań, ich prostota i efektywność sprawiają, że są nieocenione w wielu problemach. Ważne jest jednak, aby dobrze rozumieć warunki, w których zachłanne podejście jest skuteczne, oraz być świadomym jego ograniczeń.

Następna lekcja ==> Praca z grafami