Chciwy algorytm z przykładem: co to jest, metoda i podejście

Co to jest algorytm zachłanny?

A Algorytm chciwy rekurencyjnie dzieli zestaw zasobów na podstawie maksymalnej natychmiastowej dostępności danego zasobu na dowolnym etapie wykonywania.

Rozwiązanie problemu przy użyciu podejścia chciwego składa się z dwóch etapów:

1. Skanowanie listy pozycji
2. Optymalizacja

Oba etapy przebiegają równolegle, ponieważ tablica wejściowa jest stopniowo dzielona.

Aby zastosować podejście chciwe, przydatna jest praktyczna znajomość rekurencji i przełączania kontekstu. tracKod. Paradygmat chciwości można opisać za pomocą pary stwierdzeń koniecznych i wystarczających.

Paradygmat zachłanności definiują dwa warunki.

• Każdy krok po kroku musi prowadzić problem w stronę najlepszego, akceptowanego rozwiązania.
• Struktura problemu musi zatrzymać się w skończonej liczbie kroków zachłannych.

Mając już tę teorię, przyjrzyjmy się historii podejścia opartego na chciwych poszukiwaniach.

Historia Chciwości Algorithms

Oto najważniejsze punkty zwrotne w historii algorytmów zachłannych:

• Koncepcja algorytmów zachłannych została po raz pierwszy opracowana w latach 1950. XX wieku dla algorytmów przeglądania grafów.
• Edsger Dijkstra opracował algorytm najkrótszej ścieżki w celu skrócenia tras przebiegających przez stolicę Holandii, Amsterdam.
• W tej samej dekadzie Prim i Kruskal opracowali strategie optymalizacji, które minimalizują koszty ścieżek wzdłuż tras ważonych w celu budowy minimalnych drzew rozpinających.
• W latach 70. amerykańscy badacze Cormen, Leiserson, Rivest i Stein opisali rekurencyjną podstrukturyzację rozwiązań zachłannych w swojej klasycznej pracy Introduction to Algorithms podręcznik.
• Paradygmat wyszukiwania zachłannego został skatalogowany jako odrębna strategia optymalizacji w dokumentach NIST w 2005 r.
• Do dziś protokoły sieciowe, takie jak OSPF (Open Shortest Path First) i wiele protokołów przełączania pakietów wykorzystują strategię zachłanną w celu zminimalizowania czasu przesyłania danych w sieci.

Chciwe strategie i decyzje

Logika ta sprowadza się do binarnego wyboru na każdym etapie — „chciwy” lub „niechciwy” — w zależności od kierunku, w którym podąża algorytm.

Na przykład algorytm Dijkstry identyfikuje hosty w Internecie, obliczając funkcję kosztu na każdym kroku. Wartość zwracana przez funkcję kosztu decyduje o tym, czy następna ścieżka jest „chciwa”, czy „niechciwa”.

Krótko mówiąc, algorytm przestaje być zachłanny w chwili, gdy wykona krok, który nie jest lokalnie optymalny, a problemy zachłanne kończą się, gdy nie jest możliwe wykonanie kolejnego kroku zachłannego.

Charakterystyka algorytmu zachłannego

Ważnymi cechami algorytmu zachłannego są:

• Uporządkowana lista zasobów niesie ze sobą przypisanie kosztów lub wartości, które określają ograniczenia systemu.
• Algorytm wykorzystuje maksymalną ilość zasobów w czasie obowiązywania ograniczenia.
• Na przykład w problemie harmonogramowania działań koszty zasobów mierzy się w godzinach, a działania muszą być wykonywane w określonej kolejności.

Dlaczego warto stosować podejście chciwe?

Oto powody stosowania podejścia zachłannego:

• Podejście chciwe ma swoje wady i zalety, które sprawiają, że dobrze nadaje się do optymalizacji.
• Najbardziej oczywistym powodem jest natychmiastowe wygenerowanie wykonalnego rozwiązania. W omawianym poniżej problemie wyboru aktywności, jeśli więcej aktywności zmieści się przed zakończeniem bieżącej aktywności, można je zaplanować w tym samym oknie.
• Innym powodem jest to, że dzieli problem rekurencyjnie na podstawie warunku, bez potrzeby scalania podrozwiązań.
• W problemie wyboru aktywności krok dzielenia rekurencyjnego polega na jednokrotnym przejrzeniu listy i uwzględnieniu tylko aktywności spełniających kryteria.

Jak rozwiązać problem wyboru aktywności

W przykładzie harmonogramowania aktywności każda aktywność ma godzinę rozpoczęcia i zakończenia oraz jest indeksowana numerem w celach informacyjnych. Istnieją dwie kategorie aktywności:

1. Rozważana aktywność: działalność referencyjna, od której mierzona jest możliwość dopasowania pozostałych aktywności.
2. Pozostałe działania: działania na jednym lub większej liczbie indeksów przed rozważaną działalnością.

Kosztem wykonania czynności jest czas jej trwania, liczony według wzoru (zakończenie – rozpoczęcie).

Zakres zachłanny to po prostu liczba pozostałych czynności, które można wykonać w czasie rozważanej czynności.

Archicharakter podejścia zachłannego

Krok 1) Przejrzyj listę kosztów działań, zaczynając od indeksu 0 jako indeksu branego pod uwagę.

Krok 2) Jeśli do czasu zakończenia danej czynności można zakończyć więcej czynności, należy wyszukać pozostałe czynności.

