Úloha č. 1 - problém batohu

Zadání úlohy

Naprogramujte řešení 0/1 problému batohu hrubou silou. Na zkušebních datech pozorujte závislost výpočetního času na n.
Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/váha. Pozorujte:
  • závislost výpočetního času na n
  • průměrné zhoršení proti exaktní metodě
  • maximální chybu

Specifikace

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í)
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).
  • výraz c1x1+c2x2 + ... + cnxn nabýval maximální hodnoty pro všechny takové množiny (cena věcí v batohu byla maximální).

Rozbor řešení

Řešení hrubou silou

Řešení hrubou silou využívá zkoušení všech kombinací. Z toho důvodu nalezne jak nejlepší řešení, tak ale i s nejhorší asymptotickou složitost - exponenciální (2^počet_prvků).

Řešení heuristikou

Algoritmus s heuristikou mají mnohem vhodnější složitost, ale obecně není zaručeno, že nalezené řešení je optimální, ale tzv. supoptimální. Heuristiku představuje fukce, která se snaží nějakým způsobem ohodnotit možnou změnu, resp. prvek a podle toho vybírá.
V tomto případě jde především o ohodnocení podle cena/hmotnost. Prvky se vkládají do batohu od největšího ohodnocení k nejnižímu, resp. obráceně.
Prvky, které se do batohu již nevejdou jsou přeskočeny.
V rámci aplikace jsou naimplementovány celkem tři různé heuristiky:
  • podle klesající ceny
  • podle rostoucí hmotnosti
  • podle hlesajícího poměru cena/hmotnost
Veškerá měření i řešení uživetelem zadaného příkladu je možné dle volby vyřešit všemi zmíněnými heuristikami.

Popis algoritmu

Algoritmus řešení hrubou silou

Pro generování instancí je použito pole booleanů, které postupně, obdobně jako čítač, mění jednotlivé hodnoty od false,...,false po true,...,true. Čítání probíhá v opačném pořadí než u čítače z důledu lehčí implementace.
Celé prohledávání představuje cyklus o dvou funkcích: inkrementace a kontrola. Kontrola zahrnuje jak test, zda nalezená instance má vyšší cenu a zdali je možná. V Případě nalezení lepší instance se uloží a pokračuje se dokud nebudou prozkoušeny všechny kombinace.
Algoritmus procházení byl dále vylepšen ořezáním, tj. pokud vím, že současná testovaná kombinace neodpovídá nezvyšuji čítač o 1, ale o hodnotu nejnižšího nastaveného bitu...

Algoritmus řešení heurestikou

Na začátku se jednotlivé prvky zabalí do objektů a vyhodnotí poměr cena/hmotnost, v rámci kolekce seřadí a poté prochází od nejvyššího po nejnižší. Pokud se právě zkoumavý prvek vejde do batohu, je tam vložen v opačném případě cyklus pokračuje dál, dokud neprojde celou kolekci.

Naměřené výsledky

Časová složitost

Relativní chyba heuristiky

Cena/počet prvků a absolutní chyba heuristiky

Program

Program je napsán v jazyce Java. Program zahrnuje jak GUI pro řešení zadané úlohy, tak i měření včetně grafů:
Pro spuštění bude možná nutné změnit cestu k interpretu v souboru run.bat
stáhnout

Naměřená data

Naměřená data byla vložena do MS Excel, kde vznikly grafy (viz. nahoře).
download

Závěr

Z výsledků je zřejmě patrné, že brutální síla pracuje se exponenciální složitostí což je neakceptovatelné.
Na druhou starnu heuristika cena/hmotnost nedává příliž dobré výsledky. Při průměrných hodnotách se zdá relaitvní chyba akceptovatelná, ale při hledání maximálních chyb se hodnota šplhá prudce vzhůru a výsledné instance jsou tedy vysoce mimo očekávání.

Poznámky

Program byl napsán v jazyce Javě a JBuilder a testována na Intel Centrino (1,83 GHz).