Řešení hrubou silou
Pro řešení hrubou silou jsem vytvořil dva algoritmy. První
je čisté řešení hrubou silou, tedy vždy jsou zkoušeny všechny varianty.
Druhá varianta je malým zjednodušením, které
spočívá v seřazení věcí dle hmotnosti od nejlehčí. To nám umožní ukončit
větev výpočtu dříve, protože pokud se testovaná věc do batohu nevejde, nemá smysl
zkoušet ani věci následující. Tato úprava by měla přinést malé zlepšení pro
větší počet věcí (při malém počtu zabírá nějaký čas počáteční řazení
věcí).
Oba algoritmy zkouší (skoro) všechny varianty uložení věcí do batohu, jejich
složitost je tedy exponenciální - O(2n).
Řešení heuristikou
Tato varianta je zjednodušením algoritmu - nejsou
zkoušeny všechny varianty, naopak se věci přidávají, dokud se do batohu ještě
nějaká vejde. Tím samozřejmě nezískáme nejlepší řešení, ale při dobré volbě
hodnotícího kritéria se mu můžeme přiblížit. Různé heuristiky se liší volbou
pořadí přidávání věcí do batohu, v našem případě je kritériem poměr
cena/váha věci.
Heuristické algoritmy mají samy o sobě lineární složitost, která je však zhoršena
počátečním řazením (pokud se věci řadí). Proto je složitost algoritmů
většinou O(n*log(n)), podle použitého řazení.
Srovnání časové složitosti
Pro srovnání časové složitosti jednotlivých algoritmů uvádím tabulku průměrné
doby běhu algoritmu pro 50 instancí (zkušební data) v závislosti na počtu věcí. Je
důležité upozornit, že hodnoty neuvádí přímo časovou složitost algoritmu, ale
celkovou dobu běhu, přičemž není vždy možno zaručit algoritmu všechen čas
procesoru - hodnoty mohou být ovlivněny swapováním OS. Neuvedené hodnoty byly
příliš časově náročné pro měření.
Pro přehlednější srovnání je též uveden graf vytvořený z této tabulky.
| počet věcí | hrubá síla 1 | hrubá síla 2 | heuristika |
| 4 | < 1 | < 1 | < 1 |
| 10 | 1.0 | 3.2 | < 1 |
| 15 | 129.6 | 129.8 | 1.2 |
| 20 | 3507.8 | 3058.4 | < 1 |
| 22 | 14928.8 | 13989.4 | 2.2 |
| 25 | 107382.1 | 107952.8 | < 1 |
| 27 | 531990.0 | 1.0 | |
| 30 | < 1 | ||
| 32 | < 1 | ||
| 35 | < 1 | ||
| 37 | 1.2 | ||
| 40 | 1.0 |
Chyba heuristické metody
Jak již bylo uvedeno, pomocí heuristických metod nezískáme přesné řešení, ale
řešení jemu "blízké" - ale radikálně snížíme složitost algoritmu.
Následující tabulka je srovnáním výsledků heuristické metody s optimálním
řešením. Pro každý počet věcí byly otestovány výsledky algoritmu se všemi 50-ti
instancemi.
Přesnost řešení je průměr "relativní přesnosti" - poměru
cena_heuristika / cena_max. Počet přesných výsledků udává, pro kolik z
50-ti instancí byl výsledek heuristického algoritmu optimální (přesnost 100%). Maximální
chyba je maximální relativní chyba ze všech instancí (1 - přesnost), ID
max. chyby je ID instance, pro kterou byla chyba řešení maximální.
| počet věcí | přesnost řešení [%] | počet přesných výsledků | max. chyba [%] | ID max. chyby |
| 4 | 92.81 | 32 | 68.37 | 9002 |
| 10 | 97.07 | 23 | 15.72 | 9079 |
| 15 | 99.20 | 30 | 5.64 | 9100 |
| 20 | 98.73 | 20 | 6.12 | 9184 |
| 22 | 98.57 | 15 | 8.75 | 9211 |
| 25 | 98.74 | 16 | 5.42 | 9272 |
| 27 | 99.09 | 18 | 3.87 | 9320 |
| 30 | 99.04 | 8 | 3.33 | 9355 |
| 32 | 99.31 | 14 | 3.61 | 9404 |
| 35 | 99.05 | 14 | 3.82 | 9480 |
| 37 | 99.39 | 16 | 2.20 | 9514 |
| 40 | 99.38 | 12 | 2.54 | 9558 |
Pokud by vás zajímaly podrobné výsledky měření, jsou zazipované ke stažení zde. V adresářích output se nachází výsledek algoritmu se stejným formátem jako originální výsledky, adresář table obsahuje "důležitá" data - ID zadání, čas běhu algoritmu v ms, dosažená cena, optimální (maximální) cena a relativní chyba řešení ((opt-max) / max) (není uvedena v procentech, i když jsou procenta za hodnotou uvedeny).
Ověřili jsem exponenciální složitost řešení problému batohu hrubou silou a
též praktickou neřešitenost problémů s takto velkou složitostí - pro poměrně
malý počet věcí (30) je již doba běhu algoritmu nepřípustná (více jak 20min).
Srovnáním s heuristickou metodu jsme též ověřili značný rozdíl mezi
polynomiální a exponenciální složitostí.
Též byl ověřen předpoklad kratšího běhu upravené metody hrubou silou (pro n = 25
nebyl test zcela přesný, u 1. metody byly z časových důvodů provedeny pouze tři
měření. Toto zlepšení je však vzhledem k celkovému běhu algoritmu zanedbatelné.
Při kontrole chyb heuristické metody jsme dospěli k závěru, že pro větší počet věcí (>10) je toto řešení v průměru srovnatelné a v našich případech dokonce ani největší chyby nejsou nijak extrémně velké (to však nemusí platit obecně).