3. úloha - problém batohu II.

Tomáš Kubeš - kubest1
FEL-ČVUT PAA (Problémy a algoritmy) LS 2005

Zadání

• Naprogramujte řešení 0/1 problému batohu metodou větví a hranic tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria.
• Naprogramujte řešení 0/1 problému batohu nebo alespoň 0/1 exaktního problému batohu bez cen metodou dynamického programování.
• Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/hmotnost s testem nejcennější věci.

Specifikace úlohy

Je dáno:

• celé číslo n (počet věcí)
• celé číslo M (kapacita batohu)
• konečná množina V={v₁, v₂, ... ,v_n} (hmotnosti věcí)
• konečná množina C={c₁, c₂, ... ,c_n} (ceny věcí)

Zkonstruujte množinu X={x₁, x₂, ... ,x_n}, kde x_i je z {0,1}, tak aby platilo:

• v₁x₁+v₂x₂ + ... + v_nx_n <= M (batoh nebyl přetížen)
• výraz c₁x₁+c₂x₂ + ... + c_nx_n nabýval maximální hodnoty pro všechny takové množiny (cena věcí v batohu byla maximální).

Problém batohu lze slovně popsat jako úlohu, kdy máme předměty různých hodnot a hmotností zabalit do batohu tak, aby jeho hodnota byla co možná nejvyšší a nebyla překročena jeho nosnost.

Metody Řešení

Užití metody větví a hranic

Algoritmus je založen na řešení hrubou silou z první úlohy. Rozdíl je v tom, že některé větve nejsou prozkoumávány, rozvíjení skončí už když se dostane do situace, že rozvíjená větev nemůže být lepší než dosud dosažené řešení - tj. libovolnou kombinací zbývajících předmětů nemůže být zlepšena cena batohu. Jedná se o ořezávání neperspektivních větví = název metody. Očividně takto určená horní mez někdy značně nadhodnocuje možnosti rozvíjeného řešení. Teoreticky je v nejhorším případě složitost stejná jako u metody hrubá síla (asymptoticky O(2ⁿ)), prakticky však bývá výrazně nižší.

K implementaci tohoto řešení bylo nutné původní program na hledání řešení hrubou silou výrazně pozměnit, protože zde je mnohem příhodnější užít rekurzi (původní řešení pouze čítalo 64bit proměnnou ve for cyklu).

Užití dynamického programování

Jádrem tohoto řešení je rozložení problému na dva menší problémy. Rekurzivním opakováním tohoto postupu dospějeme až k triviálním úlohám, které lze řešit v konstantním čase. Až potud by měl algoritmus opět složitost O(2ⁿ). Výhoda dynamického programování spočívá v tom, že si pamatujeme to, co jsme již počítali a nepočítáme to znovu. Využíváme k tomu fakt, že pro prvních k věcí a danou nosnost je nejlepší řešení vždy stejné, nezávisle na cestě, která k němu vedla. Využijeme triviální dvourozměrné pole obsahující nejlepší možné řešení pro prvých k věcí a nosnost batohu w.

Pro dělení úlohy využijeme faktu, že je-li řešení problému s k věcmi a nosností N optimální a obsahuje k-tou věc, pak optimální řešení problému s prvními k-1 věcmi a nosností (N - váha k) je toto řešení bez k-té věci. Podíváme li se na fakt z druhé strany, tak zjistíme, že abychom stanovili optimální řešení pro n věcí, musíme znát:

• optimální řešení problému s vyjmutou n-tou věcí (v případě, že n-tá věc v optimálním řešení není), a
• optimální řešení problému s vyjmutou n-tou věcí a kapacitou batohu sníženou o hmotnost té věci (v případě, že n-tá věc je součástí optimálního řešení).

Užití heuristiky podle poměru cena/hmotnost s testem nejcennější věci

Jedná o stejnou heuristiku jako v první úloze. Po seřazení podle klesajícího poměru cena/váha jsou předměty postupně vkládány do batohu podle pořadí v posloupnosti. Navíc se na závěr porovná tento batoh s batohem s jedním předmětem s nejvyšší cenou, který se do batohu vejde. Vítězný batoh je použit. Nalezené řešení není optimální, jeho chyba je maximálně 50%. Složitost je závislá na metodě použitého řazení, při uvážení celočíselných vah lze aplikovat counting sort a složitost této metody bude asymptoticky O(n), tj. úžasná.

Programy

• Balíček zdrojových kódů

Výsledky

Cena řešení

Výsledky pro instance nabízené při zadání úlohy. Průměry vždy pro 50 instancí s daným rozsahem.

Počet kroků

Výsledky pro instance nabízené při zadání úlohy. Průměry vždy pro 50 instancí s daným rozsahem.

Závěr

Metoda heuristiky poměr cena/hmotnost doplněná o test nejcennější věci má teoreticky prokázanou úspěšnost v nejhorším případě pouze 50% (tzn. je zaručeno, že dosáhne přinejmenším poloviny ceny optima). V drtivé většině případů se zde rozdíl drží pod 1% a nikdy nepřekročí 2%. Důvod je jednoduchý - cena řešení je obvykle mezi 1000-3500. Cena jedné věci je okolo dvou set. Výhodné by to mohlo být, kdyby měly ceny a hmotnosti věcí větší rozptyl a mnoho různých kombinací by se do batohu nevešlo. Potom by heuristika zřejmě vykazovala podstatně horší výsledky.

Z hlediska počtu kroků je nejúspěšnější heuristika. Velmi úspěšně si v našich úlohách počíná dynamické programování, které dává optimální výsledky s relativně velmi nízkou náročností. Metoda větví a hranic je zde o několik řádů horší, to je zřejmě dáno typem užitých úloh.

Přestože naměřené výsledky mají jistou vypovídací hodnotu, nelze je zobecňovat, je zde problém s poměrně jednotvárně zdanými úlohami.