Rešení problému batohu

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 Hrubá síla

Metoda je založena na projití všech možností (mimo možností, kdy je batoh přetížen), jak do batohu předměty vložit a vybraní optimální sestavy předmětů. Všech kombinací pro jednu instanci problému (kombinace předmětů a jejich ceny spolu s nosností batohu) je 2^n, kde n je počet předmětů, které můžeme pobrat. Složitost je tedy O(2^n).

n čas [s]
4 0
10 0
15 0
20 0,5
22 1,5
25 12
27 54

Tabuka 1. Závislost výpočetního času na n (průměrné hodnoty pro 50 instancí)

Pro n od 30 do 40 jsme měření nedokončili, výpočet je příliš časově náročný. Potřebná doba roste exponenciálně s n.

2.2 Heuristika cena/váha

Heuristika je založena na setřídění předmětů podle klesajícího poměru cena/váha, do batohu se tak nejdříve vkládají cennosti s touto dobrou hodnotou poměru.

Metoda nevede k nejlepšímu řešení, ale vybraná kombinace přemětů se k ideální blíží. Nejdůležitější je úspora času, nejnáročnější operací je setřídění předmětů. Tabulku závislosti na n nebudeme uvádět, ve všech případech trval výpočet 0 sekund. Ukážeme raději porovnání mezi oběma způsoby řešení.

n relativní chyba [%]
4 2,174508
10 1,104380
15 0,305038
20 0,449143
22 0,542115
25 0,424777
27 0,289616

Tabuka 2. Rozdíl mezi hrubou silou a heuristikou (průměrné hodnoty pro 50 instancí)

3. Závěr

Použitím heuristiky jsme dosáhli významné úspory času a přitom jsem zachovali rozumnou hladinu správnosti řešení. Chyba se pohybuje od 0,3 do 2 procent. Maximální chyba mezi hmotnosté batohu při ideálním a suboptimílním řešením činila 121 jednotek. Metoda hrubé síly, i když dává ideální řešení, je vhodná pouze pro nízká n.

Dodatek

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