Krok 3) Jeśli nie można zaplanować więcej aktywności, bieżąca pozostała aktywność staje się kolejną rozważaną aktywnością. Powtórz kroki 1 i 2 z nową rozważaną aktywnością. Jeśli nie pozostały żadne aktywności, przejdź do kroku 4.

Krok 4) Zwróć unię rozważanych indeksów — są to indeksy aktywności maksymalizujące przepustowość.

Archicharakter podejścia zachłannego

Code Wyjaśnienie

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Wyjaśnienie kodu:

1. Dołączone pliki nagłówkowe/klasy
2. Maksymalna liczba czynności, które może skonfigurować użytkownik.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Wyjaśnienie kodu:

1. Deklaruje standardową przestrzeń nazw dla operacji przesyłania strumieniowego.
2. Definicja klasy dla TIME
3. Znacznik czasu godziny.
4. Konstruktor domyślny TIME
5. Godziny są zmienne.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Wyjaśnienie kodu:

1. Definicja klasy dla Aktywności.
2. Znaczniki czasu, które razem definiują czas trwania.
3. Wszystkie znaczniki czasu są inicjowane wartością 0 w konstruktorze domyślnym.

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Wyjaśnienie kodu:

1. Część 1 definicji klasy programu planującego.
2. consider_index jest punktem początkowym skanowania tablicy.
3. init_index służy do przypisywania losowych znaczników czasu podczas konfiguracji.
4. Tablica obiektów Activity jest dynamicznie przydzielana za pomocą operatora new.
5. Zaplanowany wskaźnik przechowuje bieżący wynik chciwy.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Wyjaśnienie kodu:

1. Konstruktor Scheduler — część 2 definicji klasy.
2. consider_index oznacza początek bieżącego skanowania.
3. Zakres chciwości jest na początku nieokreślony.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
&#8230;
&#8230;

Wyjaśnienie kodu:

1. Pętla for inicjuje godziny rozpoczęcia i zakończenia każdej zaplanowanej czynności.
2. Inicjuje czas rozpoczęcia.
3. Inicjuje czas zakończenia tak, aby przypadał na godzinę rozpoczęcia lub późniejszą.
4. Polecenie debugowania drukuje przydzielone czasy trwania.

	public:
   		 Activity * activity_select(int);
};

Wyjaśnienie kodu:

1. Część 4 — ostatnia część definicji klasy Scheduler.
2. activity_select() przyjmuje indeks początkowy jako bazę i dzieli zachłanne zadanie na podproblemy.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. Operator rozwiązywania zakresu (::) łączy definicję funkcji z klasą Scheduler.
2. consider_index jest przekazywany przez wartość, a greedy_extent jest inicjowany na indeksie bezpośrednio po nim.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
&#8230;
...

Wyjaśnienie kodu:

1. Podstawowa logika — zakres chciwości jest ograniczony do MAX_ACTIVITIES.
2. Godzina rozpoczęcia bieżącej aktywności jest porównywana z godziną zakończenia rozważanej aktywności.
3. Dopóki warunek jest spełniony, drukowane jest opcjonalne polecenie debugowania.
4. Następnie zakres chciwy przechodzi do następnego indeksu w tablicy aktywności.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Wyjaśnienie kodu:

1. Funkcja warunkowa sprawdza, czy wszystkie działania zostały uwzględnione.
2. W przeciwnym razie algorytm rozpoczyna zadanie zachłanne od nowa od bieżącego indeksu — jest to krok rekurencyjny, który dzieli problem w sposób zachłanny.
3. Jeśli tak, kontrola powraca do osoby wywołującej, nie dając jej możliwości dalszego działania zachłannie.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Wyjaśnienie kodu:

1. Funkcja główna wywołuje Harmonogram.
2. Tworzony jest nowy obiekt Scheduler.
3. Funkcja activity_select() zwraca wskaźnik Activity do wywołującego po zakończeniu chciwego zadania.

Wyjście:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5
finish6
 activity:3

Schedule start:9
finish10
 activity:5

Ograniczenia techniki chciwej

Podejście zachłanne nie nadaje się do rozwiązywania problemów wymagających optymalnego rozwiązania dla każdego podproblemu, np. sortowania.

W takich przypadkach metoda chciwa może okazać się błędna — w najgorszym przypadku doprowadzi do rozwiązania nieoptymalnego.

Podstawową wadą algorytmów chciwych jest to, że dokonują wyboru nie wiedząc, co będzie dalej po bieżącym stanie chciwości.

Poniższy diagram ilustruje tę wadę metody chciwej.

W skanowaniu zachłannym przedstawionym tutaj w formie drzewa (wyższa wartość oznacza większą zachłanność), algorytm o wartości 40 wybrałby następnie 29, a następnie zakończyłby na 12, co łącznie dałoby 41.

Z kolei strategia „dziel i rządź” zastosowana do 25 punktów przy 40 dałaby łącznie 65, co stanowi wynik o 24 punkty wyższy niż lokalna chciwość.

Przykłady chciwości Algorithms

Większość algorytmów sieciowych opiera się na podejściu zachłannym. Typowe przykłady algorytmów zachłannych obejmują:

• Algorytm minimalnego drzewa rozpinającego Prima
• Problem komiwojażera (przybliżony)
• Kolorowanie wykresów i map
• Algorytm minimalnego drzewa rozpinającego Kruskala
• Algorytm najkrótszej ścieżki Dijkstry
• Pokrycie wierzchołków grafu
• Problem z plecakiem
• Sekwencjonowanie zadań z terminami

FAQ