Šajā apmācībā jūs uzzināsiet, kas ir mantkārīgs algoritms. Jūs atradīsit arī mantkārīgas pieejas piemēru.
Alkatīgs algoritms ir pieeja problēmas risināšanai, izvēloties labāko šobrīd pieejamo opciju, neuztraucoties par tā nākotnes rezultātu. Citiem vārdiem sakot, vietējā labākā izvēle ir vērsta uz vislabāko rezultātu sasniegšanu pasaulē.
Šis algoritms var nebūt labākais risinājums visām problēmām. Dažos gadījumos tas var radīt nepareizus rezultātus.
Šis algoritms nekad neatgriežas, lai mainītu pieņemto lēmumu. Šis algoritms darbojas no augšas uz leju pieeja.
Šī algoritma galvenā priekšrocība ir:
- Algoritmu ir vieglāk aprakstīt .
- Šis algoritms var darboties labāk nekā citi algoritmi (bet ne visos gadījumos).
Iespējamais risinājums
Īstenojams risinājums ir optimāls problēmas risinājums.
Alkatīgs algoritms
- Vispirms risinājumu kopa (kas satur atbildes) ir tukša.
- Katrā solī risinājumu komplektā tiek pievienots vienums.
- Ja risinājumu kopa ir iespējama, pašreizējais vienums tiek saglabāts.
- Cits elements tiek noraidīts un nekad vairs netiek izskatīts.
Piemērs - mantkārīga pieeja
Problēma: jums ir jāmaina summa, izmantojot pēc iespējas mazāku monētu skaitu. Daudzums: $ 28 Pieejamās monētas: $ 5 monēta $ 2 monēta $ 1 monēta
Risinājums:
- Izveidojiet tukšu risinājumu kopu = ().
- monētas = (5, 2, 1)
- summa = 0
- Kamēr summa ≠ 28, rīkojieties šādi.
- No monētām izvēlieties monētu C, kuras summa + C <28.
- Ja C + summa> 28, neatgrieziet risinājumu.
- Cita summa = summa + C.
- Pievienojiet C šķīduma kopai.
Līdz pirmajām 5 atkārtojumiem risinājumu komplektā ir 5 monētas 5 USD. Pēc tam mēs iegūstam 1 $ 2 monētu un, visbeidzot, 1 $ 1 monētu.
Alkatīgu algoritmu lietojumi
- Atlasīšana Kārtot
- Muguras problēma
- Minimālais aptverošais koks
- Viena avota īsākā ceļa problēma
- Darba plānošanas problēma
- Prima minimālais aptverošā koka algoritms
- Kruskaļa minimālais aptverošā koka algoritms
- Dižkstra minimālais aptverošā koka algoritms
- Huffman kodēšana
- Ford-Fulkersona algoritms
