Algoritmus prochází všechny možné kombinace předmětů v batohu kromě těch, které by způsobily jeho přetížení. Prochází tak tedy téměř celý stavový prostor úlohy. Moje varianta tohoto algoritmu obsahuje jednorozměrné pole, které o i-tém prvku říká, zda se ve výsledné množině nachází či ne, dále je zde celková, "již nakumulovaná" hmotnost předmětů a podobně i zatím dosažená cena. Je zde rekurzívní funkce, kde jejímu i-tému zanoření odpovídá zkoumání i-tého prvku. Funkce nejdřív i-tý prvek "zařadí do batohu" a zanoří se do další vrstvy rekurze a po návratu prvek z batohu "vyjme" a opět se zanoří, bez něj. Pokud už jsou takto zpracovány všechny prvky, máme o stavu batohu jasno a zjišťujeme, jestli toto dosažené řešení je dosud nejoptimálnější.
Vzhledem k tomz, že testujeme takřka všechny kombinace dvoustavových veličin, měla by časová náročnost tohoto algoritmu růst jako n2.
Heuristika podle poměru cena/váha spočívá v tom, že se předměty nejdříve seřadí podle klesajícího poměru cena/váha a potom se postupně do batohu přidávají postupně ty prvky, který mají tento poměr nejvýhodnější a ještě se do batohu vejdou. Pokud nějaký prvek má nejvýhodnější poměr, ale překročil by nosnost batohu, ignoruje se a pokračuje se dalším prvkem, který už tak výhodný poměr mít nemusí, ale zato se může do batohu stále "vejít".
Z grafu je jasně patrné, že časová náročnost algoritmu "hrubá síla" roste exponenciálně. Náročnost heuristického algoritmu záleží především na tom, s jakou časovou náročností dokážeme seřadit pole a procházet jím. Z grafu je vidět, že tato náročnost je oproti hrubé síle zanedbatelná.
Relativní chybu jsem počítal pro každou instanci problému vztahem chyba = (opt_cena - heur_cena) / opt_cena, kde opt_cena je skutečná optimální cena (v mém případě zjištěná metodou hrubé síly) a heur_cena je cena zjištěná heuristickým algoritmem. Průměrná chyba pro každé n je pouhý aritmetický průměr chyb všech instancí problému s daným počtem prvků a maximální chyba je nejvyšší z těchto chyb.
Z grafu je patrné, že čím vyšší je počet předmětů, tím spíše se pomocí heuristiky přiblížíme optimálnímu řešení.
Ukázalo se, že daná heuristika může být při malém počtu předmětů zdrojem velkých chyb a je tedy lepší použít metodu hrubé síly. Pro vyšší počet předmětů odchylka od optima klesá a pohybuje se mezi 1 a 2 procenty. I to však může být v některých případech nežádoucí. To by se dalo vyřešit buď nalezením nějaké výhodnější heuristiky nebo jiným přístupem k problému, například dynamickým programováním.
Pomocné funkce pro čtení, zápis a zpracování výsledků
global.c
Funkce pro řešení pomocí hrubé síly a heuristiky cena/váha a měření chyby
uloha1.c