Úloha 3: Problém batohu
Jan Dohnal (dohnaj1@fel.cvut.cz)
Naprogramujte řešení 0/1 problému batohu metodou větví a hranic tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria.
Naprogramujte řešení 0/1 problému batohu nebo 0/1 exaktního problému batohu bez cen metodou dynamického programování.
Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/hmotnost s testem nejcennější věci.
Jedná se o rekurzivní metodu, která je založena na procházení kombinací umístění věcí do batohu tak, že batoh nesmí být přetížen. V každém koncovém stavu dojde ke srovnání ceny aktuálního řešení s dosud nejlepším řešením (hranice). Neprocházejí se stavy, ve kterých už není možné zlepšit cenu batohu (ořezávání). Metoda by měla poskytovat výrazně nižší složitost než hrubá síla.
V této metodě se vypočítá maximální cena naplněného batohu. Začíná se s prázdným batohem. V každém kroku se ptáme, jaká je cena batohu s vloženým předmětem a bez něho, poté vybereme tu lepší variantu. Dále postupujeme rekurzivně až k nejmenším problémům triviálního charakteru. Hlavní myšlenkou této metody je to, že si budeme pamatovat stavy, které jsme navštívili. Tyto stavy budeme ukládat do pole o rozměrech N krát M.
Nejdříve seřadíme předměty podle poměru cena/váha a to v klesajícím pořadí. Provádíme test nejcennější věci: porovnáváme batoh s předmětem s nejvyšší cenou, který ještě můžeme do batohu vložit. Tuto věc pak do batohu přidáme. Složitost závisí na použitím řazení.
| n | průměrný počet prohledávaných instancí | ||
| větve a hranice | dynamicky | test nejcennější věci | |
| 4 | 11 | 22 | 3 |
| 10 | 181 | 623 | 7 |
| 15 | 361 | 2655 | 14 |
| 20 | 6822 | 5519 | 15 |
| 22 | 26562 | 6486 | 18 |
| 25 | 74718 | 9065 | 18 |
| 27 | 95417 | 11617 | 22 |
| 30 | 451564 | 15108 | 23 |
| 32 | 755698 | 18251 | 24 |
| 35 | 2035668 | 22598 | 26 |
| 37 | 2286086 | 26373 | 28 |
| 40 | 25525695 | 31241 | 30 |
Z naměřených výsledků vyplývá, že metoda větví a hranic dává solidní výsledky v porovnání s hrubou silou, je však závislá na struktuře konkrétní instance, kdy se může čas řešení prodloužit.
Metoda dynamického programování umožňuje velmi rychle najít řešení. Nevýhodou je vyšší paměťová náročnost, je však použitelná jen pro některé problémy.
Při zvolení vhodného algoritmu řazení dává třetí metoda s použitím heuristiky dobré výsledky.
Ke stažení je k dispozici zabalená celá úloha, nebo jen zdrojový kód vytvořený v programovacím jazyku C: