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

Aby zrozumieć podejście zachłanne, musisz posiadać praktyczną wiedzę na temat rekurencji i przełączania kontekstu. Pomoże Ci to zrozumieć, jak śledzić kod. Paradygmat zachłanności można zdefiniować w kategoriach własnych stwierdzeń koniecznych i wystarczających.

Paradygmat zachłanności definiują dwa warunki.

• Każde rozwiązanie krok po kroku musi doprowadzić problem do najlepszego możliwego do zaakceptowania rozwiązania.
• Wystarczy, jeśli konstruowanie problemu można zatrzymać w skończonej liczbie zachłannych kroków.

Kontynuując teoretyzowanie, opiszmy historię związaną z podejściem do wyszukiwania zachłannego.

Historia Chciwości Algorithms

Oto ważny punkt odniesienia w algorytmach zachłannych:

• W latach 1950. XX wieku opracowano koncepcję algorytmów zachłannych dla wielu algorytmów przeglądania grafów.
• Esdger Djikstra opracował koncepcję algorytmu generowania minimalnych drzew rozpinających. Zamierzał skrócić rozpiętość tras w obrębie stolicy Holandii, Amsterdamu.
• W tej samej dekadzie firmy Prim i Kruskal osiągnęły strategie optymalizacyjne polegające na minimalizacji kosztów tras po trasach ważonych.
• W latach 70. amerykańscy badacze Cormen, Rivest i Stein w swoim klasycznym wprowadzeniu do algorytmów zaproponowali rekurencyjną podstrukturyzację rozwiązań zachłannych.
• Paradygmat wyszukiwania zachłannego został zarejestrowany jako inny typ strategii optymalizacji w dokumentach NIST w 2005 roku.
• Do chwili obecnej protokoły obsługujące sieć, takie jak OSPF (Open-Shortest-path-first) i wiele innych sieciowych protokołów przełączania pakietów, korzystają ze strategii zachłannej, aby zminimalizować czas spędzony w sieci.

Chciwe strategie i decyzje

Logika w najprostszej formie sprowadzała się do „chciwości” lub „niechciwości”. Stwierdzenia te zostały zdefiniowane w oparciu o podejście przyjęte w celu osiągnięcia postępu na każdym etapie algorytmu.

Na przykład algorytm Djikstry wykorzystywał krokową strategię zachłanną, identyfikując hosty w Internecie poprzez obliczenie funkcji kosztu. Wartość zwrócona przez funkcję kosztu określała, czy następna ścieżka jest „zachłanna” czy „niezachłanna”.

Krótko mówiąc, algorytm przestaje być zachłanny, jeśli na którymkolwiek etapie wykona krok, który nie jest lokalnie zachłanny. Problemy chciwości ustają bez dalszego zakresu chciwości.

Charakterystyka algorytmu zachłannego

Ważnymi cechami algorytmu zachłannego są:

• Istnieje uporządkowana lista zasobów z kosztami lub przypisaniami wartości. Określają one ilościowo ograniczenia systemu.
• Pobierzesz maksymalną ilość zasobów w czasie obowiązywania ograniczenia.
• Na przykład w problemie harmonogramowania działań koszty zasobów są wyrażane w godzinach, a działania muszą być wykonywane w określonej kolejności.

Dlaczego warto stosować podejście zachłanne?

Oto powody stosowania podejścia zachłannego:

• Podejście zachłanne ma kilka kompromisów, co może sprawić, że będzie odpowiednie do optymalizacji.
• Jednym z najważniejszych powodów jest natychmiastowe osiągnięcie najbardziej wykonalnego rozwiązania. W przypadku problemu wyboru czynności (wyjaśnionego poniżej), jeśli przed zakończeniem bieżącej czynności można wykonać więcej czynności, można je wykonać w tym samym czasie.
• Innym powodem jest rekurencyjny podział problemu na podstawie warunku, bez konieczności łączenia wszystkich rozwiązań.
• W problemie wyboru czynności etap „podziału rekurencyjnego” realizowany jest poprzez jednokrotne przeskanowanie listy pozycji i rozważenie określonych czynności.

Jak rozwiązać problem wyboru aktywności

W przykładzie planowania działań istnieje czas „rozpoczęcia” i „zakończenia” każdego działania. Każde działanie jest indeksowane numerem w celach informacyjnych. Istnieją dwie kategorie aktywności.

1. rozważana aktywność: jest Aktywnością, która jest odniesieniem, na podstawie którego analizowana jest możliwość wykonania więcej niż jednej pozostałej Aktywności.
2. pozostałe zajęcia: działania na jednym lub większej liczbie indeksów przed rozważaną działalnością.

Całkowity czas trwania określa koszt wykonania czynności. Oznacza to, że (koniec – początek) daje nam czas trwania jako koszt działania.

Dowiesz się, że stopień zachłanności to liczba pozostałych czynności, które możesz wykonać w czasie rozpatrywanej czynności.

Archicharakter podejścia zachłannego

KROK 1) Przeskanuj listę kosztów działalności, zaczynając od indeksu 0 jako rozpatrywanego Indeksu.

KROK 2) Gdy do czasu zakończenia danej czynności uda się ukończyć więcej czynności, rozpoczyna się wyszukiwanie jednej lub więcej pozostałych czynności.

KROK 3) Jeśli nie ma już żadnych pozostałych działań, bieżąca pozostała czynność staje się następną braną pod uwagę aktywnością. Powtórz krok 1 i krok 2 z nową rozważaną aktywnością. Jeśli nie pozostały już żadne czynności, przejdź do kroku 4.

