Page 3 - Informatyka na czasie. Podejście zachłanne w rozwiązywaniu problemów. Podręcznik klasa 3

4. Podejście zachłanne w rozwiązywaniu problemów

Jeśli potrafimy uzasadnić, że znalezione rozwiązanie problemu jest
najlepsze z możliwych, to nazywamy je rozwiązaniem optymalnym. Rozwiązanie optymalne
Inaczej możemy mówić tylko o rozwiązaniu przybliżonym. Rozwiązanie przybliżone

Ćwiczenie 1
Podaj przykład problemu optymalizacyjnego (inny niż opisane).

Podejście zachłanne w optymalizacji
W części drugiej podręcznika omawialiśmy już jeden problem optymali-
zacyjny: wyznaczanie największego wspólnego dzielnika (NWD) dwóch
liczb. Do rozwiązania problemu wykorzystaliśmy algorytm Euklidesa.
W algorytmie tym stosuje się metodę rozwiązywania problemów
zwaną podejściem zachłannym (ang. greedy approach). Polega ono Podejście zachłanne
na podejmowaniu szeregu decyzji optymalnych lokalnie, czyli najlepszych (metoda zachłanna)
(ze względu na przyjęte kryterium) na danym etapie rozwiązywania
problemu. Nie sprawdzamy przy tym, jaki wpływ mają takie decyzje
na znalezienie rozwiązania optymalnego globalnie, czyli najlepszego
rozwiązania całego problemu.
Istotę podejścia zachłannego dobrze widać na przykładzie
wycinanki Euklidesa przedstawionej na rysunku 4.1. Wycinanka Euklidesa,
podręcznik Informatyka
na czasie 2. Zakres
podstawowy, s. 156 

 Warto wiedzieć
Czasami algorytmy
zachłanne pozwalają
znaleźć tylko rozwiązania
przybliżone. Takie
algorytmy zazwyczaj są
dość szybkie i można je
wykorzystać jako punkt
Rys. 4.1. Kolejne etapy wycinanki Euklidesa wyjścia do szukania
lepszych rozwiązań.
Dla liczb całkowitych dodatnich a i b wyznaczenie NWD(a,b) jest
równoważne znalezieniu największego kwadratu, którym można by
wypełnić prostokąt o bokach długości a i b.
W każdym kolejnym kroku algorytmu odcinamy od danego prosto-  Dobra rada
kąta jak największy kwadrat (postępujemy zachłannie), a w rezultacie Nie używaj wyrażenia
otrzymujemy poszukiwany kwadrat. „najbardziej optymalny”,
Algorytm Euklidesa zawsze znajduje rozwiązanie optymalne. Na przy- gdyż jest ono
niepoprawne. Coś może
kład dla liczb 112 i 88 algorytm zwraca liczbę 8, która na pewno jest być najbardziej korzystne
największą liczbą dzielącą 112 i 88. albo po prostu optymalne.
W części drugiej podręcznika rozważaliśmy różne algorytmy, które
rozwiązują problem optymalizacyjny wyznaczenia NWD dwóch liczb,
ale tylko algorytm Euklidesa wykorzystuje do tego podejście zachłanne.

63