Úloha 3

Autor: Petr Chytil

Zadání

• Naprogramujte řešení 0/1 problému batohu metodou větví a hranic (B&B) tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria. Tj. použijte ořezávání shora (překročení kapacity batohu) i zdola (stávající řešení nemůže být lepší než nejlepší dosud nalezené)

• Naprogramujte řešení 0/1 problému batohu nebo alespoň 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.

Zpráva by měla obsahovat:

• Popis implementovaných metod

• Srovnání výpočetních časů hrubé síly, B&B a dynamického programování (grafy vítány)

• Srovnání vylepšené heuristiky s původní

• Zhodnocení naměřených výsledků

Popis řešení

Řešení metodou větví a hranic

Tato metoda používá brute force algoritmus, ale snaží se jej omezovat, abychom dosahovali lepších výsledků (bohužel při stejné asymptotické složitosti). První omezení jsem již v brute force algoritmu z úlohy 1 měl zakomponováno. Bylo jím omezení dané maximální vahou věcí v batohu. Stavy, jejichž konfigurace předmětů přesahovala kapacitu batohu jsme vůbec neřešili. V této metodě přidáváme omezení cenou. Původní rekurzivní funkci jsem přidal parametr, který určuje součet cen všech předmětů, které ještě v této větvi stavového prostoru můžeme přidat. Před přidáním dalšího předmětu zjišťuji, zda-li součet cen předmětů aktuálně obsažených v batohu se sumou cen všech nevložených předmětů přesahuje doposud nejlepší dosaženou celkovou cenu věcí v batohu. Pokud ano, tak jedeme dál a pokud ne, tak řežeme větev a dál v ní nepokračujeme, protože nám neumožní dosáhnout lepšího řešení než jsme už doteď našli.

Řešení pomocí dynamického programování

Aplikuji jednoprůchodovou verzi dynamického programování s dekompozicí dle ceny batohu. Pracuji s tabulkou, ve které řádky specifikují podúlohy, které mají nastavenu nosnost batohu od max do 0, kde max je nosnost batohu aktuálně řešeně instance. Sloupce zase určují předměty (0 až n). Jednotlivé buňky tabulky pak obsahují dvojici cena, váha. Začínám prvním sloupcem pro první předmět a řeším triviální podúlohu – pokud se tento předmět vejde do batohu (max. váha je specifikována řádkem), tak jej vložím, v opačném případě nevkládám nic. Pro další sloupce pokračuji jinak. Porovnávám vždy cenu buňky v předchozím sloupci na stejném řádku (stejná kapacita batohu) se součtem ceny aktuálního předmětu a ceny buňky v předchozím sloupci a řádku sníženém o váhu aktuálního předmětu. Z těchto dvou cen vybírám tu lepší. Po vyplnění celé tabulky nastupuje rekonstrukce konfigurace nejlepšího řešení. Začínám posledním předmětem v řádku pro max váhu. Porovnávám jej se sloupcem vlevo. Pokud jsou shodné, tak aktuální předmět v řešení není a pokračuji dalším předmětem na stejném řádku. V opačném případě předmět v řešení je a pokračuji na řádku, který dostanu odečtením hmotnosti předmětu předchozího od hmotnosti předchozí buňky. Takto dojdu až k prvnímu předmětu, u kterého pouze kontroluji, zda se vejde do batohu o kapacitě specifikované řádkem, na kterém se zrovna nacházíme.

Řešení heuristikou podle poměru cena/hmotnost s testem nejcennější věci

U tohoto řešení jsem použil hotovou jednoduchou heuristiku z první úlohy. Po jejím proběhnutí pouze zjistím, který předmět je nejcennější ze všech. Cenu tohoto předmětu porovnám s celkovou cenou všech věcí v batohu, na kterou prišla heuristika. Z těchto dvou cen vybírám tu vyšší a prohlašuji jí za na naše konečné řešení.

Zdrojový kód všech tří řešení

• Zdrojový kód řešení pomocí B&B v jazyce Java: BranchAndBounds.java

• Zdrojový kód řešení pomocí dynamického programování v jazyce Java: DynProg.java

• Zdrojový kód řešení pomocí jednoduché heuristiky s testem nejcennější věci v jazyce Java: SimpleHeuristicMax.java

Změřená závislost výpočetního času na n

Měření byla provedena pomocí knihovní funkce System.nanoTime(), kterou jazyk Java poskytuje.
A to na stroji s procesorem Core Duo 1.66GHz a operačním systémem Windows XP 32bit.
Nebylo započítáváno načítaní dat ze souboru ani jejich zapisování na výstup.
U heuristiky byl započítán i čas potřebný k seřazení pole prvků dle zvoleného poměru cena/váha.

Změřené časy v nanosekundách jsou k nahlednutí v adresáři data.

Zhoršení

Průměrné zhoršení pro daný počet věcí v batohu jsem vypočítal jako aritmetický průměr relativnich chyb všech instancí.
Hodnota relatviní chyby v mém pojetí vyjadřuje o kolik procent je řešení metodou brute force lepši než řešení heuristikou.

Graf

Zhodnocení a závěr

Metoda B&B vylepšuje brute force algoritmus tak, že dává o poznání lepší výsledky, ale bohužel stejně rychle roste. Tím je pro velké instance stejně nepoužitelná. Pro menší instance nám však pomůže, protože dokáže být rychlejší než brute force i dynamické programování.

Přidáním testu na nejtěžší předmět do heuristiky jí sice nepatrně zpomalíme, ale dostaneme díky tomu nižší průměrnou relativní chybu.

Dynamické programování je pro nízký počet předmětu nejpomalejší kvůli velkému množství pomocných výpočtů, které pro jeho běh potřebujeme. Tato režie není závislá na velikosti instance. Jedná se tedy o pseudopolynomiální algoritmus. Nedosahuje sice rychlosti heuristiky, ale najde vždy optimální řešení. Je to zatím nejlepší algoritmus pro řešení problému batohu, který jsem implementoval – pokud však potřebujeme optimální řešení a velké instance (kolem 20ti a více předmětů).