MI-PAA - 1.úloha Problém batohu Tomáš Čejka 3. října 2011
1
Obsah 1 Specifikace úlohy
3
2 Rozbor možných variant řešení 2.1 Řešení hrubou silou . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Řešení s pomocí heuristiky založené na poměru cena/hmotnost
3 3 3
3 Rámcový popis postupu řešení
4
4 Popis kostry algoritmu - řešení s heuristikou
4
5 Naměřené výsledky
5
6 Závěr
9
2
1
Specifikace úlohy
Úkolem této úlohy byla implementace programu pro řešení problému batohu, definovaného na stránce: https://edux.fit.cvut.cz/courses/MI-PAA/homeworks/knapsack/def Je -
dáno celé číslo n (počet věcí) celé číslo M (kapacita batohu) konečná množina V={v1, v2, ... ,vn } (hmotnosti věcí) konečná množina C={c1, c2, ... ,cn } (ceny věcí)
Nejznámější varianta je optimalizační. Pokud se mluví o „problému batohu“ bez bližšího určení, většinou se rozumí tato verze. Zkonstruujte množinu X={x1, x2, ... ,xn }, kde každé xi je 0 nebo 1, tak, aby - platilo v1x1+v2x2 + ... + vnxn <= M (batoh nebyl přetížen). - a výraz c1x1+c2x2 + ... + cnxn nabýval maximální hodnoty pro všechny takové množiny (cena věcí v batohu byla maximální).
2 2.1
Rozbor možných variant řešení Řešení hrubou silou
Řešení hrubou silou představuje prohledání celého stavového prostoru instance problému a nalezení nejlepší konfigurace.
2.2
Řešení s pomocí heuristiky založené na poměru cena/hmotnost
Algoritmus nezaručuje nalezení optimálního řešení, ale jeho časová složitost je řádově mnohem menší než prohledávání celého stavového prostoru.
3
3
Rámcový popis postupu řešení
Řešení hrubou silou se provádí pomocí průchodu do hloubky stavového prostoru a průběžné ukládání nejlepšího dosud nalezeného řešení - tedy konfigurace. Řešení pomocí heuristiky ohodnotí každou věc z množiny věcí poměrem cena/hmotnost. Na základě těchto hodnot se postupně do batohu vkládají věci tak dlouho, dokud není dosažena maximální možná celková hmotnost.
4
Popis kostry algoritmu - řešení s heuristikou
Celý algoritmus se opírá o prioritní frontu, do které se na začátku výpočtu přidají všechny věci podle vypočteného poměru cena/hmotnost. Počátečním stavem problému je prázdný batoh. Postupným průchodem prioritní fronty se algoritmus pokouší přidat věc do batohu a zkoumá, jestli již není překročena celková maximální hmotnost věcí v batohu. Jakmile již nejde hmotnost zvýšit, algoritmus končí.
4
5
Naměřené výsledky
Měření probíhalo na notebooku s procesorem Intel(R) Core(TM)2 T7200 @ 2.00GHz, program byl napsán v jazyce Java s využitím knihovny jCOP a spouštěn v JDK 1.6.0_18. Relativní chyby z výsledků z 50-ti různých zadaných instancí pro každné n byly zprůměrovány a zaneseny do tabulky. n Průměrná relativní chyba Maximální relativní chyba 4 0,0007975 0,0235690 10 0,0102235 0,0929791 15 0,0038152 0,0854271 20 0,0042266 0,0843373 22 0,0056846 0,0722892 25 0,0042232 0,0367893 27 0,0041692 0,1060172 30 0,0043113 0,0551378 32 0,0030387 0,0334076 35 0,0026043 0,0460922 37 0,0030181 0,0819672 40 0,0019034 0,0233723 Tabulka 1: Relativní chyba výpočtu
Výsledky průměrných relativních chyb jsou rovněž uvedeny v podobě grafu, obsahující průměrné a maximální relativní chyby pro jednotlivé hodnoty n.
5
Obrázek 1: Průměrná a maximální relativní chyba
Pomocí knihovny jCOP byl měřen čas výpočtu jednotlivých instancí. Následující tabulka obsahuje průměrné časy CPU pro řešení hrubou silou a algoritmu s heuristikou. Výpočet pro n > 22 již nebylo z časových důvodů možné pro řešení hrubou silou naměřit, protože celkový čas výpočtu všech 50-ti již přesahoval 4 hodiny běhu programu.
6
n Heuristic [ms] Brute force [ms] 4 2,8 3,7 10 6,1 36,2 15 9,06 1142,4 20 11,48 58687,2 22 12,78 283621,6 25 14,66 27 16,4 30 19 32 19,6 35 21,8 37 24,6 40 28,6 Tabulka 2: Čas výpočtu hrubou silou a algoritmem s heuristikou
Podle následujícího grafu s porovnáním časů výpočtů obou algoritmů vidíme, že pro velké n je čas výpočtu algoritmu s heuristikou zanedbatelný vzhledem k času výpočtu hrubou silou.
Obrázek 2: Průměrný čas výpočtu řešení hrubou silou a s heuristikou
Složitost výpočtu řešení hrubou silou je O(n!), protože se prohledává celý 7
stavový prostor (hledáme všechny kombinace věcí v batohu).
Obrázek 3: Závislost času na velikosti instance (hrubá síla)
Složitost výpočtu algoritmu s heuristikou odpovídá asymptoticky lineární složitosti, protože s použitím vhodné prioritní fronty můžeme počáteční řazení věcí podle poměru zanedbat.
8
Obrázek 4: Závislost času na velikosti instance (heuristika)
6
Závěr
Bohužel použitím algoritmu s heuristikou není možné optimální řešení nalézt vždy. Problém způsobují takové instance problému, kde optimální řešení neobsahuje některou z věcí s vysokým poměrem cena/hmotnost. Výhodou algoritmu s heuristikou je rychlost nalezení výsledku pro velká n, který má zanedbatelnou průměrnou relativní chybu. Na základě měření jsem zjistil, že relativní chyba se při použití algoritmu s heuristikou zmenšuje, a přitom čas výpočtu roste jen nepatrně. Pro velké instance problému je tedy efektivní použít algoritmus s heuristikou přes ztrátu přesnosti.
9
