1. úloha - problém batohu

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

Specifikace úlohy

Je dáno:

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

Řešení

Řešení hrubou silou

Algoritmus, řešící problém hrubou silou, postupně generuje všechny možné kombinace věcí umisťovaných do batohu - batoh je reprezentován jako proměnná a je postupně inkrementován - a testuje obě podmínky (zda zvolená kombinace nepřetíží batoh a zda cenová funkce nabývá maxima). Nejsou provedeny žádné dílčí optimalizace.

Řešení heuristikou

Algoritmus, řešící problém pomocí heuristiky, pracuje podobně jak člověk, kdyby měl batoh zaplnit. Algoritmus vybírá věci vkládané do batohu podle kritéria cena/hmotnost. Nejprve setřídí všechny věci podle tohoto poměru a následně postupně přidává do batohu od nejlepší a testuje, zda je možné přidat další.

Rozbor složitosti algoritmů

Řešení hrubou silou

V popisu uvedeném výše zkouší program 2n kombinací. Pokud považujeme složitost zkoušení jedné instance za lineární (pro každou kombinaci program počítá hmotnost a cenu řešení skalárním součinem n-složkových vektorů), pak je asymptotická složitost O(n*2n).

Řešení heuristikou

Program řešící problém algoritmem s heuristikou řadí pole triviální metodou hledání největšího. Jeho časová složitost je asymptoticky O(n2). Pak zkouší vložit jednotlivé věci do batohu po jedné a testuje plnost batohu, tato operace má asymptotickou složitost O(n), celková asymptotická složitost (nejvyšší řád) je tedy O(n2). Heuristika pro všechny velikosti instance běžela neměřitelně krátkou dobu. Chyba heuristiky je značná, to je dáno tím, že se zastaví okamžitě, jakmile nelze vložit další věc, chybu lze výrazně snížit, toto je diskutováno v závěru.

*Pro instanci o rozsahu 32 došlo k chybě při běhu heuristiky.
**U obou grafů je pro instance 4 - 25 brán průměr ze všech 50 měření.

Program

Závěr

Asymptotická časová složitost algoritmu řešící problém batohu hrubou silou je O(n*2n). Ač je naprogramován relativně svižně v čistém C tak pro instance s n>25 je doba běhu na počítači s PIII Celeron 1,43GHz v minutách.

Proto můžeme využít pro řešení problému algoritmus s využitím heuristiky. Složitost se radikálně sníží, avšak cenou je nalezení sub-optimálního řešení. Zde je chyba heuristiky poměrně značná, avšak poměrně triviálními úpravami (testování na vložení nejdražší vložitelné věci, snaha o naplnění nevyužitého prostoru jakýmikoliv věcmi) by bylo možné chybu algoritmu výrazně snížit.