Chciwe algorytmy to klasa algorytmów, które tworzą lokalnie optymalne wyborów na każdym kroku z nadzieją znalezienia optymalne globalne rozwiązanie. W algorytmach tych decyzje podejmowane są na podstawie informacji dostępnych w danym momencie, bez uwzględnienia konsekwencji tych decyzji w przyszłości. Kluczową ideą jest wybranie na każdym etapie najlepszego możliwego wyboru, prowadzącego do rozwiązania, które nie zawsze jest najbardziej optymalne, ale często jest wystarczające w przypadku wielu problemów.

W tym artykule zrozumiemy algorytmy zachłanne na przykładach. Przyjrzymy się także problemom i ich rozwiązaniom, stosując podejście zachłanne.

Chciwe algorytmy

Spis treści

kolejka i kolejka priorytetowa w Javie

• Co to jest algorytm zachłanny?
• Kroki tworzenia zachłannego algorytmu
• Przykłady zachłannych algorytmów
• Zastosowania algorytmu zachłannego
• Wady/ograniczenia stosowania algorytmu zachłannego
• Podstawy algorytmu zachłannego
• Standardowe algorytmy zachłanne
• Chciwe problemy na Array
• Chciwe problemy w systemie operacyjnym
• Chciwi problemy na wykresie
• Przybliżony algorytm zachłanny dla NP został ukończony
• Chciwy na specjalne przypadki DP
• Łatwe problemy w algorytmie zachłannym
• Średnie problemy w algorytmie zachłannym
• Trudne problemy w algorytmie zachłannym

Co to jest algorytm zachłanny?

A zachłanny algorytm to rodzaj algorytmu optymalizacji, który dokonuje lokalnie optymalnych wyborów na każdym etapie, aby znaleźć globalnie optymalne rozwiązanie. Działa na zasadzie wyboru najlepszej opcji już teraz, bez rozważania długoterminowych konsekwencji.

Aby dowiedzieć się czym jest metoda zachłanna i jak stosować podejście zachłanne, przeczytaj podany tutorial na temat algorytmu zachłannego:

Kroki tworzenia zachłannego algorytmu

Aby zdefiniować algorytm zachłanny, należy wykonać następujące kroki:

1. Zdefiniuj problem: Jasno określ problem do rozwiązania i cel, który należy zoptymalizować.
2. Zidentyfikuj zachłanny wybór: Określ lokalnie optymalny wybór na każdym etapie w oparciu o bieżący stan.
3. Dokonaj zachłannego wyboru: Wybierz zachłanny wybór i zaktualizuj bieżący stan.
4. Powtarzać: Kontynuuj dokonywanie chciwych wyborów, aż znajdziesz rozwiązanie.

Wykonując podane kroki, można dowiedzieć się, jak używać algorytmów zachłannych do znajdowania optymalnych rozwiązań.

Przykłady zachłannych algorytmów

Najlepszym sposobem na zrozumienie algorytmu są przykłady algorytmów zachłannych. Oto kilka przykładów z życia wziętych algorytmów zachłannych:

• Ułamkowy plecak : Optymalizuje wartość przedmiotów, które można ułamkowo zmieścić w plecaku o ograniczonej pojemności.
• Algorytm Dijkstry : Znajduje najkrótszą ścieżkę od wierzchołka źródłowego do wszystkich pozostałych wierzchołków grafu ważonego.
• Algorytm Kruskala : Znajduje minimalne drzewo rozpinające grafu ważonego.
• Kodowanie Huffmana : Kompresuje dane, przypisując krótsze kody do częstszych symboli.

Zastosowania algorytmu zachłannego

Jest wiele zastosowania metody zachłannej w DAA . Niektóre ważne zastosowania algorytmów zachłannych to:

• Przypisywanie zadań do zasobów, aby zminimalizować czas oczekiwania lub zmaksymalizować wydajność.
• Wybieranie najcenniejszych przedmiotów tak, aby zmieściły się w plecaku o ograniczonej pojemności.
• Podział obrazu na obszary o podobnych cechach.
• Zmniejszenie rozmiaru danych poprzez usunięcie zbędnych informacji.

Wady/ograniczenia stosowania algorytmu zachłannego

Poniżej przedstawiono niektóre wady algorytmu zachłannego:

spać w j

• Zachłanne algorytmy nie zawsze znajdują najlepsze możliwe rozwiązanie.
• Kolejność, w jakiej rozważane są elementy, może znacząco wpłynąć na wynik.
• Algorytmy zachłanne skupiają się na lokalnych optymalizacjach i mogą pomijać lepsze rozwiązania, które wymagają uwzględnienia szerszego kontekstu.
• Algorytmy zachłanne nie mają zastosowania do problemów, w których zachłanny wybór nie prowadzi do optymalnego rozwiązania.

Podstawy algorytmu zachłannego:

• Zachłanne algorytmy (ogólna struktura i zastosowania)
• Różnica między algorytmem zachłannym a algorytmem dziel i zwyciężaj
• Chciwe podejście a programowanie dynamiczne
• Porównanie algorytmów Chciwości, Dziel i Rządź oraz Programowania Dynamicznego

Standardowe algorytmy zachłanne:

