Problém batohu - metodami DP a větví a hranic

Zadání

1. Naprogramujte řešení 0/1 problému batohu metodou větví a hranic tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria.
2. Naprogramujte řešení 0/1 problému batohu nebo alespoň 0/1 exaktního problému batohu bez cen metodou dynamického programování.
3. Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/hmotnost s testem nejtěžší věci.

Použité algoritmy

Příklad

Nechť n=5, V=(2,6,5,3,4), C=(5,9,20,12,18), a M = 10. Začneme ve sloupci n=0 a postupně plníme tabulku doprava. Výsledné řešení je určeno polem v posledním sloupci, které obsahuje váhu menší než M a má maximální index. Jestliže pole (n-1,c) obsahuje váhu stejnou jako pole (n,c), pak n-tá věc není součástí optimálního řešení  Takto se dá rekonstruovat vektor X z tabulky.

Legenda:

Dekompozice podle kapacity batohu

Nechť (X_n, C_n, m) = KNAP (V, C, M) je algoritmus řešící instanci problému batohu danou (V, C, M) a vracející vektor X, celkovou cenu C_n a celkovou váhu m. Pak můžeme KNAP napsat jako následující pseudokód, kde tečka je operátor zřetězení:

function KNAP (V, C, M)
    if isTrivial (V, C, M) return trivialKNAP (V, C, M);
    (X0, C0, m0) = KNAP (V-{vn}, C-{cn}, M);
    (X1, C1, m1) = KNAP (V-{vn}, C-{cn}, M-vn);
    if C1+cn > C0 return (X1.1,  C1+cn, m1+vn);
    return (X0.0, C0, m0);

function isTrivial (V, C, M)
    return (isEmpty (V) or M=0 or M<0);

Abychom stanovili optimální řešení pro n věcí, musíme znát

• optimální řešení problému s vyjmutou n-tou věcí (v případě, že n-tá věc v optimálním řešení není), a
• optimální řešení problému s vyjmutou n-tou věcí a kapacitou batohu sníženou o hmotnost té věci (v případě, že n-tá věc je součástí optimálního řešení).

Srovnáme-li oě varianty, zjistíme, zda n-tá věc má být v optimálním řešení. Tím jsme optimální řešení instance o n prvcích převedli na optimální řešení dvou instancí o n-1 prvcích. Rekurze se zastaví u instancí, které jsou řešitelné v konstantním čase. Funkci trivialKNAP přenecháme laskavému čtenáři jako cvičení.

Až dosud uvbedený algoritmus je hledáním do šířky. Protože pokaždé voláme funkci dvakrát a hloubka rekurze je n, je složitost 2ⁿ. Nicméně, některé instance řešíme vícekrát a můžeme tedy uschovávat řešení. Protože podúlohy pracují vždy s i prvými věcmi a množiny V and C lze považovat za globální, každá podúloha je charakterizována hodnotami n a M. Proto pamět mezivýsledků můžeme uspořádat do dvourozměrného pole indexovaného hodnotami n a M. Pole má  nM prvků a taková je i složitost algoritmu. Je polynomiální ve velikosti instance, nicméně obsahuje parametr, který s velikostí instance nesouvisí. Takové algoritmy se nazývají pseudopolynomiální.

Dynamické programování mmůžebýt buď složeno z dopředné a zpětné fáze nebo může obsahovat jen zpětnou fázi. V dopředné fázi začínáme od původní úlohy v prvku (n, M) pole a rekurzivně označujeme podúlohy, které potřebujeme řešit, až narazíme na triviální podúlohy. Ve zpětné fázi vyřešíme nejprve označené triviální podúlohy (resp. všechny triviální podúlohy, nemáme-li dopřednou fázi). Pak řešíme takové označené (resp. všechny takové) úlohy, které lze řešit pomocí úloh již vyřešených a v tabulce uložených, až dospějeme k celkovému řešení.

Příklad

 Nechť n=5, V=(2,6,5,3,4), C=(5,9,20,12,18), a M = 10. Dopředná fáze začíná s prvkem (5, 10). Abychom tuto úlohu vyřešili, potřebujeme řešení (4,10), pokud pátá věc není v optimálním řešení, a (4,6) v opačném případě.Tento postup se opakuje, až dostaneme triviální podúlohy pro n=0 nebo nekladné M. Pro názornost jsou zachyceny potřebné instance se zápornými kapacitami, ačkoliv jejich řešení je konstantní a nezávislé na parametrech.

Legenda:


Zpětná fáze začíná řešením triviálních podúloh a pak dalších ve směru rostoucího n. Dvojice(m, C_n) reprezentuje řešení každé podúlohy.


Pokud není dopředná fáze, je třeba vyřešit podúlohy ve všech prvcích pole. Na závěr rekonstruujeme vektor X. Jestliže hodnoty v prvku (n, m) jsosu stejné jako v prvku (n-1, m), pak n-tá věc není ve výsledném řešení podúlohy charakterizované (n, m). Tento postup dá optimální řešení i v případě, že obě varianty (s n-tou věcí a bez ní) dávají týž výsledek.

Naměřené hodnoty

Všechny metody

Bez hrubé síly

Bez hrubé síly a metody větví a hranic

Chyby

Data

sešit [.xls]

Program

stáhnout

Závěr