Řešení problému batohu

1. Úloha

    Výsledkem bude krátká zpráva s naměřenými charakteristikami, doprovázená zdrojovými texty. Měření nechť je orientační - doba chodu jednotlivých testů nemusí překračovat několik málo minut. Rozsáhlejší experimenty jsou náplní pozdějších úloh.

2. Řeš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.

Řešení hrubou silou

    Procházejí se všechny kombinace věcí v batohu. Kombinace jsou generované tak, aby se nepřidávali věci do batohu již přetíženého.

Heuristiky typu nejrychlejšího vzestupu (greedy)

    Věci jsou seřazeny podle klesajícího poměru cena/hmotnost a pakliže se do batohu vejdou, jsou postupně přidávány.

 

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,001
10 0,02
15 0,75
20 23,68
22 88,2
25 690
27 3033

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

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

2.2 Heuristika cena/hmotnost

    Heuristika je založena na setřídění předmětů podle klesajícího poměru cena/hmotnost, 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ředmětů se k ideální blíží. Nejdůležitější je úspora času, kde nejnáročnější operací je setřídění předmětů. Tabulku potřebného výpočetního času neuvádím, neboť ve všech případech trval výpočet méně než 1 sekundu. Ukážeme raději porovnání mezi oběma způsoby řešení.

n relativní chyba [%]
4 73,5
10 17,4
15 8,1
20 7,3
22 7,6
25 5,9
27 5,17

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

 

3. Závěr

    Použitím heuristiky jsem dosáhl významné úspory času ale pro malou složitost výpočtu ne zrovna optimálního řešení. Chyba se pohybuje až do 73,5 %.  Metoda hrubé síly sice dává ideální řešení, ale je vhodná pouze pro nízká n. Při řešení této úlohy jsem se inspiroval u již jednoho hotového řešení Ondřeje Stárka (http://stareko.webzdarma.cz/). Čerpal jsem zde však pouze syntaxi pro načtení dat ze souboru. Samotné algoritmy jsem naprogramoval sám a pro měření času jsem využil zdroje časopisu Progres ze článku "Přesné měření času ve Windows" (http://www.eternal.cz/article.php?nID=210).

4. GUI

    Program byl vytvořen v prostředí Borland builder C++, verze 6.0.


                 Obr.1:   Náhled na jednoduché uživatelské rozhraní

5. Dodatek

Zkompilovaný program
Tento web ke stažení včetně programu
Zdrojový kód programu (Projekt pro Borland Builder C++)