Godusis algoritmas

Optimizavimo algoritmas vadinamas godžiuoju, jei kiekviename žingsnyje, kuriame jis tik turi pasirinkimą, renkasi tuo momentu (tame žingsnyje) geriausią variantą, neatsižvelgdamas į tai, koks rezultatas bus gautas visumoje. Geras pavyzdys – kuprinės uždavinys. Yra ribojimas, kokį svorį galima sudėti į kuprinę, ir duoti galimų nešulių svoriai. Reikia kuprinę sukrauti taip, kad nešamas svoris būtų kuo didesnis. Pvz., kuprinė talpina 20 kg. Yra trys nešuliai: 15 kg, 9 kg, 8 kg. Godusis algoritmas pradėtų kuprinę “krauti” nuo sunkiausiojo nešulio, ir apsiriktų. Beje, įrodoma, kad kuprinės uždavinys išsprendžiamas tik pilno perrinkimo būdu.

 


II lygis

Konkurso „Bebras“ uždavinys: Valčių krova


 

 

 

 

 

 

Uždavinių paaiškinimai

Valčių krova