Úloha 1

Autor: Petr Chytil

Zadání

• 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. Grafy jsou vítány (i pro exaktní metodu).

  • průměrné zhoršení proti exaktní metodě

  • maximální relativní chybu. Absolutní chyba nic neříká!

Zdrojový kód obou řešení

• Zdrojový kód řešení hrubou silou v jazyce Java: Brute.java

• Zdrojový kód řešení pomocí jednoduché heuristiky v jazyce Java: SimpleHeuristic.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.

Relativní chyba

Maximální relativní chyba 10,5% byla naměřena u instance č. 9087 (viz adresář data).
Brute force zde dává celkovou cenu batohu 1059, zatímco u heuristiky dostáváme cenu pouze 948.

Data, z kterých byly zhoršení a relativní chyby počítány: vypocty.pdf.