Ebben az oktatóanyagban megtudhatja, mi az a Kapzsi algoritmus. Ezenkívül talál egy mohó megközelítés példáját.
A kapzsi algoritmus megközelítést jelent a probléma megoldásához azáltal, hogy kiválasztja a jelenleg elérhető legjobb lehetőséget, anélkül, hogy aggódna a jövőbeni eredmény miatt. Más szavakkal, a helyben legjobb választások célja a világszerte legjobb eredmények elérése.
Lehet, hogy ez az algoritmus nem a legjobb megoldás az összes probléma megoldására. Bizonyos esetekben rossz eredményeket hozhat.
Ez az algoritmus soha nem tér vissza a meghozott döntés megfordításához. Ez az algoritmus felülről lefelé irányuló megközelítésben működik.
Az algoritmus fő előnye:
- Az algoritmust könnyebb leírni .
- Ez az algoritmus jobban képes teljesíteni, mint más algoritmusok (de nem minden esetben).
Megvalósítható megoldás
Megvalósítható megoldás az, amely optimális megoldást kínál a problémára.
Kapzsi algoritmus
- Először is, a (válaszokat tartalmazó) megoldáskészlet üres.
- Minden lépésben egy elem kerül a megoldáskészletbe.
- Ha a megoldáskészlet megvalósítható, az aktuális elem megmarad.
- Egyébként az elemet elutasítják, és soha többé nem fontolják meg.
Példa - kapzsi megközelítés
Probléma: A lehető legkisebb számú érme felhasználásával kell módosítania egy összeget. Összeg: 28 dollár Rendelkezésre álló érmék: 5 dollár érme 2 dollár érme 1 dollár érme
Megoldás:
- Hozzon létre egy üres megoldáskészletet = ().
- érmék = (5, 2, 1)
- összeg = 0
- Miközben összege ≠ 28, tegye a következőket.
- Válasszon egy C érmét olyan érmékből, amelyek összege + C <28.
- Ha C + összeg> 28, akkor ne adjon megoldást.
- Egyébként összeg = összeg + C.
- Adjunk C-t az oldathoz.
Az első 5 iterációig a megoldáskészlet 5 $ 5 érmét tartalmaz. Ezt követően 1 $ 2 érmét kapunk, végül 1 $ 1 érmét.
Kapzsi algoritmus alkalmazások
- Válogatás rendezése
- Hátizsák probléma
- Minimális átfogó fa
- Egyforrású legrövidebb út probléma
- Munkaütemezési probléma
- Prim minimális átívelő fa algoritmusa
- Kruskal minimális átívelő fa algoritmusa
- Dijkstra minimális átívelő fa algoritmusa
- Huffman Coding
- Ford-Fulkerson algoritmus
