Algorytm zachłanności z przykładami: metoda chciwości & Podejście

Spisie treści:

Anonim

Co to jest algorytm chciwości?

W Greedy Algorithm zbiór zasobów jest rekurencyjnie dzielony na podstawie maksymalnej, natychmiastowej dostępności tego zasobu na dowolnym etapie wykonywania.

Aby rozwiązać problem oparty na chciwym podejściu, są dwa etapy

  1. Skanowanie listy pozycji
  2. Optymalizacja

Etapy te są omówione równolegle w tym samouczku dotyczącym algorytmu Greedy'ego, na temat przebiegu dzielenia tablicy.

Aby zrozumieć zachłanne podejście, będziesz potrzebować praktycznej wiedzy na temat rekurencji i przełączania kontekstów. Pomaga to zrozumieć, jak śledzić kod. Możesz zdefiniować chciwy paradygmat za pomocą własnych niezbędnych i wystarczających stwierdzeń.

Dwa warunki definiują chciwy paradygmat.

  • Każde rozwiązanie krokowe musi ustrukturyzować problem w kierunku najlepszego zaakceptowanego rozwiązania.
  • Wystarczy, że ustrukturyzowanie problemu może zatrzymać się w skończonej liczbie zachłannych kroków.

Kontynuując teoretyzowanie, opiszmy historię związaną z podejściem Greedy search.

W tym samouczku dotyczącym algorytmu Greedy dowiesz się:

  • Historia chciwych algorytmów
  • Chciwe strategie i decyzje
  • Charakterystyka podejścia chciwego
  • Dlaczego warto skorzystać z chciwego podejścia?
  • Jak rozwiązać problem z wyborem zajęć
  • Architektura podejścia chciwego
  • Wady algorytmów zachłannych

Historia chciwych algorytmów

Oto ważny punkt orientacyjny zachłannych algorytmów:

  • Algorytmy Greedy zostały opracowane dla wielu algorytmów poruszania się po grafach w latach 50.
  • Esdger Djikstra opracował konceptualizację algorytmu do generowania minimalnych drzew rozpinających. Jego celem było skrócenie rozpiętości tras w stolicy Holandii, Amsterdamie.
  • W tym samym dziesięcioleciu Prim i Kruskal osiągnęli strategie optymalizacji, które opierały się na minimalizacji kosztów tras na ważonych trasach.
  • W latach 70. amerykańscy badacze Cormen, Rivest i Stein zaproponowali rekurencyjne substrukturyzowanie zachłannych rozwiązań w ich klasycznym wprowadzeniu do książki o algorytmach.
  • Paradygmat Greedy search został zarejestrowany jako inny rodzaj strategii optymalizacji w rekordach NIST w 2005 roku.
  • Do tej pory protokoły działające w Internecie, takie jak Open-Shortest-Path-First (OSPF) i wiele innych protokołów przełączania pakietów sieciowych, wykorzystują strategię zachłanności, aby zminimalizować czas spędzany w sieci.

Chciwe strategie i decyzje

Logika w swojej najprostszej postaci sprowadzała się do „chciwości” lub „nie chciwości”. Stwierdzenia te zostały określone przez podejście przyjęte na każdym etapie algorytmu.

Na przykład algorytm Djikstry wykorzystał stopniową zachłanną strategię identyfikowania hostów w Internecie poprzez obliczenie funkcji kosztu. Wartość zwracana przez funkcję kosztu określa, czy następna ścieżka jest „chciwa” czy „niechciwa”.

Krótko mówiąc, algorytm przestaje być chciwy, jeśli na jakimkolwiek etapie podejmuje krok, który nie jest lokalnie chciwy. Problemy chciwości ustają bez dalszego zasięgu chciwości.

Charakterystyka podejścia chciwego

Ważnymi cechami algorytmu metody Greedy są:

  • Istnieje uporządkowana lista zasobów z przypisaniem kosztów lub wartości. Te ilościowo określają ograniczenia w systemie.
  • Wykorzystasz maksymalną ilość zasobów w czasie obowiązywania ograniczenia.
  • Na przykład w przypadku problemu z planowaniem działań koszty zasobów są wyrażone w godzinach, a czynności muszą być wykonywane w kolejności seryjnej.

Dlaczego warto skorzystać z chciwego podejścia?

Oto powody stosowania chciwego podejścia:

  • Chciwe podejście ma kilka kompromisów, co może sprawić, że będzie ono odpowiednie do optymalizacji.
  • Jednym z głównych powodów jest natychmiastowe osiągnięcie najbardziej realnego rozwiązania. W przypadku problemu wyboru czynności (wyjaśnionego poniżej), jeśli można wykonać więcej czynności przed zakończeniem bieżącej czynności, czynności te można wykonać w tym samym czasie.
  • Innym powodem jest rekurencyjny podział problemu na podstawie warunku, bez konieczności łączenia wszystkich rozwiązań.
  • W przypadku problemu z wyborem czynności krok „podziału rekurencyjnego” uzyskuje się przez jednokrotne skanowanie listy elementów i rozważenie określonych czynności.

Jak rozwiązać problem z wyborem zajęć

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

  1. rozpatrywana czynność : jest to działanie, które jest odniesieniem, na podstawie którego analizowana jest zdolność do wykonania więcej niż jednej pozostałej czynności.
  2. pozostałe działania: działania o co najmniej jednym indeksie przed rozważaną czynnością.