• Problem z wyborem działania
• Problem z kolejnością zadań
• Kodowanie Huffmana
• Dekodowanie Huffmana
• Problem z podłączeniem wody
• Minimalne swapy w celu wyważenia wsporników
• Frakcja egipska
• Policjanci łapią złodziei
• Problem z montażem półek
• Przypisz myszy do otworów

Chciwe problemy na tablicy:

• Minimalny podzbiór iloczynu tablicy
• Maksymalizuj sumę tablicy po K negacjach za pomocą sortowania
• Minimalna suma iloczynu dwóch tablic
• Minimalna suma bezwzględnej różnicy par dwóch tablic
• Minimalny przyrost/zmniejszenie, aby tablica nie zwiększała się
• Tablica sortująca z odwrotnością wokół środka
• Suma pól prostokątów możliwych dla tablicy
• Największa tablica leksykograficzna z maksymalnie K kolejnych zamian
• Podział na dwie podtablice o długości k i (N – k) tak, aby różnica sum była maksymalna

Chciwe problemy w systemie operacyjnym:

• Algorytm First Fit w zarządzaniu pamięcią
• Algorytm Best Fit w zarządzaniu pamięcią
• Algorytm najgorszego dopasowania w zarządzaniu pamięcią
• Najkrótsze planowanie pierwszego zadania
• Planowanie zadań z dwoma zadaniami dozwolonymi jednocześnie
• Program do optymalnego algorytmu zastępowania stron

Chciwe problemy na wykresie:

• Minimalne drzewo rozpinające Kruskala
• Minimalne drzewo rozpinające Prima
• Minimalne drzewo rozpinające Boruvki
• Algorytm najkrótszej ścieżki Dijkastry
• Algorytm wybierania
• Minimalny koszt połączenia wszystkich miast
• Wprowadzenie do problemu maksymalnego przepływu
• Liczba składowych pojedynczego cyklu w grafie nieskierowanym

Przybliżony algorytm zachłanny dla NP Ukończono:

• Ustaw problem z okładką
• Problem z pakowaniem do pojemników
• Kolorowanie wykresu
• Problem z centrami K
• Problem z najkrótszą superstruną
• Przybliżone rozwiązanie problemu komiwojażera przy użyciu MST

Chciwy na specjalne przypadki DP:

• Problem ułamkowego plecaka
• Wymagana minimalna liczba monet

Łatwe problemy na Greedy Algorytm :

• Podziel n na maksymalne liczby złożone
• Kup akcje maksymalne, jeśli i-tego dnia można kupić akcje
• Znajdź minimalną i maksymalną kwotę, aby kupić wszystkie N cukierków
• Maksymalna możliwa suma równa sumie trzech stosów
• Podziel prostopadłościan na kostki w taki sposób, aby suma objętości była największa
• Maksymalna liczba klientów, których można zadowolić daną ilością
• Minimalne obroty, aby odblokować okrągły zamek
• Minimalna liczba sal na m wydarzeń z n partii z podanym harmonogramem
• Minimalny koszt utworzenia tablicy o rozmiarze 1 poprzez usunięcie większych par
• Minimalny koszt nabycia wszystkich monet z dodatkowymi monetami dozwolonymi dla każdej monety
• Minimalny przyrost o k operacji, aby wszystkie elementy były równe
• Znajdź minimalną liczbę banknotów i wartości, które sumują się do podanej kwoty
• Najmniejszy podzbiór o sumie większej niż wszystkie pozostałe elementy

Średnie problemy na Greedy Algorytm :

• Maksymalna liczba pociągów, dla których można przewidzieć postój
• Minimalne wyrazy Fibonacciego o sumie równej K
• Podziel 1 do n na dwie grupy z minimalną różnicą sum
• Papier pocięty na minimalną liczbę kwadratów
• Minimalna różnica między grupami wielkości dwa
• Połącz n lin przy minimalnych kosztach
• Minimalna liczba peronów wymagana dla dworca kolejowego/autobusowego
• Minimalne początkowe wierzchołki, aby przejść przez całą macierz przy danych warunkach
• Największa liczba palindromowa poprzez permutację cyfr
• Znajdź najmniejszą liczbę o podanej liczbie cyfr i sumie cyfr
• Największy podciąg leksykograficzny taki, że każdy znak występuje co najmniej k razy

Trudne problemy na Greedy Algorytm :

• Maksymalne elementy, które można wyrównać za pomocą k aktualizacji
• Zminimalizuj przepływ środków pieniężnych wśród znajomych
• Minimalny koszt pocięcia deski na kwadraty
• Minimalny koszt przetwarzania m zadań, w przypadku których koszty zmiany są wysokie
• Minimalny czas na ukończenie wszystkich zadań przy danych ograniczeniach
• Minimalizuj maksymalną różnicę wysokości wież
• Minimalne krawędzie do odwrócenia, aby utworzyć ścieżkę od źródła do miejsca docelowego
• Znajdź największą kostkę utworzoną przez usunięcie minimalnych cyfr z liczby
• Zmień kolejność znaków w ciągu tak, aby żadne dwa sąsiednie nie były takie same
• Zmień układ ciągu tak, aby wszystkie te same znaki znajdowały się w odległości d

Szybkie linki:

• Naucz się struktury danych i algorytmów | Poradnik DSA
• 20 najpopularniejszych pytań do wywiadu na temat zachłannych algorytmów
• „Zadania praktyczne” dotyczące algorytmów zachłannych
• „Quiz” na temat zachłannych algorytmów