3. úloha - problém batohu II.

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

Zadání

Specifikace úlohy

Je dáno:

Zkonstruujte množinu X={x1, x2, ... ,xn}, kde xi je z {0,1}, tak aby platilo:

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(2n)), 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(2n). 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:

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

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.

věcí dynamické programování metoda větví a hranic heuristika hrubá síla (optimální)
4 352 352 347 352
10 1125 1125 1110 1125
15 1814 1814 1808 1814
20 2335 2335 2321 2335
22 2501 2501 2488 2501
25 2954 2954 2941 2954
27 3143 3143 3122 3143
30 3581 3581 3563 3581
32 3694 3694 3678 3694
35 4081 4081 4067 4081
37 4222 4222 4205 4222
40 4628 4628 4612 4628

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.

věcí dynamické programování metoda větví a hranic heuristika hrubá síla (optimální)
4 16 12 4 16
10 1000 146 10 1024
15 3000 178 15 32768
20 5000 3491 20 1048576
22 5500 12755 22 4194304
25 7500 33225 25 33554432
27 9450 38631 27 134217728
30 12000 184291 30 1073741824
32 14400 263077 32 4294967296
35 17500 677279 35 34359738368
37 20350 721623 37 137438953472
40 24000 8576258 40 1099511627776

 

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.