Zachłanne algorytmy

4.1 Definicja zachłannych algorytmów.

Zachłanne algorytmy (Greedy Algorithms) to klasa algorytmów, które budują rozwiązanie poprzez przyjmowanie lokalnie optymalnych decyzji na każdym kroku. Te decyzje są podejmowane na podstawie bieżącego stanu i nie są przeglądane w przyszłości.

Zachłanne algorytmy są często używane do rozwiązywania problemów optymalizacyjnych, gdzie celem jest maksymalizacja lub minimalizacja określonej wielkości.

Podstawowe zasady zachłannych algorytmów

• Zachłanny wybór: Na każdym kroku algorytm wybiera najlepszą lokalną opcję, która według niego doprowadzi do globalnie optymalnego rozwiązania.
• Optymalna podstruktura: Problem musi mieć właściwość, że lokalnie optymalne rozwiązania można połączyć, aby uzyskać globalne optymalne rozwiązanie.
• Monotoniczność: Po wybraniu kolejnego lokalnie optymalnego kroku, rozwiązanie nie powinno być pogorszone przez kolejne wybory.

Zalety i wady zachłannych algorytmów

Zalety:

• Prostota implementacji: Zachłanne algorytmy są często łatwe do zrozumienia i implementacji.
• Wydajność: Zazwyczaj działają szybciej niż bardziej skomplikowane algorytmy, takie jak programowanie dynamiczne.

Wady:

• Brak globalnej optymalności: Zachłanne algorytmy nie zawsze prowadzą do globalnie optymalnego rozwiązania.
• Nie wszystkie problemy się nadają: Tylko określone problemy można rozwiązać za pomocą zachłannych algorytmów.

Istnieje cała klasa problemów, dla których najlepsze rozwiązanie osiąga się za pomocą zachłannego algorytmu. Warto się z nimi zapoznać.

4.2 Problem rozmieniania monet.

Problem:

Mamy monety o różnych nominałach. Trzeba znaleźć minimalną liczbę monet do wydania danej kwoty.

Rozwiązanie:

Zawsze wybierana jest moneta o największym nominale, która nie przekracza pozostałej sumy.

Złożoność czasowa: O(n), gdzie n - liczba typów monet.

Przykład kodu w Pythonie:

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count
        

4.3 Problem plecakowy

Problem:

Mamy przedmioty o znanej wartości i wadze. Chcemy włożyć do plecaka o stałej wielkości rzeczy o jak największej wartości.

W tej wersji problemu przedmioty można dzielić na części. Na przykład, chcemy kupić różne kasze i można wziąć 1000 gramów lub nawet 512.

Rozwiązanie:

Sortowanie przedmiotów według wartości jednostkowej (wartość/waga) i wybieranie największych wartości jednostkowych aż do wypełnienia plecaka.

Złożoność czasowa: O(n log n), gdzie n - liczba przedmiotów.

Przykład kodu w Pythonie:

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight
        
def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x.ratio, reverse=True)
    total_value = 0.0
    for item in items:
        if capacity >= item.weight:
            total_value += item.value
            capacity -= item.weight
        else:
            total_value += item.ratio * capacity
            break
    return total_value
        
        

4.4 Problem pokrycia odcinkami

Problem:

Istnieją odcinki na linii prostej, określone przez swoje końce (x1, x2) i jeden celowy odcinek. Trzeba znaleźć minimalną liczbę odcinków, które pokrywają wszystkie punkty celowego odcinka.

Rozwiązanie:

Sortowanie odcinków według prawego końca i wybieranie najmniejszego odcinka, który pokrywa bieżący punkt.

Złożoność czasowa: O(n log n), gdzie n - liczba odcinków.

Przykład kodu w Pythonie:

def min_segments(segments):
    segments.sort(key=lambda x: x[1])
    count = 0
    end = -float('inf')
    for seg in segments:
        if seg[0] > end:
            end = seg[1]
            count += 1
    return count
        

1

Опрос

Algorytmy zachłanne,  59 уровень,  3 лекция

недоступен

Algorytmy zachłanne

Algorytmy zachłanne

Открыть