Úloha 4

Autor: Petr Chytil

Zadání

• Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. Máte-li podezření na další závislosti, modifikujte zdrojový tvar generátoru.

• Na základě zjištění navrhněte a proveďte experimentální vyhodnocení kvality řešení a výpočetní náročnosti.

• Pokud možno, prezentujte algoritmy jako body v ploše, jejíž souřadnice jsou výše uvedená kritéria.

Poznámky k řešení

• 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.

• Nepřehledné výpočty vedoucí k číslům v níže uvedených tabulkách jsou k nahlédnutí v souboru vypocty.

• Každá změřená časová hodnota v tabulce je průměrem měření 50ti instancí.

Velikost instance

Graf

• závislost časové náročnosti výpočtu na velikosti instance jsme si mohli ověřit již v úkolu 3 – zdrojová data těchto grafů jsou k nalezení tamtéž.

Stejně tak máme změřeny relativní odchylky heuristik pro různě velké instance.

Maximální váha věci

Tabulka

Graf

• Z tabulky je vidět, že maximální váha věci má vliv na časovou náročnost řešení hlavně u dynamického programování. Ta stoupá téměř lineárně s rostoucí maximální váhou věci. Jistá citlivost se projevuje také u metody branch & bounds.

Maximální cena věci

Tabulka

Graf

• Z tabulky je vidět, že významější změny v naměřených hodnotách jsou jen u dynamického programování a u metody branch & bounds. Stejně jako tomu bylo u maximální hmotnosti věci. U maximalní ceny věci však nepozorujeme lineární závislost.

Poměr kapacity batohu k sumární váze

Tabulka

Graf

• U grafu je použito logaritmické měřítko.

• Vlivu tohoto parametru se vyhly pouze heuristiky. Proto je neuvádím v grafu. Nejdramatičtější závislost je z pochopitelných důvodů u brute force. Ten ořezává jen v případě plného batohu a zvyšováním poměru se zvýší počet případů, kdy k téměř žádnému ořezání nedojde.

Zhodnocení a závěr

Rozhodl jsem se měřit časovou náročnost výpočtu jednotlivých algoritmů na těchto parametrech generátoru:

• velikost instance

  • Nebýt tohoto parametru, tak si vystačíme s brute force algoritmem. Veškeré naše snažení vedlo právě ke zbavení se exponencíální závislosti na velikosti instance. U metody branch & bounds exponencielu trochu zmírníme za cenu citlivosti algoritmu na další parametry instance, u heuristik zase nedosahujeme optimálního řešení. Dynamické programování je pseudopolynomiální a závisí na mnoha parametrech instance (plyne z měření dalších parametrů generátoru instancí).

• maximální váha

  • Zde se objevila jistá závislost u metody branch & bounds. Z naměřených hodnot není jasné, zda se jedná o náhodné výkyvy nebo o nějakou silnější závislost. Dynamické programování se lineárně zpomaluje s růstem tohoto parametru. Objev takto pěkné závislosti považuji za úspěch.

• maximální cena

  • Na tento parametr byly opět citlivé metody branch & bounds a dynamické programování. Z grafu je však vidět, že závislost se pravděpodobně neřídí žádnou jednoduchou funkcí a tak si z grafu žádný objevný závěr neodneseme. Snad kromě toho, že nějaká ta citlivost na tento parametr u daných metod existuje.

• poměr kapacity batohu k sumární váze

  • Brute force zde ukazuje silnou závislost na tomto parametru. Nedá se však mluvit o tom, že by závislost rostla nade všechny meze, protože je tento parametr shora omezen jedničkou. Vše nad jedničku se řeší prostým naskládáním všech předmětů do batohu a tak si brute force projde celý stavový prostor a dosahuje nejhorší možné časové náročnosti. Ukázalo se, že zde velmi pomáhá aplikace branch & bounds metody. Časy pro velikost parametru nad 0,5 začínají dokonce klesat a pro krajní hodnoty intervalu 0 až 1 dokonce předčí dynamické programování. Je to pochopitelné, protože listy binárního stromu, který vzniká rekurzí, zde nabývají podobných hodnot sumární ceny – do batohu se vejdou téměř všechny předměty. Porovnání se zbývající cenou předmětů, které mají být ještě vloženy nám tu pomáhá a stavový prostor se pěkně prořezává. Dynamické programování je na tomto parametru silně závislé. Vždyť počet řádků tabulky, kterou vytváří a následně musí propočítat je dán právě kapacitou batohu.

Citlivost chyb heuristik jsem měřil jen u prvního parametru (převzato z úlohy 3). U dalších parametrů jsem se omezil jen na časovou náročnost. A to z důvodu počtu instancí, které bylo třeba zpracovat (viz adresář data).