KROK 4 ) Zwróć sumę rozważanych indeksów. Są to wskaźniki aktywności, które zostaną wykorzystane w celu maksymalizacji przepustowości.

Objaśnienie kodu

#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 aktywności udostępniona przez użytkownika.

using namespace std;

class TIME
{
    public:
    int hours;

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

Wyjaśnienie kodu:

1. 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 na podstawie działania
2. Znaczniki czasu określające czas trwania
3. Wszystkie znaczniki czasu są inicjowane na 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. Rozważany indeks jest punktem wyjścia do skanowania szyk.
3. Indeks inicjalizacji służy do przypisywania losowych znaczników czasu.
4. Tablica obiektów aktywności jest dynamicznie przydzielana za pomocą operatora new.
5. Zaplanowany wskaźnik definiuje bieżącą lokalizację bazową dla zachłanności.

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

Wyjaśnienie kodu:

1. Konstruktor harmonogramu – część 2 definicji klasy harmonogramu.
2. Uwzględniany indeks określa bieżący początek bieżącego skanowania.
3. Obecny zasięg zachłannoś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);
 }
…
…

Wyjaśnienie kodu:

1. Pętla for inicjująca godziny rozpoczęcia i zakończenia każdej z aktualnie zaplanowanych czynności.
2. Inicjalizacja czasu rozpoczęcia.
3. Inicjalizacja czasu zakończenia zawsze po lub dokładnie o godzinie rozpoczęcia.
4. Instrukcja debugowania służąca do wydrukowania przydzielonych czasów trwania.

	public:
   		 Activity * activity_select(int);
};

Wyjaśnienie kodu:

1. Część 4 – ostatnia część definicji klasy planisty.
2. Funkcja wyboru działania przyjmuje jako podstawę indeks punktu początkowego i dzieli zachłanne zadanie na zachłanne podproblemy.

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

1. Definicja funkcji jest podawana za pomocą operatora rozdzielczości zakresu (::).
2. Rozważany Indeks to Indeks wywoływany przez wartość. Greedy_extent jest inicjowanym indeksem po rozpatrywanym indeksie.

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++;
    	}
…
...

Wyjaśnienie kodu:

1. Podstawowa logika – zachłanność ogranicza się do liczby działań.
2. Godziny rozpoczęcia bieżącej Aktywności są sprawdzane pod kątem możliwości zaplanowania ich przed zakończeniem rozważanej Aktywności (określonej za pomocą rozważanego indeksu).
3. O ile to możliwe, drukowana jest opcjonalna instrukcja debugowania.
4. Przejdź 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. Warunek sprawdza, czy wszystkie działania zostały uwzględnione.
2. Jeśli nie, możesz ponownie uruchomić zachłanność z rozważanym Indeksem jako bieżącym punktem. Jest to krok rekurencyjny, który zachłannie dzieli opis problemu.
3. Jeśli tak, wraca do dzwoniącego bez możliwości rozszerzenia chciwości.

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

Wyjaśnienie kodu:

1. Główna funkcja używana do wywoływania harmonogramu.
2. Tworzona jest instancja nowego harmonogramu.
3. Funkcja wyboru działania, która zwraca wskaźnik typu działania, wraca do osoby wywołującej po zakończeniu zachłannej wyprawy.

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

Nie nadaje się do problemów zachłannych, gdzie wymagane jest rozwiązanie dla każdego podproblemu, np. sortowanie.

W przypadku takich problemów praktycznych z algorytmem Greedy'ego metoda Greedy może być błędna; w najgorszym przypadku prowadzić nawet do nieoptymalnego rozwiązania.

Dlatego wadą algorytmów zachłannych jest to, że nie wiemy, co czeka nas przed aktualnym stanem zachłannym.

Poniżej przedstawiono wady metody Greedy:

W skanie zachłannym pokazanym tutaj jako drzewo (wyższa wartość, wyższa zachłanność), stan algorytmu przy wartości: 40 prawdopodobnie przyjmie 29 jako następną wartość. Co więcej, jego misja kończy się na 12. Daje to wartość 41.

Jeśli jednak algorytm obrał nieoptymalną ścieżkę lub przyjął strategię podboju. po 25 nastąpi 40, a ogólna poprawa kosztów wyniesie 65, co jest oceniane o 24 punkty wyżej jako decyzja nieoptymalna.

Przykłady chciwości Algorithms

Większość algorytmów sieciowych używa podejścia chciwego. Oto lista kilku przykładów algorytmów chciwych:

• Algorytm minimalnego drzewa opinającego Prima
• Problem sprzedawcy podróży
• Wykres – Kolorowanie mapy
• Algorytm minimalnego drzewa opinającego Kruskala
• Algorytm minimalnego drzewa opinającego Dijkstry
• Wykres – pokrycie wierzchołków
• Problem z plecakiem
• Problem z planowaniem pracy

Podsumowanie

Podsumowując, artykuł zdefiniował paradygmat chciwości, pokazał, jak optymalizacja chciwa i rekurencja mogą pomóc Ci uzyskać najlepsze rozwiązanie do pewnego stopnia. Algorytm chciwy jest szeroko stosowany do rozwiązywania problemów w wielu językach jako algorytm chciwy Python, C, C#, PHP, Javaitp. Wybór aktywności w przykładzie algorytmu zachłannego został opisany jako problem strategiczny, który umożliwia osiągnięcie maksymalnej przepustowości przy zastosowaniu podejścia zachłannego. Na koniec wyjaśniono wady stosowania podejścia zachłannego.