PAA 2007-2008, Petr Maj (majp1)

Zadani ukolu

Naprogramujte řešení 0/1 problému batohu hrubou silou. Pozorujte závislost výpočetního času na n.

Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/váha. Pozorujte:

závislost výpočetního času na n
průměrné zhoršení proti exaktní metodě
maximální relativní chybu.

Reseni Hrubou Silou

Reseni hrubou silou spociva v postupnem projiti vsech stavu reseni (stavy reseni jsou bitove vektory stejne delky jako pocet veci ktere muzeme do batohu dat) , kterych je 2^n a jedna se tedy o exponencialni slozitost. Diky tomu byla data pocitana pouze pro instance delky 4, 10 a 15, pro vetsi instance jiz byla celkova doba vypoctu neunosna.

Algoritmus provadi jednoduchou kontrolu pripustnosti reseni, kdy se netestuji potomci stavu, ktery jiz sam neni pripustny (vaha veci jiz obsazenych v batohu je vetsi nez maximalni povolena mez). Jak vyplyva z tabulky, toto "vylepseni" vsak nema na exponencialni slozitost algoritmu samozrejme zadny vliv.

Optimalni reseni je timto algoritmem nalezeno vzdy. V tabulce jsou zaznamenany minima, maxima a prumery pro celkovy cas straveny na procesoru (bezrozmerne diky vicenasobnemu pocitani instance v pripade nulovych casu), pocet navstvivenych stavu a presnost reseni, ktera je pocitana jako nalezene reseni/optimalni reseni. (samozrejme u brute force algoritmu vzdy rovna 1.0).

Instance Size	Tested Instances	Maximal Time	Minimal Time	Average Time	Maximal Visited States	Minimal Visited States	Average Visited States	Maximal Accuracy	Minimal Accuracy	Average Accuracy
4	15	0.18	0.02	0.096	23	14	19.0	1.0	1.0	1.0
10	15	2.0	0.27	1.17	1535	589	1141.0	1.0	1.0	1.0
15	15	72.0	63.0	70.3333333333	49151	44018	48382.0	1.0	1.0	1.0

Tabulka hodnot namerenych pro algoritmus bruteforce

Reseni Greedy Algoritmem

Greedy algoritmus ktery byl pouzit srovna vsechny polozky podle pomeru cena/vaha od nejlepsi k nejhorsi a pote je pridava od nejlepsi do batohu. Pokud nemuze danou polozku vlozit, pokracuje na dalsi az do konce.

Slozitost tohoto reseni je zavisla na pouzitem algoritmu trideni (jelikoz byla pouzita standardni funkce sort pro seznamy v jazyce Python, da se ocekavat ze bude optimalni a tedy slozitost v prumernem pripade blizka n log n + n, kde +n je za projiti setrideneho pole a pridani polozek do batohu. V pripade pouziti quicksort muze byt samozrejme slozitost az n^2 v nejhorsich pripadech.

Instance Size	Tested Instances	Maximal Time	Minimal Time	Average Time	Maximal Visited States	Minimal Visited States	Average Visited States	Maximal Accuracy	Minimal Accuracy	Average Accuracy
4	15	0.23	0.19	0.210666666667	4	4	4.0	1.0	0.887755102041	0.987825171189
10	15	2.24	1.0	2.11466666667	10	10	10.0	1.0	0.909090909091	0.988862892612
15	15	12.95	12.8	12.874	15	15	15.0	1.0	0.984308736217	0.997162655518
20	15	13.17	12.97	13.0713333333	20	20	20.0	1.0	0.959207014868	0.993517558585
22	15	13.42	13.2	13.3093333333	22	22	22.0	1.0	0.980753480753	0.995230765361
25	15	13.71	13.45	13.5766666667	25	25	25.0	1.0	0.99191848208	0.997338311012
27	15	14.0	1.0	13.012	27	27	27.0	1.0	0.983650316984	0.996990476767
30	15	14.34	14.03	14.1853333333	30	30	30.0	1.0	0.982508882208	0.996239878563
32	15	14.69	1.0	13.632	32	32	32.0	1.0	0.966592427617	0.995675118694
35	15	15.1	14.73	14.92	35	35	35.0	1.0	0.953907815631	0.994491508582
37	15	15.52	1.0	14.3786666667	37	37	37.0	1.0	0.988240324995	0.997992994075
40	15	16.01	15.57	15.788	40	40	40.0	1.0	0.991683524388	0.998626875885

Tabulka hodnot pro greedy algoritmus

Vysledne grafy

Popis implementace a Zaver

Celou ulohu (tedy G i BF algoritmus) jsem implementoval v jazyce python jako skript ktery precte instance, vypocita je a pote automaticky vygeneruje vsechny vysledky (grafy, data, tabulky, atd).

zdrojovy kod

Diky chybe v programu, kde se stav pricita na dvou mistech je potreba hodnoty navstvivenych stavu vydelit dvema a odecist jednicku pro dosazeni spravneho vysledku. Cas je v poradku.

Zaver

V pripade BF se zadne prekvapeni nekonalo, tedy krome toho ze uz pro hodnotu 20 bylo dost nerealne cekat na vysledek vypoctu. Co se greedy algoritmu tyce, byl jsem osobne velice prekvapen tim, jak mala je jeho chyba v porovnani k optimu. Cim vice polozek v batohu, tim byla chyba mensi a hranice chyby jedno procento byla prekracovana jen vyjimecne. To muze byt samozrejme dano idealnimi daty, ale predpokladal bych ze zadana data byla prumerem. V nejhorsim moznem pripade by byla jeho uspesnost rozhodne mensi.