Problém batohu 2

Úloha z předmětu 36PAA

Martin Tůma

Zadání

  1. Naprogramujte řešení 0/1 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. 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 nejcennější věci.

Zpráva by měla obsahovat:

Řešení

1. Řešení metodou větví a hranic

Metoda větví a hranic spočívá v rozvětvování stavovým prostorem v nejperspektivnějším směru a "odřezávání" (tzn. ukončení cesty) větví, kde již nemůžeme dosáhnout lepšího výsledku než je aktuální nalezené maximum. V implementaci je pro průchod stavovým prostorem použito prohledávání do hloubky (implementované rekurzí) nad prvky seřazenými sestupně dle ceny, tzn. výběr následujícího prvku je určen heuristikou dle ceny. Přesto, že heuristika dle poměru C/m dosahuje obecně lepších výsledků, byla zvolena tato heuristika, neboť zamezuje "výrazně nepříznivým průchodům stavovým prostorem". Složitost algoritmu je O(2n).

2. Řešení metodou dynamického programování

Metoda dynamického programování staví na rozdělení problému na nezávislé podproblémy, které je možno "předpočítat" a z jejich výsledků pak sestavit celkové řešení. V implementaci je použita dekompozice podle kapacity batohu, která spočívá ve výpočtu optimálního ř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ího řešení problému s vyjmutou n-tou věcí a kapacitou batohu sníženou o hmotnost n-té věci (v případě, že n-tá věc je součástí optimálního řešení). Z těchto dvou hodnot lze pak určit, zda se n-tá věc nachází v optimálním řešení či nikoliv. Podrobný popis algoritmu uvádí [2]. Algoritmus má pseudopolynomiální složitost O(mmax·n).

3. Řešení heuristikou podle poměru C/m s testem Cmax

Postup řešení je následující: V prvním kroku se provede výpočet řešení heuristikou typu nejrychlejšího vzestupu (dle poměru C/m) a ve druhém kroku se tento výsledek srovná s řešením sestávajícím pouze z jediného, nejcenějšího, předmětu. Konečným výsledkem je pak maximum z obou řešení. Složitost algoritmu je O(n·log(n)) a maximální chyba heuristiky 50% [3].

Naměřené hodnoty

Měření probíhala v následujícím prostředí: PC s CPU Celeron M 1.47GHz, Linux 2.6.20, gcc 4.1.2. Naměřené časy u časových závislostí jsou udávány vždy pro celý vstupní soubor, tzn. 50 instancí problému.

Časové závislosti

n410152022 252730323537 40
B&B 0.641.061.311.972.72 3.373.956.6714.6317.17 17.5962.41
Dyn. 2.125.8618.2429.3031.88 43.1254.6068.6882.25100.41 116.13113.46

Tabulka 1: Naměřené výpočetní časy [ms].

Graf 1: Srovnání výpočetních časů dynamického programování a B&B

Relativní chyby heuristiky

Vstupní data ηø [%] ηmax [%] ηøh2øh1 [%]
knap_4.txt1,328324,745861.08
knap_10.txt1,104411,480185.86
knap_15.txt0,30502,774864.08
knap_20.txt0,43144,079371.88
knap_22.txt0,54213,017778.94
knap_25.txt0,42482,587785.23
knap_27.txt0,28961,845157.72
knap_30.txt0,39721,749178.28
knap_32.txt0,27442,278280.42
knap_35.txt0,18801,817267.09
knap_37.txt0,17971,176052.29
knap_40.txt0,15270,945776.54

Tabulka 2: Relativní chyby kombinované heuristiky (h2) a srovnání její efektivity (jako poměr chyb) s heuristikou typu nejrychlejšího vzestupu (h1)[4].

Závěr

Implementace pomocí metody větví a hranic dosáhla na všech instancích nejlepšího výsledku ze všech tří "exaktních" metod (hrubá síla, B&B, dynamické programování), nicméně za pomoci extrapolace naměřených výsledků lze odhadnout, že pro n>40 je již výhodnější použít metodu dynamického programování. Přesto, že B&B metoda výrazně snižuje výpočetní náročnost oproti metodě hrubé síly (v poslední měřené instanci n=27 106x!), potvrdily testy exponenciální složitost algoritmu.

Metoda dynamického programování je nejvhodnější (a pro opravdu velká n pravděpodobně i jedinou možnou) metodou pro instance kde n>40. Tedy alespoň pro případy, kdy jsou hmotnosti jednotlivých věcí celočíselné (či je požadované rozlišení reprezentace reálných čísel dostatečně malé) a "rozumně" veliké.

Použití kombinované heuristiky (podle poměru C/m s testem Cmax) snížilo relativní chybu heuristiky. Test Cmax je účinný především u instancí, kde se vyskytuje jedna věc s hodnotou blížící se optimu a mnoho "levných" věcí s poměrem C/m větším než tato věc.

Reference

[1] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html
[2] http://service.felk.cvut.cz/courses/36PAA/by_m.html
[3] http://service.felk.cvut.cz/courses/36PAA/greedyproof.html
[4] http://tumic.wz.cz/fel/online/36PAA/1

Přílohy

1. batoh_bb.c - Program pro řešení metodou B&B.
2. batoh_dyn.c - Program pro řešení dynamickým programováním.
3. batoh_h2.c - Program pro řešení heuristikou podle poměru C/m s testem Cmax