Całkowity czas trwania podaje koszt wykonania czynności. Oznacza to, że (koniec - początek) podaje 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 rozważanej czynności.

Architektura podejścia chciwego

KROK 1)

Przejrzyj listę kosztów działań, zaczynając od indeksu 0 jako rozpatrywanego indeksu.

KROK 2)

Gdy do określonego czasu można zakończyć więcej działań, a dane działanie dobiegnie końca, rozpocznij wyszukiwanie co najmniej jednego pozostałego działania.

KROK 3)

Jeśli nie ma już pozostałych działań, bieżąca pozostała czynność staje się kolejną braną pod uwagę czynnością. Powtórz kroki 1 i 2 z nowym rozważanym działaniem. Jeśli nie zostały już żadne czynności, przejdź do kroku 4.

KROK 4 )

Zwróć sumę rozważanych wskaźników. Są to wskaźniki aktywności, które będą używane do maksymalizacji przepustowości.

Architektura podejścia chciwego

Objaśnienie kodu

#include#include#include#define MAX_ACTIVITIES 12

Wyjaśnienie kodu:

  1. Dołączone pliki / klasy nagłówkowe
  2. Maksymalna liczba czynności wykonywanych 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. Sygnatura czasowa godziny.
  4. Konstruktor domyślny TIME
  5. Zmienna godzin.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Wyjaśnienie kodu:

  1. Definicja klasy na podstawie aktywności
  2. Znaczniki czasu określające czas trwania
  3. Wszystkie znaczniki czasu są inicjalizowane na 0 w domyślnym konstruktorze
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 tablicy.
  3. Indeks inicjalizacji służy do przypisywania losowych znaczników czasu.
  4. Tablica obiektów działań jest dynamicznie alokowana przy użyciu nowego operatora.
  5. Zaplanowany wskaźnik określa bieżącą lokalizację bazową chciwości.
Scheduler(){considered_index = 0;scheduled = NULL;… …

Wyjaśnienie kodu:

  1. Konstruktor harmonogramu - część 2 definicji klasy harmonogramu.
  2. Rozważany indeks określa aktualny początek bieżącego skanowania.
  3. Obecny stopień 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żdego z aktualnie zaplanowanych działań.
  2. Czas rozpoczęcia inicjalizacji.
  3. Czas zakończenia inicjalizacji zawsze po godzinie rozpoczęcia lub dokładnie o tej godzinie.
  4. Instrukcja debugowania do wydrukowania przydzielonych czasów trwania.
public:Activity * activity_select(int);};

Wyjaśnienie kodu:

  1. Część 4 - ostatnia część definicji klasy harmonogramu.
  2. Funkcja wyboru aktywności przyjmuje indeks punktu początkowego jako podstawę i dzieli chciwe poszukiwania na chciwe podproblemy.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …

  1. Za pomocą operatora rozpoznawania zakresu (: :) udostępniana jest definicja funkcji.
  2. Rozważany indeks to indeks nazywany wartością. Greedy_extent to zainicjowany tylko indeks po rozważanym 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 - chciwość ogranicza się do liczby działań.
  2. Godziny rozpoczęcia bieżącego działania są sprawdzane jako możliwe do zaplanowania przed zakończeniem rozważanego działania (określonego przez rozważany indeks).
  3. Tak długo, jak 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. Warunkowe sprawdzenie, czy wszystkie działania zostały uwzględnione.
  2. Jeśli nie, możesz ponownie uruchomić chciwość z rozważanym indeksem jako bieżącym punktem. Jest to krok rekurencyjny, który zachłannie dzieli stwierdzenie 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 aktywności, która zwraca wskaźnik typu aktywność wraca do dzwoniącego po zakończeniu chciwego poszukiwania.

Wynik:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Wady algorytmów zachłannych

Nie nadaje się do problemów Greedy, w których wymagane jest rozwiązanie każdego podproblemu, takiego jak sortowanie.

W takich problemach z praktyką algorytmu Greedy metoda Greedy może być błędna; w najgorszym przypadku nawet prowadzi do nieoptymalnego rozwiązania.

Dlatego wadą zachłannych algorytmów jest brak wiedzy o tym, co znajduje się przed obecnym zachłannym stanem.

Poniżej znajduje się opis wady metody Greedy:

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

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

Przykłady zachłannych algorytmów

Większość algorytmów sieciowych stosuje podejście zachłanne. Oto lista kilku przykładów algorytmów Greedy:

  • Algorytm minimalnego drzewa opinającego Prim
  • Problem komiwojażera
  • Wykres - kolorowanie mapy
  • Algorytm minimalnego drzewa opinającego Kruskala
  • Algorytm minimalnego drzewa rozpinającego Dijkstry
  • Wykres - pokrycie wierzchołków
  • Problem z plecakiem
  • Problem z planowaniem pracy

Podsumowanie:

Podsumowując, artykuł zdefiniował chciwy paradygmat, pokazał, jak chciwa optymalizacja i rekurencja mogą pomóc w uzyskaniu najlepszego rozwiązania do pewnego momentu. Algorytm Greedy jest szeroko stosowany w rozwiązywaniu problemów w wielu językach, takich jak algorytm Greedy Python, C, C #, PHP, Java itp. Wybór działania przykładu algorytmu Greedy został opisany jako problem strategiczny, który mógłby osiągnąć maksymalną przepustowość przy użyciu metody chciwego podejście. W końcu wyjaśniono wady stosowania chciwego podejścia.