Šioje pamokoje sužinosite, kas yra godus algoritmas. Taip pat rasite godaus požiūrio pavyzdį.
Gobšus algoritmas yra būdas išspręsti problemą, parenkant geriausią šiuo metu galimą variantą, nesijaudinant dėl būsimo jo atnešto rezultato. Kitaip tariant, geriausiais pasirinkimais vietoje siekiama geriausių rezultatų visame pasaulyje.
Šis algoritmas gali būti ne pats geriausias pasirinkimas visoms problemoms spręsti. Kai kuriais atvejais tai gali sukelti neteisingus rezultatus.
Šis algoritmas niekada nebegali pakeisti priimto sprendimo. Šis algoritmas veikia „iš viršaus į apačią“ požiūriu.
Pagrindinis šio algoritmo privalumas yra:
- Algoritmą lengviau apibūdinti .
- Šis algoritmas gali veikti geriau nei kiti algoritmai (bet ne visais atvejais).
Galimas sprendimas
Galimas sprendimas yra optimalus problemos sprendimas.
Gobšus algoritmas
- Pirmiausia, sprendinių rinkinys (kuriame yra atsakymai) yra tuščias.
- Kiekviename žingsnyje elementas pridedamas prie sprendimo rinkinio.
- Jei sprendimo rinkinys yra įmanomas, dabartinis elementas paliekamas.
- Kita vertus, daiktas atmetamas ir daugiau niekada nebesvarstomas.
Pavyzdys - godus požiūris
Problema: Jūs turite pakeisti sumą naudodami kuo mažesnį monetų skaičių. Kiekis: 28 USD Galimos monetos: 5 USD moneta 2 USD moneta 1 USD moneta
Sprendimas:
- Sukurkite tuščią sprendinių rinkinį = ().
- monetos = (5, 2, 1)
- suma = 0
- Nors suma ≠ 28, atlikite šiuos veiksmus.
- Iš monetų pasirinkite monetą C, kurios suma + C <28.
- Jei C + suma> 28, negrąžinkite jokio sprendimo.
- Kitu atveju, suma = suma + C.
- Į tirpalų rinkinį įpilkite C.
Iki pirmųjų 5 kartojimų tirpalų rinkinyje yra 5 USD 5 monetos. Po to gausime 1 USD 2 monetą ir galiausiai 1 USD 1 monetą.
Gobšių algoritmų taikymai
- Pasirinkimas Rūšiuoti
- Kuprinės problema
- Minimalus apimantis medis
- Vieno šaltinio trumpiausio kelio problema
- Darbo planavimo problema
- „Prim“ minimalus apimantis medžių algoritmas
- Minimalus Kruskalio apimančių medžių algoritmas
- Dijkstros minimalus apimantis medžių algoritmas
- „Huffman Coding“
- „Ford-Fulkerson“ algoritmas
