Úkol 3 - problém batohu (knapsack problem)

• CTU Prague, MI-PAA, ZS 2011
• Autor: Tomáš Borovička (borovto1)

Zadání

• Naprogramujte řešení problému batohu:
  1. metodou větví a hranic (B&B) tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria. Tj. použijte ořezávání shora (překročení kapacity batohu) i zdola (stávající řešení nemůže být lepší než nejlepší dosud nalezené)
  2. metodou dynamického programování (dekompozice podle vah nebo podle cen)
  3. modifikujte tento program tak, aby pracoval s omezenou přesností zobrazení vah nebo cen (podle zvoleného přístupu k dynamickému programování) - aproximativní algoritmus.

Je dán batoh s kapacitou W a monožina předmětů N, kde každý předmět má svou váhu w_i a cenu v_i. Úkolem je najít takovou podmonožinu N, která maximalizuje cenu předmětů v batohu a nepřesáhne svou vahou kapacitu batohu W. Problém batohu je kombinatorický optimalizační problém spadající do třídy NP úplných problémů.

• Metodaje vychází z původního řešení hrubou silou. Principem metody větví a hranic je ořezávání stavového prostoru o stavy, které nevedou k optimálnímu řešení.
  • Ořezávání shora: stav je ukončen, pokud by měla být překročena kapacita batohu.
  • Ořezávání zdola: stav je ukončen, pokud je aktuální řešení horššší než nejlepší nalezené.

        private Solution SolveBranchAndBound(Solution solution, int idx)
        {
            if (idx < 0) return solution;
 
            // branch and bound
            if (_residualValues[idx] + solution.Value <= _bestSolution.Value) return solution;
 
            if (solution.ResCapacity < solution.Instance.Items[idx].Weight)
                return SolveBranchAndBound(solution, idx - 1);
 
            var s1 = solution;
            var s2 = solution.Clone();
 
            //            s2.Bits[idx] = true;
            s2.Value += solution.Instance.Items[idx].Value;
            s2.ResCapacity -= solution.Instance.Items[idx].Weight;
 
            s1 = SolveBranchAndBound(s1, idx - 1);
            s2 = SolveBranchAndBound(s2, idx - 1);
 
            solution = s1.Value > s2.Value ? s1 : s2;
 
            _bestSolution = solution;
 
            return solution;
        }

• Dynamické programování je založeno na dekompozici problémů, řešení jednotlivých subproblému a následné skládání problému s využitím těchto vyřešených subproblémů. Následující algoritmus reší problém dynamickým programováním s dekompozicí podle kapacity. Pro ukládání vesledků využívá algoritmus dvourozměrného pole _solutionCache[kapacita+1, pocet prvku]. Při průchodu pak algoritmus testuje, zda není subproblém vyřešen a pokud ano využije vypočtených hodnot.

        private Solution SolveDynamic(Solution solution, int idx, int weight)
        {
            if (weight < 0) return new Solution(solution.Instance){Value = int.MinValue};
            if (idx < 0) return new Solution(solution.Instance);
 
            if (_solutionCache[weight, idx] != null)
            {
                return _solutionCache[weight, idx].Clone();
            }
 
            var s1 = solution;
            var s2 = solution.Clone();
 
            s1 = SolveDynamic(s1, idx - 1,weight);
            s2 = SolveDynamic(s2, idx - 1,weight-solution.Instance.Items[idx].Weight);
 
            s2.Value += solution.Instance.Items[idx].Value;
            s2.ResCapacity -= solution.Instance.Items[idx].Weight;
            var result =  s1.Value > s2.Value ? s1 : s2;
 
            _solutionCache[weight, idx] = result.Clone();
            return result;
        }

• FTPAS algoritmus je plně polynomiální časově aproximační algoritmus. Respektive jedná se stále o stejný dynamický algoritmus ovšem využívající plně polynomiální časově aproximační schéma (FPTAS). To umožňuje řešit problém s libovolně stanovenou přesností , kde výpočetní složitost algoritmu se zvyšováním přesnosti neporoste hůře, než polynomiálně.
• Princip algoritmu spočívá v “zaokrouhlení” parametru jež má vliv na počet stavů, které se mohou při řešení vyskytovat. V následujícím algoritmu je tímto parametrem váha předmětů (a s nimi samozřejmě kapacita batohu). Samotné zaokrouhlení spočívá v zanedbání posledních x bitů z váhy předmětu (neboli ve vydělení váhy mocninami 2).

        public void RoundByWeight(int bitsToRound)
        {
            Capacity = Capacity >> bitsToRound;
            foreach (var item in Items)
            {
                item.Weight = item.Weight >> bitsToRound;
            }
        }
 
        public Solution SolveFTPAS(Instance instance)
        {
            instance.RoundByWeight(BitsToRound);
            _solutionCache = new Solution[instance.Capacity + 1, instance.Items.Count];
            _solutionCache.Initialize();
            return SolveDynamic(new Solution(instance), instance.Count - 1, instance.Capacity);
        }

Windows Server 2008 EE x64, Intel Core2 Duo E8500@3.16GHz, 8 GB DDR2

Z tabulky a grafu 1 (v logaritmickém měřítku) je vidět exponenciálně rostoucí čas řešení hrubou silou i metodou branch and bound, i když metodou B&B roste čas výrazně pomaleji. Naopak téměř lineární růst výpočetní času s velikostí instance můžeme pozorovat při dynamickém programování a aproximativním řešení.

Graf 1

• Podle očekávání relativní chyba roste s počtem zanedbaných bitů jak ukazuje Graf 2. Výraznější chyba začíná být od tří zaokrouhlených bitů, kde u většiny instancí překračuje hranici 10%.

Graf 2

• Zanedbáním x nejméně významných bytů redukujeme počet možných stavů problému, důsledkem čehož musí klesat i výpočetní čas. Důkazem je Graf 3, kde FTPAS 0 je vlastně dynamický algoritmus a FTPAS 6 je řešení se zanedbáním 6 posledních bitů.

Graf 3

Jako nejlepší řešení problému batohu se ukázalo řešení dynamickým programováním, pokud bychom si mohli dovolit ztrátu přesnosti, může nám výrazně snížit výpočetní čas aproximativní řešení s využitím FPTAS.

• http://en.wikipedia.org/wiki/Knapsack_problem
• http://rosettacode.org/wiki/Knapsack_problem/0-1