1. úloha - problém batohu

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

Specifikace úlohy

Je dáno:

• celé číslo n (počet věcí)
• celé číslo M (kapacita batohu)
• konečná množina V={v₁, v₂, ... ,v_n} (hmotnosti věcí)
• konečná množina C={c₁, c₂, ... ,c_n} (ceny věcí)

Zkonstruujte množinu X={x₁, x₂, ... ,x_n}, kde x_i je z {0,1}, tak aby platilo:

• v₁x₁+v₂x₂ + ... + v_nx_n <= M (batoh nebyl přetížen)
• výraz c₁x₁+c₂x₂ + ... + c_nx_n nabýval maximální hodnoty pro všechny takové množiny (cena věcí v batohu byla maximální).

Ř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 2ⁿ 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*2ⁿ).

Ř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(n²). 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(n²). 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

• Program napsaný v C
• Přeložený program pro Win32
  Užití: batoh.exe vstupni_soubor vystupni_soubor
• Arch výsledků programu
• Výsledky zpracované v Excelu

Závěr

Asymptotická časová složitost algoritmu řešící problém batohu hrubou silou je O(n*2ⁿ). 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.