Rešení problému batohu 2

1. Úkol

2. Rešení

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.

2.1 Větve a hranice

Metoda je rekurzivní. Prochází kombinace umístění věcí do batohu s podmínkou nepřetížení batohu tak, že si v každém koncovém stavu (další předmět by batoh přetížil) srovná cenu aktuálního řešení s řešením dosud nejlepším (to je ta hranice specifikovaná v názvu). Využívá však přitom ještě jednu vlastnost, neprochází takové stavy, ve kterých už libovolnou kombinací zbývajících předmětů nemůže být zlepšena cena batohu - zde se jedná o ořezávání neperspektivních větví. Teoreticky je složitost stejná jako u metody hrubá síla (asymptoticky O(2^n)), prakticky však bude výrazně nižší.

2.2 Dynamicky podle kapacity batohu

Spočteme maximální cenu naplněného batohu se zachováním jeho nosnosti. Na začátku budeme pracovat s nenaplněným batohem. Zeptáme se, jaká je cena batohu s nějakým vloženým předmětem a bez něho a vybereme si lepší variantu, a tím převedeme náš úkol na určení ceny batohu s počtem přemětů o jedna menším. Postupnou rekurzí dojdeme k řešení triviálních problémů - kapacita batohu je vyčerpána. Až potud by měl algoritmus složitost opět 2 na n. Pokud si budeme stavy s opakovaným řešením pamatovat (tyto stavy mají vždy stejné řešení, at je postup k nim jakýkoliv), zlepšíme složitost na n * (maximální hmotnost batohu). Pamět realizujeme dvojrozměrným polem s délkou N a výškou odpovídající nostnosti batohu. Nakonec z tohoto pole zrekonstruujeme obsah batohu.

2.3 Heuristika podle poměru cena/hmotnost s testem nejcennější věci

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. Až potud se jedná o stejnou heuristiku jako v první úloze. Test nejcennější věci spočívá v porovnání takto zabaleného batohu s předmětem s nejvyšší cenou, který se do batohu vejde. Vítěz srovnání je přidán do batohu. Rešení není optimální, složitost je závislá na metodě použitého řazení.

3. Srovnání

n Průměrný počet prohledávaných instancí
Větve a hranice Dynamicky podle kapacity batohu Heuristika podle poměru cena/hmotnost s testem nejcennější věci
4 11 22 3
10 181 623 7
15 361 2655 14
20 6822 5519 15
22 26562 6486 18
25 74718 9065 18
27 95417 11617 22
30 451564 15108 23
32 755698 18251 24
35 2035668 22598 26
37 2286086 26373 28
40 25525695 31241 30

Tabuka 1. Průměrný počet prohledávaných instancí

4. Závěr

Dodatek

Kompeltní balíček s programem pro řešení úlohy, programem pro analýzu, výsledky testů a soubory pro make.
Zdrojový kód programu pro usnadnění prohlížení.
Spustitelný soubor programu pro Linux.