Metoda zachłanna jest jedną ze strategii takich jak Dziel i rządź, używaną do rozwiązywania problemów. Metodę tę stosuje się do rozwiązywania problemów optymalizacyjnych. Problem optymalizacji to problem, który wymaga maksymalnych lub minimalnych wyników. Rozumiemy za pomocą niektórych terminów.

Metoda zachłanna jest najprostszą i najszybszą metodą. To nie algorytm, ale technika. Główną funkcją tego podejścia jest podejmowanie decyzji na podstawie aktualnie dostępnych informacji. Bez względu na obecne informacje, decyzja jest podejmowana bez obawy o skutki bieżącej decyzji w przyszłości.

wstawianie Pythona

Technikę tę stosuje się zasadniczo do określenia wykonalnego rozwiązania, które może być optymalne lub nie. Rozwiązaniem dopuszczalnym jest podzbiór spełniający podane kryteria. Rozwiązaniem optymalnym jest rozwiązanie, które jest najlepszym i najkorzystniejszym rozwiązaniem w podzbiorze. W przypadku wykonalnych, jeżeli więcej niż jedno rozwiązanie spełnia podane kryteria, wówczas te rozwiązania zostaną uznane za wykonalne, natomiast rozwiązanie optymalne to rozwiązanie najlepsze spośród wszystkich rozwiązań.

Charakterystyka metody zachłannej

Poniżej przedstawiono cechy metody zachłannej:

• Aby skonstruować rozwiązanie w sposób optymalny, algorytm ten tworzy dwa zbiory, z których jeden zawiera wszystkie wybrane elementy, a drugi elementy odrzucone.
• Algorytm zachłanny dokonuje dobrych wyborów lokalnych w nadziei, że rozwiązanie będzie wykonalne lub optymalne.

Składniki algorytmu zachłannego

Elementy, które można wykorzystać w algorytmie zachłannym to:

Java czytaj CSV

Zestaw kandydata:Rozwiązanie utworzone na podstawie zbioru nazywa się zbiorem kandydującym.Funkcja selekcji:Funkcja ta służy do wyboru kandydata lub podzbioru, który można dodać do rozwiązania.Funkcja wykonalności:Funkcja używana do określenia, czy kandydat lub podzbiór mogą przyczynić się do rozwiązania, czy nie.Funkcja celu:Funkcja służy do przypisania wartości do rozwiązania lub rozwiązania częściowego.Funkcja rozwiązania:Funkcja ta służy do sprawdzenia, czy osiągnięto pełną funkcję, czy nie.

Zastosowania algorytmu zachłannego

• Służy do wyszukiwania najkrótszej ścieżki.
• Służy do znalezienia minimalnego drzewa rozpinającego przy użyciu algorytmu Prima lub algorytmu Kruskala.
• Jest używany w sekwencjonowaniu zadań z ostatecznym terminem.
• Algorytm ten służy również do rozwiązywania ułamkowego problemu plecakowego.

Pseudokod algorytmu Greedy

 Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } 

Powyższy algorytm jest zachłanny. Początkowo rozwiązaniu przypisuje się wartość zerową. W algorytmie zachłannym przekazujemy tablicę i liczbę elementów. Wewnątrz pętli for wybieramy jeden po drugim elementy i sprawdzamy, czy rozwiązanie jest wykonalne, czy nie. Jeśli rozwiązanie jest wykonalne, wykonujemy zjednoczenie.

Rozumiemy na przykładzie.

Załóżmy, że istnieje problem „P”. Chcę podróżować z punktu A do B, jak pokazano poniżej:

P: A → B

Problem w tym, że musimy odbyć tę podróż z A do B. Istnieją różne rozwiązania, aby przejść z A do B. Możemy przejść z A do B poprzez spacer, samochód, rower, pociąg, samolot itp. Istnieje ograniczenie w podróży, że musimy odbyć tę podróż w ciągu 12 godzin. Jeśli pojadę pociągiem lub samolotem tylko wtedy, tę odległość pokonam w ciągu 12 godzin. Istnieje wiele rozwiązań tego problemu, ale tylko dwa rozwiązania spełniają to ograniczenie.

Jeśli mówimy, że musimy pokryć podróż minimalnym kosztem. Oznacza to, że musimy przebyć tę odległość jak najmniej, więc problem ten nazywany jest problemem minimalizacji. Jak dotąd mamy dwa możliwe rozwiązania, tj. jedno koleją i drugie samolotem. Ponieważ podróż pociągiem wiąże się z minimalnymi kosztami, jest to więc rozwiązanie optymalne. Rozwiązanie optymalne to także rozwiązanie wykonalne, ale zapewniające najlepszy wynik, tak aby rozwiązanie było rozwiązaniem optymalnym przy minimalnych kosztach. Optymalne rozwiązanie byłoby tylko jedno.

Problem wymagający wyniku minimalnego lub maksymalnego nazywany jest problemem optymalizacji. Metoda zachłanna jest jedną ze strategii stosowanych w rozwiązywaniu problemów optymalizacyjnych.

waga kat timpf

Wady stosowania algorytmu Greedy

Algorytm zachłanny podejmuje decyzje na podstawie informacji dostępnych na każdym etapie, nie biorąc pod uwagę szerszego problemu. Może zatem istnieć możliwość, że rozwiązanie zachłanne nie zapewni najlepszego rozwiązania każdego problemu.

Na każdym etapie następuje wybór optymalnego lokalnego z zamiarem znalezienia optymalnego globalnego. Rozumiemy na przykładzie.

Rozważmy wykres podany poniżej:

Musimy podróżować od źródła do miejsca docelowego przy minimalnych kosztach. Ponieważ mamy trzy wykonalne rozwiązania ze ścieżkami kosztów 10, 20 i 5. 5 to ścieżka minimalnego kosztu, więc jest to rozwiązanie optymalne. Jest to maksimum lokalne i w ten sposób na każdym etapie znajdujemy maksimum lokalne, aby obliczyć rozwiązanie optymalne globalne.

śpij w javascript