Závěrečná zpráva

Jakub Holý: Řešení problému batohu hrubou silou a heuristikou
36PAA LS 2003

Úvod

Teoretický úvod a vysvětlení metody hrubé síly resp. heuristiky s dovolením vynechám, neboť jsou obsaženy v zadání (pro zvědavé viz odkazy).
V následujících odstavcích porovnávám obě metody řešení podle rychlosti výpočtu (je zde brán skutečný čas, což zdaleka není optimální, ale pro naše účely to stačí) a podle optimality (metoda hrubé síly samozřejmě vždy najde nejlepší řešení - bráno podle ceny obsahu - a otázka je pouze jak dobrá je heuristika, která je nutně podoptimální).

Algoritmy

1. Hrubá síla

Algoritmus zkouší všechny možnosti, které nepřekračují nosnost batohu. Jinak řečeno, prochází téměř celý stavový prostor, který lze reprezentovat jako listy binárního stromu - cesta do daného listu určuje, které věci jsou v batohu obsaženy (n-tý uzel má následující dva potomky: "n-tá věc je obsažena" a "n-tá věc není obsažena"). Má implementace neužívá reprezentace celého stromu (případně okleštěného o "řešení" nesplňující omezující podmínku), ale místo toho pracuje s obrazem cesty v tomto grafu, počínající kořenem a končící v listu. Tato cesta je měněna, až dokud nejsou vyzkoušeny všechny přijatelné možnosti. Pro podrobnosti viz rozsáhlé komentáře ve zdrojovém kódu.

2. Heuristika

V tomto způsobu řešení věci seřadíme podle poměru cena/váha a následně je v tomto pořadí zkoušíme vložit do batohu; pokud by vložením nějaké věci došlo k překročení maximální kapacity (nosnosti), tato věc vložena není a pokračuje se s následující (tzn. algoritmus zde neskončí, ale pokračuje až k poslední věci v řadě). Tato heuristika byla zvolena, protože z představených metod je nejpropracovanější a zároveň je stále jednoduchá.

Porovnání rychlosti

Naměřené hodnoty jsou pouze orientační a slouží jen k hrubému porovnání obou metod navzájem. Na jiném stroji či při použití lepšího překladače by byly odlišné.
graf porovnani rychlosti
žlutá - heuristika
fialová - řešení hrubou silou

Z grafu jasně vidíme, že podle očekávání doba výpočtu pro metodu hrubé síly s počtem věcí exponenciálně roste, zatímco doba výpočtu heuristickou metodou je téměř konstantní (pomalejší řazení věcí a prodloužení času na procházení seřazených věcí je zde zanedbatelné).

Porovnání úspěšnosti

1. Četnost dosažení nejoptimálnějších výsledků heuristikou

Následující graf ukazuje, jak často heuristický algoritmus dosáhl téhož výsledku, jako metoda hrubé síly.
Graf uspesnosti

Zpočátku je heuristika skoro tak úspěšná, jako metoda hrubé síly, později však procento případů, kdy dosáhla nejlepšího řešení, klesá. To souvisí s rostoucí složitostí problému a tím i rostoucím množstvím těch lepších řešení, která heuristice uniknou.

2. Průměrná odchylka od optimality

Podívejme se, jak moc se řešení heuristikou odchyluje od optimálního řešení. Následující tabulka obsahuje pro každý počet věcí průměrnou odchylku od optimálního výsledku spočtenou vždy jako průměr z padesáti relativních odchylek pro jednotlivé instance. Odchylka pro instanci byla spočtena takto:
(optimální výsledek - výsledek heuristiky) / optimální výsledek

Odchylka od optimality
4 věci
 10 věcí
 15
 20
 22
 25
 27
 30
 32
 35
 37
 40 věcí
1,9%
 1,4%
 0,3%
 0,6%
 0,5%
 0,4%
 0,7%
 0,5%
 0,5%
 0,4%
 0,4%
 0,4%

Jsou-li výsledky správné, můžeme pozorovat jev, který jsem neočekával - ač klesá množství případů, kdy bylo dosaženo nejlepšího výsledku (viz předchozí graf), tak výsledky heuristiky se blíží výsledkům metody hrubé síly, jinak řečeno, výsledky dosažené heuristikou se nezhoršují, ale zlepšují. Příčinou nejspíše bude to, že v rostoucím množství věcí a tím i celkové ceny obsahu batohu se pár ne zcela ideálně zvolených věcí lépe "ztratí".

Největší odchylka od optimálního řešení byla 0,25%, v absolutních číslech 222 oproti 295 (nastalo pro 4 věci).

Závěr

Heuristika se na daných instancích ukázala jako velmi dobrá, takže ji lze použít i pro jednodušší problémy, které ještě v rozumném čase zvládne i metoda hrubé síly. Pro problémy složitější nám nic jiného nezbude, vzhledem k exponenciálnímu nárůstu spotřeby času u metody hrubé síly. Domnívám se, že odchylka od optima je opravdu nízká, a není tedy třeba usilovat o nalezení lepší heuristiky.

Přílohy

Zdrojové kódy programového řešení:
  1. zpracování soboru se vstupními daty (společné pro obě řešení):
    ksack_in.hh.html a ksack_in.cc.html
  2. řešení hrubou silou:
    hw1_force.hh.html a hw1_force.cc.html
  3. řešení heuristikou:
    hw1_heuristic.hh.html a hw1_heuristic.cc.html