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