Algorytmy i struktury danych - Algorytmy zachłanne

1. Algorytmy zachłanne to takie, które w każdym kroku podejmują taką decyzję, która w danej chwili wydaje się być najkorzystniejsza (np. wydawanie reszty. Mamy do dyspozycji 5zł, 2 zł i 1 gr. Chcemy wydać 6 złotych. Algorytm zachłanny -> wydajemy 3 razy po 2 zł, a nie 5 złotych i 100 jednogroszówek).

2. Film:

3. Wyróżniamy:

• algorytmy dokładne - algorytmy te dają gwarancję znalezienia rozwiązania optymalnego
• algorytmy niedokładne - algorytmy te nie dają gwarancję znalezienia rozwiązania optymalnego

4. Własności algorytmu zachłannego, który zawsze ma zwracać rozwiązanie optymalne:

• Własność optymalnej podstruktury (znając optymalne rozwiązania podproblemów można efektywnie wyznaczyć rozwiązanie głównego problemu)
• Własność wyboru zachłannego (wystarczy rozwiązać tylko ten podproblem, który można ocenić jako najbardziej obiecujący)