PAA 2007-2008, Petr Maj (majp1)
Pro řešení problému batohu existuje mnoho algoritmů jak exaktních, tak přibližných. O jejich vlastnostech toho není mnoho známo, pouze pro kombinované heuristiky byla dokázána maximální chyba. Chceme-li vědět více, musíme vyhodnocovat experimentálně.
Budeme sledovat dva podstatné parametry - kvalitu řešení a výpočetní náročnost. Uvedeme-li obě tyto veličiny do vytahu, dozvíme se, pro které kombinace nároků na čas a kvalitu je ten který algoritmus nejvýhodnější. Kvalita řešení
Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. Máte-li podezření na další závislosti, modifikujte zdrojový tvar generátoru. Na základě zjištění navrhněte a proveďte experimentální vyhodnocení kvality řešení a výpočetní náročnosti. úplné zadání úlohy
Dynamicke programovani pouzite pro reseni problemu batohu je pseudopolynomialni algoritmus, coz znamena ze krome velikosti instance zalezi take na dalsich okolnostech. V nasem pripade je to na maximalni vaze batohu, ktera bohuzel rostla mnohem rychleji nez pocet instanci, takze pro vypocet batohu o velikosti 1000 jiz vypocet trval 120 sekund, pro 1200 jsem provedl pouze jeden vypocet ktery trval pres 10 minut a pro 1400 jiz nestacila pamet (bylo potreba pres 1 GB pameti za predpokladu ze integer ma 6 byte).
Velkou vyhodou tohoto algoritmu vsak je zavislost "pouze" na teto velikosti batohu, proto jsem ani nemeril pro zadnou velikost dynamicke programovani vic nez jednou, protoze pocet provedenych ukonu je vzdy zhruba stejny (samozrejme v zavislosti na kapacite batohu, ta se vsak da rici ze je pro instance dane velikosti vzdy velice podobna).
Protoze jsem jiz z minule ulohy tusil ze na zakladnich datech si algoritmus povede dobre, zkusil jsem nejprve nalezt takove instance, ve kterych by na tom metoda vetvi a hranic byla velice spatne.
Nejprve jsem myslel ze bude algoritmus velice zavisly na tom, jak blizko se pocatecni reseni nalezene greedy algoritmy priblizi optimu. Zkusil jsem proto otestovat tuto zavislost na 1000 instancich velikosti 200. Ackoli jsem zjistil, ze opravdu pocet navstivenych stavu klesa s tim jak moc se greedy algoritmus priblizil optimu, rozdily byly vylozene minimalni, a proto ani neuvadim graf. Mnou namerene hodnoty jsou k dispozici v souboru fastbb_dependency.dat.
Dale jsem se pokusil algoritmus zhorsit tim, ze jsem vypustil jeho dalsi vyznamnou slozku, tedy orezavani na spodni cele cislo. Toho jsem dosahl tim ze vetsina pomeru cena/vaha byla vetsi nez 1.0. Na jedne testovaci instanci delky 40 kterou jsem vytvoril rucne se opravdu ukazal propad oproti prumeru.
Do tretice jsem zkusil nalezt pomoci generatoru instanci na strankach takove parametry, ktere by davaly nejhorsi vysledky. Nejprve jsem zjistil ze idealni pomer k celkove vaze je 0.35, dale jsem zjistil ze je lepsi davat prednost velkym prvkum. Ani jedno z techto omezeni vsak vyrazne neovlivnilo algoritmus, teprve pridani posledniho parametru, a to exponentu granularity se ukazalo ze pro vetsi exponent (zhruba od 1.5) dojde k vyraznemu zhorseni vlastnosti algoritmu. Testoval jsem pro instance delky 100 (na instancich delky 40 je tato zmena sice videt, ale jen velice nepatrne). Pri prohlednuti vygenerovanych instanci jsem shledal ze vetsina jejich pomeru cena/vaha je vetsi nez 1, cimz potvrdily defacto moji puvodni myslenku. V nejtezsich pripadech se mi dokonce stavalo ze se vypocet automaticky prerusil (vypocet se automaticky prerusoval pro vice nez 2000000 stavu), proto data v grafu nejsou uplne presna. Zkousel jsem vsak namatkove nektere tyto instance dopocitat (zkousel jsem jen 15 instanci z casovych duvodu) a vzdy jsem nalezl optimalni reseni do 20 000 000 stavu, coz pri delce instance 100 povazuji za velice dobry vysledek.
Zajimave ovsem je, ze spatna testovaci data byla pouze v pripade ze granularita, pomer veci i exponent byly nastaveny na nejhorsi hodnoty, jakmile byla jedna z techto tri velicin nastavena do nahodnych hodnot, algoritmus se jiz choval mnohem lepe, jak take demonstruji v nasledujici kapitole:
Po velice dobrych vysledcich z predchoziho clanku jsem se rozhodl zkusit jak vhodny je testovany algoritmus na nahodna prumerna data. Zde jsem pouzil 50 prumernych instanci (tedy takove instance, kde byly parametry nahodne generovany) ve velikostech od 10 do 2000. Dynamicke programovani skoncilo jak uz jsem vyse napsal zhruba na hranici delky instance 1000. Naopak me velice prekvapilo ze metoda vetvi a hranic se obstojne drzela i na instancich velikosti 2000, kde vypocet jedne instance trval v prumeru 5.26 vteriny.
Zkusil jsem proto tento algoritmus jeste trosku vylepsit, a to tak ze jsem jeste omezil funkci horniho odhadu, zde jsem nebral v potaz predmety ktere maji vahu vetsi nez zbyvajici vaha v batohu a prioritni frontu uzlu ke zpracovani jsem nahradil obycejnou frontou, protoze se ukazalo ze rezie vkladani do prioritni fronty je mnohem narocnejsi nez projiti o malo vice stavu ale bez prioritni fronty (je ale dulezite zminit ze vkladani bylo reseno v liearnim case, tedy ne idealne). Tento vylepseny algoritmus dosahoval znatelne lepsich vysledku, konkretne pro instance velikosti 2000 jsem vysledek spocital za 3.5 vteriny. Zkusil jsem proto tento algoritmus pro instance az do velikosti 5000. Tato data jiz nemohou byt brana 100% spravne, protoze jsem od kazde delky testoval pouze 5 instanci, presto si myslim ze i jen fakt ze se mi podarilo spocitat instanci o velikosti 5000 v case kolem 30ti sekund povazuji za dobry.
zdrojovy kodVzhledem k velkemu objemu a male informacni hodnote namerenych tabulek je neuvadim primo v tomto reportum, mohou vsak byt zobrazeny zvlast v prilozenych HTML souborech.
zdrojovy kod cele ulohy