Problém batohu 2

Úloha 3

Měřil: Tomáš Davidovič (davidt2)

CPU: Core 2 Duo E6400 (1 jádro, nepřetaktováno)

OS: WinXP SP2

Jazyk: C++

Tato úloha navazuje na a doplňuje úlohu 1. Nové zadání zní:

· Naprogramujte řešení 0/1 problému batohu 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é)

· Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/hmotnost s testem nejcennější věci.

· Naprogramujte řešení 0/1 problému batohu nebo alespoň 0/1 exaktního problému batohu bez cen metodou dynamického programování.

Řešení

Pro toto rozšířené zadání jsem se rozhodl celý problém přepsat značně objektověji, výsledkem jsou třídy:

· CItem – reprezentující jeden konkrétní předmět

· CItems – reprezentuje všechny předměty dané instance

· CInstance – reprezentuje danou instanci a nabízí operace nad ní.

Tyto nabízené operace, mimo jiné, zahrnují tři nové způsoby řešení problému.

Branch and Bound – Toto řešení vychází z původního Brute Force řešení. Již původní algoritmus obsahoval ořezávání pomocí kapacity batohu, tedy pokud předměty v batohu překročily kapacitu batohu byl tento směr zastaven, oříznut. Nově je přidáno ořezávání cenou. V rekurzi se navíc ještě předává celková zbylá cena všech věcí k rozhodnutí a pokud současná cena plus tato zbylá cena jsou dohromady menší než cena nejlepšího dosud dosaženého řešení pak je i tento směr oříznut.

Jak je zřejmé z grafu, i toto řešení má exponenciální závislost, avšak roste výrazně pomaleji, než Brute Force. Je též patrné, že dochází k větším odchylkám od čistě exponenciální závislosti, pravděpodobně z toho důvodu, že efektivita algoritmu je závislá na konkrétní podobě instance.

Heuristika 2 – Jedná se pouze o lehkou modifikace heuristiky původní. Během procházení prioritní fronty se zároveň zjišťuje nejcennější předmět, který se vejde do batohu. Pokud po průchodu heuristikou je cena tohoto předmětu větší než celková cena nalezeného řešení pak se jako výsledné řešení použije batoh obsahující pouze tento předmět.

Lze říci, že algoritmus má dobrý vliv na maximální relativní chybu. Vyšší výpočetní čas může být ovlivněn objektovou implementací tohoto algoritmu, ovšem v obou případech se jedná o lineární závislost. Doplnil jsem graf poměru času, průměrné a maximální relativní chyby obou heuristik. Ač jsou body v tomto grafu proložené křivkou, je to spíše pro ilustraci, že neexistuje žádná vypozorovatelná závislost na velikosti instance. Jedinou výjimkou je čas, kde klesající tendence naznačuje existenci jistého fixního inicializačního času u Heuristiky 2, což bych připsal přechodu na objektové řešení problému.

Dynamické programování – Jedná se o klasický přiklad dynamického programování. Máme n sloupců, každý reprezentující řešení pro předměty s indexy <0; číslo sloupce> a M+1 řádků, reprezentující řešení pro batohy s kapacitou danou číslem řádku. M+1 místo pouze M je třeba aby mohla mít tabulka rozsah <0; M>. Celý algoritmus probíhá tak, že se nejdříve inicializuje první sloupec tak, že pokud se tam vejde nultý předmět tak se vloží, jinak je batoh prázdný. Tím dostaneme ideální řešení pro všechny kapacity batohu a jeden předmět. Pro každé pole každého dalšího sloupce se pak porovnává cena ideálního řešení na stejném řádku vlevo (tj. současný předmět nepřidán) s cenou získanou jako součet ceny současného předmětu (daného indexem sloupce) a ideální ceny pro batoh bez tohoto předmětu (o sloupec vlevo) ale s kapacitou sníženou o hmotnost tohoto předmětu. Vybere se výhodnější, tedy zda‑li se vyplatí přidat předmět za cenu snížení kapacity. Pro backtracking se poznamená, která možnost byla zvolena.

Po vyplnění celé tabulky, což má složitost O(n*M) následuje backtracking pro získání celé výsledné konfigurace, což má složitost O(n). Je třeba poznamenat, že ač toto řešení vypadá jako ideální postup, nebude fungovat pokud hmotnosti předmětů budou nabývat hodnot z oboru reálných čísel, neboť je třeba diskretizovat hodnotu M.

