Algorytm zachłanny

Algorytmy zachłanne (greedy algorithms) to rodzaj algorytmów, które podejmują sekwencyjne decyzje, wybierając lokalnie optymalne rozwiązanie w nadziei, że doprowadzi to do globalnie optymalnego rozwiązania. Algorytmy te są często prostsze do zaimplementowania i mogą być bardzo efektywne w rozwiązaniu pewnych problemów, chociaż nie zawsze gwarantują znalezienie optymalnego rozwiązania.

Charakterystyka algorytmu zachłannego

Algorytm zachłanny opiera się na strategii, która polega na dokonywaniu kolejnych wyborów, które są najlepsze w danym momencie, bez rozważania przyszłych konsekwencji tych wyborów.

Kluczowe cechy algorytmów zachłannych to:

  • lokalna optymalność - w każdym kroku algorytm dokonuje lokalnie najlepszego wyboru,
  • niezależność wyborów - każdy wybór jest niezależny od poprzednich wyborów,
  • podejście iteracyjne - algorytm iteracyjnie wybiera najlepsze rozwiązanie aż do osiągnięcia celu.

Przykłady problemów rozwiązywanych algorytmami zachłannymi

Problem najkrótszej drogi

Jednym z klasycznych przykładów algorytmu zachłannego jest problem najkrótszej drogi w grafie o nieujemnych wagach krawędzi. Algorytm Dijkstry jest przykładem algorytmu zachłannego, który znajduje najkrótszą drogę od jednego wierzchołka do wszystkich innych wierzchołków w grafie.

Problem plecakowy

Problem plecakowy (knapsack problem) polega na wyborze przedmiotów o określonej wartości i wadze tak, aby maksymalizować wartość przy ograniczonej pojemności plecaka. W przypadku, gdy można wybrać ułamkowe części przedmiotów (problem plecakowy z ułamkowym wyborem (fractional knapsack problem)), algorytm zachłanny działa bardzo efektywnie.

Implementacja problemu plecakowego z ułamkowym wyborem w języku Python

def fractional_knapsack(value, weight, capacity):
    # Obliczanie wartości jednostkowej (value per weight) dla każdego przedmiotu
    index = list(range(len(value)))
    ratio = [v/w for v, w in zip(value, weight)]
    
    # Sortowanie przedmiotów na podstawie wartości jednostkowej malejąco
    index.sort(key=lambda i: ratio[i], reverse=True)
    
    max_value = 0  # Maksymalna wartość, którą można zmieścić w plecaku
    fractions = [0] * len(value)  # Tablica do przechowywania ułamków przedmiotów
    for i in index:
        if weight[i] <= capacity:
            # Jeśli można wziąć cały przedmiot, bierzemy go
            fractions[i] = 1
            max_value += value[i]
            capacity -= weight[i]
        else:
            # Jeśli nie można wziąć całego przedmiotu, bierzemy tylko część
            fractions[i] = capacity / weight[i]
            max_value += value[i] * fractions[i]
            break
    
    return max_value, fractions
# Przykładowe dane
value = [60, 100, 120]
weight = [10, 20, 30]
capacity = 50
max_value, fractions = fractional_knapsack(value, weight, capacity)
print("Maksymalna wartość w plecaku:", max_value)
print("Ułamki wybranych przedmiotów:", fractions)

Wyjaśnienie działania programu

  • Dla każdego przedmiotu obliczamy jego wartość jednostkową jako stosunek wartości do wagi.
  • Sortujemy przedmioty według wartości jednostkowej w porządku malejącym.
  • Iterujemy przez posortowane przedmioty i dodajemy je do plecaka w całości, jeśli ich waga jest mniejsza lub równa pozostałej pojemności plecaka.
  • Jeśli nie możemy dodać całego przedmiotu, dodajemy tylko jego część, która zmieści się w plecaku.
  • Zwracamy maksymalną wartość, którą można zmieścić w plecaku oraz tablicę ułamków wybranych przedmiotów.

Złożoność obliczeniowa

  • Złożoność czasowa - O(n log ⁡n), gdzie nn to liczba przedmiotów. Sortowanie dominuje czas wykonania.
  • Złożoność pamięciowa: O(n), ponieważ przechowujemy dodatkowe informacje o wartościach jednostkowych i ułamkach przedmiotów.

Zastosowania algorytmów zachłannych - przykłady

Algorytmy zachłanne znajdują zastosowanie w różnych dziedzinach, takich jak:

  • optymalizacja zasobów (np. problem plecakowy),
  • nawigacja i znajdowanie najkrótszej ścieżki (np. algorytm Dijkstry),
  • kompresja danych (np. kodowanie Huffmana),
  • harmonogramowanie zadań (np. problem najwcześniejszego terminu).

Algorytmy zachłanne są prostymi i efektywnymi narzędziami do rozwiązywania wielu problemów optymalizacyjnych. Chociaż nie zawsze gwarantują znalezienie globalnie optymalnego rozwiązania, są bardzo użyteczne w praktyce, szczególnie w przypadku problemów, gdzie lokalne wybory prowadzą do globalnie optymalnych wyników.

Komentarze