Wprowadzenie do algorytmu zachłannego
Strategia stosowana do rozwiązywania problemów. Chciwy Algorytm jest uważany za jedno z podejść stosowanych do rozwiązywania problemów. Ten heretyk rozwiązujący problemy idzie w parze z wyborem, który wydaje się najlepszy w danym momencie. Takie podejście najlepiej wykorzystać do rozwiązania problemów związanych z optymalizacją. Problemy z optymalizacją można zdefiniować jako problemy wymagające minimalnych lub maksymalnych wyników. Algorytm Chciwy jest najprostszym i najprostszym podejściem, które można zastosować w celu osiągnięcia optymalnego rozwiązania.
Co to jest Chciwy Algorytm?
Chciwy Algorytm to strategia algorytmiczna stosowana do dokonywania najlepszego opcjonalnego wyboru na bardzo małym etapie, przy jednoczesnym uzyskaniu optymalnego globalnie rozwiązania. Ten algorytm wybiera najlepsze możliwe rozwiązanie w danym momencie, bez względu na jakiekolwiek konsekwencje. Chciwa metoda mówi, że problem należy rozwiązywać etapami, w których każdy wkład jest rozważany, biorąc pod uwagę, że wkład ten jest wykonalny. Ponieważ takie podejście koncentruje się tylko na natychmiastowym wyniku, bez względu na szerszy obraz, jest uważane za chciwe.
Definiowanie podstawowej koncepcji
Do tej pory wiemy, czym jest chciwy algorytm i dlaczego tak się nazywa. Poniższe wskazówki pozwolą lepiej zrozumieć chciwy algorytm. Do tej pory stało się jasne, że chciwy algorytm działa tylko wtedy, gdy występuje problem; niemniej jednak takie podejście ma zastosowanie tylko wtedy, gdy mamy warunek lub ograniczenie tego problemu.
Rodzaje problemów
- Problem minimalizacji: Rozwiązanie problemu jest łatwe, biorąc pod uwagę, że wszystkie warunki są spełnione. Jednak gdy ten problem wymaga minimalnego rezultatu, nazywa się go wówczas problemem minimalizacji.
- Problem maksymalizacji : Problem wymagający maksymalnego wyniku jest znany jako problem maksymalizacji.
- Problem optymalizacji: Problem nazywa się problemem optymalizacji, gdy wymaga on minimalnych lub maksymalnych wyników.
Rodzaje rozwiązań
- Możliwe rozwiązanie: Teraz, gdy pojawia się problem, mamy wiele możliwych rozwiązań tego problemu. Jednak biorąc pod uwagę warunek ustawiony dla tego problemu, wybieramy rozwiązania, które spełniają dany warunek. Takie rozwiązania, które pomagają nam uzyskać wyniki spełniające dany warunek, nazywane są rozwiązaniem wykonalnym .
- Optymalne rozwiązanie: Rozwiązanie nazywa się optymalnym, gdy jest już wykonalne i osiąga cel problemu; najlepszy wynik. Ten cel może być wynikiem minimalnym lub maksymalnym. Należy tutaj zauważyć, że każdy problem będzie miał tylko jedno optymalne rozwiązanie.
Poniższy przykład pozwoli łatwo zrozumieć chciwą metodę. Powiedzmy, że chce się kupić najlepszy samochód dostępny na rynku. Jedną z metod wyboru tego samochodu jest analiza wszystkich samochodów na rynku. Teraz, ponieważ jest to czasochłonne, aby ułatwić wybranie samochodu od konkretnych marek, w które chcemy zainwestować. Kategoryzując to dalej, ponownie wybierzemy pożądane modele, biorąc pod uwagę jego cechy. Dlatego zastosowane tutaj podejście jest zachłanne, ponieważ to rozwiązanie było dla Ciebie optymalne, biorąc pod uwagę wszystkie czynniki, które były dla Ciebie korzystne.
Podstawowe elementy chciwego algorytmu
Teraz, gdy lepiej zrozumiemy ten mechanizm, zbadajmy podstawowe elementy chciwego algorytmu, który odróżnia go od innych procesów:
- Zestaw kandydacki: z tego zestawu tworzona jest odpowiedź.
- Funkcja wyboru: Wybiera najlepszego kandydata do włączenia do rozwiązania.
- Funkcja wykonalności: w tej sekcji oblicza się, czy kandydata można użyć do wniesienia wkładu w rozwiązanie.
- Funkcja celu: przypisuje wartość do pełnego lub częściowego rozwiązania.
- Funkcja rozwiązania: służy do wskazania, czy spełnione jest właściwe rozwiązanie.
Gdzie najlepiej działa Chciwy Algorytm?
Chciwy Algorytm można zastosować do wyżej wymienionych problemów.
- Podejścia Chciwego można użyć do znalezienia minimalnego wykresu drzewa opinającego za pomocą algorytmu Prim lub Kruskala
- Znalezienie najkrótszej ścieżki między dwoma wierzchołkami to kolejny problem, który można rozwiązać za pomocą chciwego algorytmu. Zastosowanie algorytmu Dijkstry wraz z algorytmem zachłannym zapewni optymalne rozwiązanie.
- Kodowanie Huffmana
Zalety
Największą zaletą algorytmu Chciwy nad innymi jest to, że jest łatwy do wdrożenia i bardzo wydajny w większości przypadków.
Niedogodności
Chciwy Algorytm zasadniczo buduje rozwiązanie część po części i wybiera następną część w taki sposób, aby natychmiast uzyskać najlepsze rozwiązanie obecnego problemu. W rezultacie konsekwencje podjętej obecnie decyzji nie mają znaczenia ani obaw. Nigdy nie zastanawiając się nad poprzednio wybranymi wyborami, Chciwy Algorytm nie daje optymalnego rozwiązania, choć daje prawie optymalne rozwiązanie . Problem plecaka i problem podróżującego sprzedawcy są przykładami problemów, w których Chciwy Algorytm nie zapewnia optymalnego rozwiązania.
- Problem plecaka : Najczęściej znany pod nazwą problem plecaka, jest codziennym problemem, z którym boryka się wiele osób. Powiedzmy, że mamy zestaw przedmiotów i każdy ma inną wagę i wartość (zysk) niż wypełniony do pojemnika lub powinien być zebrany w taki sposób, aby całkowita waga była mniejsza lub równa wadze pojemnika, podczas gdy całkowity zysk jest zmaksymalizowany .
Wniosek
Chciwy Algorytm najlepiej nadaje się, gdy potrzebne jest rozwiązanie w czasie rzeczywistym, a przybliżone odpowiedzi są „wystarczająco dobre”. Oczywiście, zachłanny algorytm minimalizuje czas, jednocześnie upewniając się, że powstaje optymalne rozwiązanie, dlatego bardziej nadaje się do zastosowania w sytuacji, gdy potrzeba mniej czasu. Po przeczytaniu tego artykułu można mieć dobry pomysł na chciwe algorytmy. Ponadto w tym poście wyjaśniono, dlaczego uważa się go za najlepsze środowisko, które odpowiada na prawie wszystkie wyzwania programistyczne, a także pomaga w wyborze najbardziej optymalnego rozwiązania w danym momencie.
Z drugiej strony, aby zastosować teorię algorytmu chciwego, trzeba ciężko pracować, aby poznać poprawne problemy. Chociaż jest to koncepcja naukowa, która ma logikę, ma także istotę kreatywności.
Polecane artykuły
To był przewodnik po czym jest chciwy algorytm. Tutaj omówiliśmy Podstawową koncepcję, komponenty, zalety i wady chciwego algorytmu. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -
- Algorytm w programowaniu
- Co to jest Perl?
- Wprowadzenie do algorytmu
- Co to jest Agile Sprint?