3. domácí úloha z předmětu PAA

Řešení problému batohu metodou větví a hranic, dynamickým programováním a heuristikou podle poměru cena/váha s testem nejdražší věci

Oto Válek

Problém batohu je řešen metodou větví a hranic, dynamickým programovním a heuristikou podle poměru cena/váha s testem nejdražší věci. Byly použity připravené instance problému pro n = 4, 10, 15, 22, 25, 27, 30, 32, 35, 37, 40. Do srovnání byly zahrnuty i výsledky algoritmů hrubé síly a jednoduché heuristiky cena/váha z 1.úlohy.

Čítač kroků řešení byl zvyšován na vhodném místě v hlavní rekurzivní funkci algoritmu. U heuristik vybírajících nejvyšší poměr cena/váha byl navíc umístěn do cyklu příslušné funkce, aby se projevila O(n) složitost pro každý navštívený stav. U metody hrubé síly, dyn. programování a metody větví a hranic však počet kroků zhruba odpovídá počtu navštívených stavů stavového prostoru.

Čas byl měřen funkcí ftime() ze std. C knihovny v prostředí WinNT. Byl použit kompilátor z MS VC 5.0 s defaultním nastavením a procesor Intel Pentium 100 Mhz.

Metoda větví a hranic je rozšířením řešení hrubou silou. Kromě podmínky testující přetížení batohu je sestup stromem stavového prostoru omezen podle ceny (tedy optimalizačního kritéria).

Rekurzívní procedura Dalsi(vec, potencionalni_cena) je rozšířena o parametr potencionalni_cena, max. cenu, které je ještě možno v této větvi dosáhnout. Na počátku je roven součtu cen všech věcí, jakmile se nějaká věc do batohu NEPŘIDÁ, je snížen o její cenu. Pokud tento parametr klesne pod dosud nejvyšší nalezenou celkovou cenu, v dalším sestupu se nepokračuje.

Dynamické programování skládá řešení z výsledků menších podúloh. Zde je touto úlohou funkce MaxCena(vec,limit), vracející nejlepší řešení úlohy omezené na věci s indexem 0..vec (tedy prvních vec+1 věcí) a váhový limit limit.

Funkce MaxCena(vec,limit) zkusí věc vec do batohu nepřidat (voláním MaxCena(vec-1,limit)) i přidat (voláním MaxCena(vec-1,limit-instance.Vaha(vec)) a Pridej(vec), pokud se do batohu ještě vejde). Z obou konfigurací vybere a vrátí tu s vyšší cenou.

Tento postup by měl však složitost metody hrubé síly, hlavní úspory se dosáhne zavedením dvourozměrného pole cache, do kterého se ukládají již vypočítané výsledky funkce. Pole má rozměry n·M, kde n je počet věcí a M je hmotnostní limit batohu. V každém prvku navíc může být uložena konfigurace o velikosti n, takže paměťová složitost je O(n²·M).

Je jednoduchým rozšířením heuristiky. Přidá O(n) test řešení skládající se z jedné nejdražší věci. Tato úprava zaručí alespoň 50% ceny optimálního řešení.

Uvedeny jsou průměrné hodnoty z 50 instancí pro každé n. U metody hrubé síly byl test ukončen u n=22.

Metoda větví a hranic, ač přidává ke hrubé síle jen jednoduchou podmínku, dosahuje značného snížení počtu kroků, bez ztráty optimálnosti výsledku. Závislost počtu kroků na n je však poměrně nepravidelná a není zdaleka lineární. Značné rozdíly jsou i mezi jednotlivými instancemi stejné velikosti ( u n=40 způsobila velký výkyv instance 9557, u které byl nutno projít téměř 120 000 000 stavů ). Tato metoda navíc předpokládá, že dokážeme u daného problému během prohledávání stavového prostoru určovat, jaké maximální hodnoty optimalizačního kritéria lze ještě dosáhnout.

Metoda dynamického programování se ukázala pro řešení 0/1 problému batohu nejvýhodnější. S rostoucím n se počet kroků blíží lineární závislosti (podle naměřených výsledků) a výsledky jsou vždy optimální. Podmínkou využití je však to, že dokážeme rozumně ukládat výsledky vyřešených podproblémů, což tento problém splňuje. Možných kombinací parametrů rekurzivní funkce zde není příliš mnoho.

Přidání testu nejdražší věci má teoretický význam, protože zaručuje heuristice podle poměru cena/váha maximální chybu 50%. Zde však ke zlepšení došlo jen u 10% případů pro n=4. Mezi větším počtem věcí už tedy jedna nejdražší věc není významná. Průměrné zhoršení proti optimální ceně dosahovalo výrazně nižších hodnot než zmíněná zaručená přesnost 50% a navíc s rostoucím n klesalo.