Toto řešení nemá snadno identifikovatelnou časovou závislost, protože je závislá na dvou proměnných (pseudopolynomiální). Z tohoto důvodu jsem do grafu doplnil pomocnou hodnotu, čas dělený kapacitou batohu. Tato závislost pak vychází podle předpokladu jasně lineární.

Časová náročnost

Pro měření času byla použita dodaná funkce GetMyCPUTime(), která měří procesorový čas, čímž odpadají nepřesnosti způsobené měřením systémového času v multitaskingovém operačním systému.

Měření nezahrnuje čas potřebný k načtení dat ze souboru

Výsledky jsou pak shrnuty v následujícím grafu. Prosím pozor, svislá (časová) osa je v logaritmickém měřítku.

Ins.	BF [ms]	B&B [ms]	H1 [ms]	H2 [ms]	Dyn [ms]
4	0,00047	0,00102	0,00061	0,00186	0,01830
10	0,00919	0,00619	0,00131	0,00359	0,05591
15	0,36504	0,00995	0,00195	0,00495	0,17942
20	11,31065	0,11681	0,00265	0,00610	0,31860
22	42,14063	0,35336	0,00292	0,00643	0,34299
25	345,31250	0,75536	0,00334	0,00675	0,46386
27	1450,31250	1,33825	0,00366	0,00718	0,58999
30	11723,12500	4,08967	0,00407	0,00809	0,75379
32	47149,06500	8,52605	0,00435	0,00848	0,89659
35	384323,44000	22,75212	0,00484	0,00863	1,10601
40	12455121,92000	137,34150	0,00561	0,00982	1,53777

Heuristiky

Porovnání obou použitých heuristik, tabulkou i graficky.

Heuristic 1			Heuristic 2		H2/H1 (size)		H2/H1
Ins.	Avg [%]	Max [%]	Avg [%]	Max [%]	Avg [-]	Max [-]	time [-]
4	1,45	24,75	1,33	24,75	0,92	1,00	3,05
10	0,99	9,09	1,10	11,48	1,11	1,26	2,75
15	0,36	8,54	0,31	2,77	0,85	0,32	2,53
20	0,32	8,43	0,43	4,08	1,34	0,48	2,30
22	0,48	7,23	0,54	3,02	1,13	0,42	2,20
25	0,27	3,68	0,42	2,59	1,57	0,70	2,02
27	0,43	10,60	0,29	1,85	0,67	0,17	1,96
30	0,37	5,51	0,40	1,75	1,09	0,32	1,99
32	0,37	3,34	0,27	2,28	0,73	0,68	1,95
35	0,34	4,61	0,19	1,82	0,56	0,39	1,78
40	0,25	2,34	0,15	0,95	0,61	0,40	1,75

Závěr

Je zřejmé, že jak B&B tak Dynamické programování dávají optimální výsledek v podstatně lepším čase než Brute Force. B&B algoritmus je náchylný na konkrétní podobu instance a v nejhorším případě může degenerovat až na Brute Force. Toho lze částečně eliminovat předsortováním předmětů, případně použitím vhodné heuristiky, která zaručí, že se nejdříve budou expandovat větve nejpravděpodobněji vedoucí k optimálnímu řešení, aby bylo co nejdříve k dispozici co možná nejlepší řešení pro efektivní ořez cenou.

Dynamické programování má zase problém v tom, že jeho složitost není závislá jen na velikosti instance, ale i na další proměnné, v našem případě kapacitě batohu. Problém je, že nezávisí přímo na hodnotě této proměnné, ale na tom, kolik diskrétních hodnot je třeba ji rozložit. Například pokud bychom měli hmotnosti definované v gramech (předkládám, že nyní jsou v kilech), tak by všechna řešení byla tisíckrát pomalejší. Pokud by hmotnost mohla být racionální číslo, pak by bylo dynamické programování nepoužitelné.

Vylepšená heuristika odstraňuje problém, že šlo vhodnou instancí problému dosáhnout skoro libovolné nepřesnosti. Přidáním kontroly řešení proti nejcennějšímu předmětu jsme dosáhli maximální nepřesnosti 50%.