Závěrečná zpráva 3

Úvod

Popis algoritmů

Stručně popíši implementaci užitých algoritmů, pro podrobnější vysvětlení viz komentáře ve zdrojových souborech (hlavně před metodou solve).

Dynamické programování (Dynamic Programming)

Jádrem tohoto řešení je rozložení problému na menší s využitím faktu, že je-li řešení problému s k věcmi a nosností N optimální a obsahuje k-tou věc, pak optimální řešení problému s prvními k-1 věcmi a nosností (N - váha k) je toto řešení po vyjmutí k-té věci. Výhoda DP spočívá v tom, že si pamatujeme co jsme již počítali a nepočítáme to znovu. K tomu mi slouží pole bestcosts[w], w = 0 ... nosnost, které v k-tém průchodu hlavní smyčkou obsahuje nejlepší možné řešení pro prvých k věcí a nosnost batohu rovnou w. Zde je tedy srdce algoritmu:

for (int i = 0; i < nr_items; i++){

   for (int w = max_load; w > 0; --w){
     if (items[i]->weight < w) {
    // bestcosts[w] = MAXIMUM of
    // 1. best solution for k < i first items and capacity w, without i-th item, 
    // 2. best solution for k = i first items and capacity w, including i-th item
    // (which is based on the best solution for k < i and capacity (w - i-th item's weight))
    bestcosts[w] = max( bestcosts[w], bestcosts[w - items[i]->weight] + items[i]->cost ); 
    }// if
  }// for all weights

}// for all items
solution_cost = bestcosts[max_load];

Metoda větví a hranic (Branch and Bound)

Algoritmus je založen na řešení hrubou silou z první úlohy. Rozdíl je v tom, že některé větve nejsou prozkoumávány, resp. metoda descend  skončí už když se dostane do situace, že rozvíjená větev nemůže být lepší než dosud dosažené řešení (a neschází ji celou), a metoda mount obdobně pomíjí neperspektivní řešení. Jádro změn leží ve funkcích (viz dynamic_progr.hh.html) do_notExclude(int item) pro mount a lessThanBest(int item, int preceding_cost) pro descend. Obě staví na porovnání ceny nejlepšího dosud dosaženého řešení a horní meze, čili největší potenciální ceně rozvíjeného řešení, která se - při zvažování i-té věci - spočte jako součet cen věcí < i které v řešení jsou a součet cen všech věcí > i [případně + cena i-té věci].
Očividně takto určená horní mez někdy značně nadhodnocuje možnosti rozvíjeného řešení. To je cena za to, že jsem dal přednost jednoduchosti před kvalitou. Podstatně lepší by bylo užít Kolesarův algoritmus, ale s tím jsem se bohužel seznámil příliš pozdě.

Heuristika "cena/váha nebo pouze nejcennější"

Tento algoritmus je téměř totožný s heuristikou z první úlohy, jenom bylo přidáno porovnání s řešením obsahujícím pouze nejcennější věc a vybrání toho lepšího.

Výsledky

Značení: DP = Dynamické Programování, BB = metoda řezů a větví, HR = Heuristika

 1. Cena řešení

Dynamické programování a metoda větví a řezů vždy (nejen v tomto případě) najdou optimální řešení. Heuristika dává i neoptimální řešení, ale v drtivé většině případů se rozdíl od optima drží pod 1% a nikdy nepřekročí 2% (viz úkol 1 pro [horší verzi heuristiky]). Přestože naměřené výsledky mají jistou vypovídací hodnotu, nelze je zobecňovat. Připomeňme jenom, že tato heuristika má teoreticky prokázanou úspěšnost  pouze > 50% (tzn. je zaručeno, že dosáhne přinejmenším poloviny ceny optima).

2. Počet kroků k nalezení řešení

Z hlediska počtu kroků je zdaleka nejúspěšnější heuristika, vzhledem k tomu, že počet kroků je roven počtu věcí. Docela rozumné je ještě dynamické programování s O(počet věcí*nosnost). Zato metoda řezů a větví roste opravdu značně rychle, i když zpočátku je lepší než dynamické programování; kdyby používala lepší heuristiku, byly by výsledky přijatelnější, ovšem na asymptotické složitosti by se nejspíš příliš nezměnilo.

3. Doba výpočtu řešení

Následující údaje jsou pouze orientační, vzhledem k tomu, že čas běhu programu závisí na kvalitě překladače a rychlosti počítače. Slouží k ilustraci problému růstu počtu kroků.

Závěr

Z dosud řečeného plyne, že jako vítěz se pro naše vstupní data a implementaci jeví heuristika. Při praktické aplikaci je však zapotřebí pečlivě zvážit, zda je důležitější cena řešení, rychlost (největší pro heuristiku) nebo něco mezi, a to s ohledem na vnější podmínky jako dostupné výpočetní vybavení, čas a charakteristika instance.

Přílohy