Úloha 3 - Řešení problému batohu dynamickým programováním, metodou větví a hranic a aproximativním algoritmem

• MI-PAA, ZS 2011/12
• Autor: Jaroslav Fibichr (fibicjar)

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.

Řešený problém se shoduje se zadáním v úkolu 1, tedy:

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ů.

Naprogramoval jsem řešení zadanéúlohy popsanými metodami. Výsledky měření jsem shrnul do tabulek a grafů a v závěru shrnul nabyté poznatky.

Metoda vychází z původního řešení hrubou silou. Úkolem je omezit průchod stavovým prostorem pouze na ty větve, které mají smysl, tedy takové, o kterých můžeme s jistotou říci, že nevedou k optimálnímu řešení. Lze provádět ořezávání dvou typů:

• Shora - do batohu nepřidáváme věci, pokud byla překročena jeho kapacita
• Zdola - do batohu nepřidáváme věci, pokud součet hodnot všech zbývajících věcí, které jsme ještě nezkusili přidat, a dosavadní ceny batohu je menší než doposud nejlepší nalezená celková cena. Tento přístup vyžaduje uchovávání “globální” nejlepší dosažené hodnoty ceny batohu a její případná aktualizace.

Složitost zůstává stejná jako u řešení hrubou silou (O(2ⁿ)), metoda by však měla být výrazně rychlejší. Nalezne vždy optimální řešení.

    private Solution solveBaB(Instance instance, Solution solution, int index) {
 
        if (index < 0) {
            return solution;
        }
 
        if (instance.items[index].weight > solution.remCapacity) {
            return solveBaB(instance, solution, index - 1);
        }
        if (instance.remValues[index] + solution.value < instance.bestSolution.value) {
            return solution;
        }
 
        Solution s1 = solution;
        Solution s2 = solution.clone();
 
        s2.value += instance.items[index].value;
        s2.remCapacity -= instance.items[index].weight;
        s2.taken[index] = 1;
 
        s1.remValue -= instance.items[index].value;  // BaB
        s2.remValue -= instance.items[index].value;  // BaB
 
        s1 = solveBaB(instance, s1, index - 1);
        s2 = solveBaB(instance, s2, index - 1);
 
        solution = s1.value < s2.value ? s2 : s1;
        instance.bestSolution = solution;           // BaB
        return solution;
    }

U dynamického programování dekomponujeme problém na jeho podproblémy. Zvolil jsem variantu dekompozice podle kapacity batohu. Řešení každého vyřešeného podproblému je opět nutné ukládat do “globálního” dvourozměrného pole, které uchovává dosažené hodnoty pro jednotlivé dvojice W (kapacita), i (počet předmětů). V případě, že je podproblém již vyřešen, vezme se tato hodnota z tohoto pole namísto opětovného počítání. Algoritmus se skládá z obou fází - dopřednou i zpětnou. Nepředpočítáváme tedy řešení pro podproblémy, které nejsou pro hledané řešení potřeba.

Složitost tohoto algoritmu je pseudopolynomiální, závisí totiž i na jiném parametru než je počet prvků.

    private Solution solveDynamic(Instance instance, Solution solution, int index, int weight) {
 
        if (weight < 0) {
            Solution s = new Solution(instance);
            s.value = Integer.MIN_VALUE;
            return s;
        }
        if (index < 0) {
            return new Solution(instance);
        }
 
        // return already known
        if (instance.solMatrix[index][weight] != null){
            return instance.solMatrix[index][weight].clone();   // pomocné pole
        }
 
        Solution s1 = solution;
        Solution s2 = solution.clone();
 
        s1 = solveDynamic(instance, s1, index - 1, weight );
        s2 = solveDynamic(instance, s2, index - 1, weight - instance.items[index].weight);
 
        s2.value += instance.items[index].value;
        s2.remCapacity -= instance.items[index].weight;
        s2.taken[index] = 1;
 
        Solution result  = s1.value < s2.value ? s2 : s1;
        instance.solMatrix[index][weight] = result.clone();  // pomocné pole
        return result;
    }

Aproximativní algoritmus je založen na předchozím dynamickém, tedy na verzi s dekompozicí podle vah. Pomocí FPTAS lze řešit problém se stanovenou přesností a zvyšování přesnosti zvyšuje složitost ne více než polynomiálně. Aproximativní algoritmes se tedy liší se tím, že před samotným spuštěním dynamického algoritmu “zaokrouhlí” kapacitu batohu i jednotlivé hmotnosti vkládaných předmětů. Toho dosáhneme zanedbáním nejnižších bitů těchto hodnot o zvolenou hodnotu.

        ...
        instance.capacity = instance.capacity >> instance.bits;
        for (int i = 0; i < instance.itemCount; i++) {
            instance.items[i].weight = instance.items[i].weight >> instance.bits;
        }
        instance.solMatrix = new Solution[instance.itemCount][instance.capacity+1];   // pomocné pole
 
        Algorithm algorithm = new Dynamic();
        Solution result = algorithm.run(instance, solution);
 
        return result;

• Intel Core2 Duo E7200@2.5GHz, 4 GB DDR2
• Windows 7 64-bit

V následující tabulce a grafu jsou znázorněny výsledky měření jednotlivých algoritmů na daných počtech předmětů a instancí. Je zřetelné, že složitost jednotlivých algoritmů se se zvyšujícím počtem prvků v batohu se je jednoznačně určná uspořádáním:

BruteForce > Branch&Bound > Dynamic > FPTAS(2)

Jediný algoritmus, který nevrací zaručeně optimální řešení je FPTAS, tudíž nejlepší z implementovaných algoritmů, který dává optimální řešení je dynamické programování.

Pozn.: Měření pro velmi krátké časy (< 1 ms) bylo opakováno vícenásobně a následně průměrováno pro dosažení kvalitnějších výsledků.

Podle očekávání se se zvyšujícím počtem zanedbaných bitů:

• snižuje výpočetní čas
• zvyšuje relativní chyba

V tabulce je možné pozorovat výsledky měření pro různé hodnoty zanedbaných bitů. Algoritmus dynamického programování, ze kterého metoda vychází je rovna FPTAS(0). Ta vrací vždy optimální řešení, proto je relativní chyba pro jakýkoliv počet předmětů roven 0. Relativně vysoká míra relativních chyb je z velké části dána nízké “granularitě” vstupních dat. To platí především pro nízká N. V případě zanedbání 3 a více bitů relativní chyba téměř vždy překračuje 5%. Tím například výrazně překračuje chybovost i heuristiky implementované v úkolu č.1.

Z hodnot i grafu naměřených časů lze vyčíst, že čas klesá s počtem zanedbaných bitů exponenciálně. Například pro největší instance se 40 předměty dosáhla v průměru pod 4 ms.

Naimplementoval jsem podle zadání různé metody řešení zadaného problému batohu. Z měření vyplynulo:

• v případě požadavku na optimálnost řešení je nejvhodnější algoritmus dynamického programování, ten dosahoval nejnižších časů výpočtu
• pokud lze požadavek optimálnosti opustit, lze pomocí algoritmu FPTAS dosahovat ještě výrazně lepších časů, ovšem za cenu snižování přesnosti řešení

u3_jaroslav_fibichr_2011.zip