PAA 2007-2008, Petr Maj (majp1)
1) 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é)
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:
Popis implementovaných metodúplné zadání úlohy
Srovnání výpočetních časů hrubé síly, B&B a dynamického programování (grafy vítány)
Srovnání vylepšené heuristiky s původní
Zhodnocení naměřených výsledků
Omezeny greedy algoritmus je takovy algoritmus ktery nejprve udela greedy podle cena/vaha a potom zjisti jestli reseni ktere mu vyslo je horsi nez greedy reseni kde ale nejcennejsi prvek je vlozen. Algoritmus vrati to lepsi reseni. Tim je dosazeno omezeni maximalni chyby shora jak je popsano na strankach PAA.
zdrojovy kodGrafy zachycuji pouze minimalni a prumernou presnost, maximalni presnost obou metod byla na testovanych instancich vzdy 1.
| 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 | 50 | 0.1 | 0.0 | 0.007 | 8 | 8 | 8.0 | 1.0 | 0.814249363868 | 0.995487519849 |
| 10 | 50 | 0.1 | 0.01 | 0.0234 | 20 | 20 | 20.0 | 1.0 | 0.925612052731 | 0.992984718616 |
| 15 | 50 | 0.1 | 0.01 | 0.0308 | 30 | 30 | 30.0 | 1.0 | 0.972251867663 | 0.996949624548 |
| 20 | 50 | 0.1 | 0.02 | 0.0392 | 40 | 40 | 40.0 | 1.0 | 0.959207014868 | 0.995685890793 |
| 22 | 50 | 0.1 | 0.02 | 0.0486 | 44 | 44 | 44.0 | 1.0 | 0.969822708412 | 0.994578847602 |
| 25 | 50 | 0.1 | 0.02 | 0.0482 | 50 | 50 | 50.0 | 1.0 | 0.974123255022 | 0.995752230453 |
| 27 | 50 | 0.1 | 0.02 | 0.0582 | 54 | 54 | 54.0 | 1.0 | 0.981548699335 | 0.997103843617 |
| 30 | 50 | 0.1 | 0.03 | 0.0496 | 60 | 60 | 60.0 | 1.0 | 0.982508882208 | 0.996028289989 |
| 32 | 50 | 0.1 | 0.03 | 0.0518 | 64 | 64 | 64.0 | 1.0 | 0.97721822542 | 0.99725623269 |
| 35 | 50 | 0.1 | 0.03 | 0.0636 | 70 | 70 | 70.0 | 1.0 | 0.981827758757 | 0.998119989732 |
| 37 | 50 | 0.1 | 0.03 | 0.0602 | 74 | 74 | 74.0 | 1.0 | 0.988240324995 | 0.998203258002 |
| 40 | 50 | 0.1 | 0.03 | 0.0676 | 80 | 80 | 80.0 | 1.0 | 0.990542763158 | 0.998472577807 |
Dynamicke programovani je rychlou metdou jak spocitat presne optimalni vysledek probelmu batohu. Tento algoritmus je ovsem pseudopolynomialni v zavislosti na c, tedy kapacite batohu, protoze pro vypocet optima je nutne spocitat c*n hodnot. Algoritmus dynamickeho programovani zalozen na principu optimality je velice jednoduchy a je uveden na strankach predmetu PAA.
zdrojovy kod| 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 | 50 | 0.2 | 0.1 | 0.132 | 400 | 400 | 400.0 | 1.0 | 1.0 | 1.0 |
| 10 | 50 | 0.4 | 0.2 | 0.306 | 1000 | 1000 | 1000.0 | 1.0 | 1.0 | 1.0 |
| 15 | 50 | 1.0 | 0.8 | 0.898 | 3000 | 3000 | 3000.0 | 1.0 | 1.0 | 1.0 |
| 20 | 50 | 1.6 | 1.3 | 1.448 | 5000 | 5000 | 5000.0 | 1.0 | 1.0 | 1.0 |
| 22 | 50 | 1.7 | 1.5 | 1.598 | 5500 | 5500 | 5500.0 | 1.0 | 1.0 | 1.0 |
| 25 | 50 | 2.3 | 2.1 | 2.18 | 7500 | 7500 | 7500.0 | 1.0 | 1.0 | 1.0 |
| 27 | 50 | 2.8 | 2.7 | 2.752 | 9450 | 9450 | 9450.0 | 1.0 | 1.0 | 1.0 |
| 30 | 50 | 3.6 | 3.4 | 3.498 | 12000 | 12000 | 12000.0 | 1.0 | 1.0 | 1.0 |
| 32 | 50 | 4.4 | 4.1 | 4.224 | 14400 | 14400 | 14400.0 | 1.0 | 1.0 | 1.0 |
| 35 | 50 | 5.3 | 5.0 | 5.146 | 17500 | 17500 | 17500.0 | 1.0 | 1.0 | 1.0 |
| 37 | 50 | 6.2 | 5.9 | 6.022 | 20350 | 20350 | 20350.0 | 1.0 | 1.0 | 1.0 |
| 40 | 50 | 7.3 | 6.8 | 7.08 | 24000 | 24000 | 24000.0 | 1.0 | 1.0 | 1.0 |
Rekl jsem si ze zkusim udelat i dynamicke programovani ktere nepocita celou tabulku, ale jen ty hodnoty ktere potrebuje (samozrejme tyto hodnoty pak v tabulce zustanou a mohou byt znovu pouzity). Protoze jsem na prvni pohled myslel ze tento pristup bude jednoduzsi, nazval jsem tuto metodu rychle dynamicke programovani, coz bylo chybne jak vyplyva z grafu.
zdrojovy kodJeho interpretace je velice jednoducha, je videt ze pocet pocitanych stavu je opravdu mensi nez u normalniho dynamickeho programovani, po case ale rekurzivni reseni "rychleho" algoritmu zacne nabirat na vaze (volani funkci jsou v jazyce Python velice narocna). Moznosti by bylo predelat rekurzi na zasobnik, pripadne pouziti tohoto algoritmu na jiny problem resitelny dynamickym programovanim, kde vypocetni doba potrebna pro vypocteni hodnoty jedne bunky by byla vyssi nez rezie volani funkce.
| 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 | 50 | 0.1 | 0.05 | 0.0734 | 15 | 10 | 12.0 | 1.0 | 1.0 | 1.0 |
| 10 | 50 | 0.3 | 0.0999999999999 | 0.21 | 400 | 55 | 332.0 | 1.0 | 1.0 | 1.0 |
| 15 | 50 | 0.9 | 0.3 | 0.748 | 1516 | 120 | 1318.0 | 1.0 | 1.0 | 1.0 |
| 20 | 50 | 1.6 | 0.4 | 1.442 | 2996 | 210 | 2764.0 | 1.0 | 1.0 | 1.0 |
| 22 | 50 | 1.8 | 0.4 | 1.658 | 3492 | 253 | 3253.0 | 1.0 | 1.0 | 1.0 |
| 25 | 50 | 2.5 | 0.6 | 2.31 | 4915 | 325 | 4526.0 | 1.0 | 1.0 | 1.0 |
| 27 | 50 | 3.2 | 0.6 | 2.932 | 6263 | 378 | 5783.0 | 1.0 | 1.0 | 1.0 |
| 30 | 50 | 4.0 | 0.9 | 3.786 | 8086 | 465 | 7507.0 | 1.0 | 1.0 | 1.0 |
| 32 | 50 | 5.0 | 1.0 | 4.572 | 9613 | 528 | 9058.0 | 1.0 | 1.0 | 1.0 |
| 35 | 50 | 5.9 | 1.2 | 5.626 | 11891 | 630 | 11217.0 | 1.0 | 1.0 | 1.0 |
| 37 | 50 | 7.2 | 1.3 | 6.582 | 13869 | 703 | 13071.0 | 1.0 | 1.0 | 1.0 |
| 40 | 50 | 8.3 | 1.7 | 7.866 | 16853 | 820 | 15821.0 | 1.0 | 1.0 | 1.0 |
Kdyz jsem premyslel jak co nejlepe udelat metodu Branch & bound, napadlo me ze protoze jeji sila spociva v tom ze orezava vetve ktere jiz nemohou zlepsit nejlepsi dosazeny vysledek, cim lepsi vysledek budeme drive znat, tim silneji budeme moci orezavat. Proto jsem se rozhodl pro prohledavani spise do hloubky (toho je dosazeno razenim v prioritni fronte), takze vlastne najdeme prvnim pruchodem reseni a toto pak jiz jen vylepsujeme.
Dal jsem si rekl ze protoze greedy algoritmus v predchozi uloze daval relativne velice male odchylky od optima a protoze je velice rychly, predradil jsem ho B&B algoritmu a vypocital si pomoci nej vysledek pomoci ktereho jsem mohl jiz od zacatku odrezavat.
Jako odhad maximalni cenu uzlu jsem pro tento algoritmus pouzil nasledujici vzorec:
Tedy ze odhad maximalni ceny reseni kde znam vanu i cenu az pro i-1 prvek (je dulezite si uvedomit ze prvky jsou jiz od greedy algoritmu serazeny sestupne podle pomeru cena/vaha) je tato jeho cena + cena toho ze zbyvajici kapacitu batohu vyplnime hypotetickym prvkem s pomerem cena/vaha jako momentalni nejlepsi volny. To ze tento odhad je pripustny je trivialni dukaz. zdrojovy kod
| 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 | 5 | 0.01 | 0.00999999999999 | 0.01 | 8 | 4 | 5.0 | 1.0 | 1.0 | 1.0 |
| 10 | 5 | 0.1 | 0.04 | 0.072 | 80 | 27 | 55.0 | 1.0 | 1.0 | 1.0 |
| 15 | 5 | 2.0 | 0.31 | 1.17 | 1778 | 238 | 905.0 | 1.0 | 1.0 | 1.0 |
| 20 | 5 | 10.0 | 1.0 | 5.0 | 7024 | 867 | 3526.0 | 1.0 | 1.0 | 1.0 |
| 22 | 5 | 11.0 | 0.999999999999 | 5.0 | 7676 | 1156 | 3526.0 | 1.0 | 1.0 | 1.0 |
| 25 | 5 | 14.0 | 8.0 | 10.6 | 10124 | 6200 | 7604.0 | 1.0 | 1.0 | 1.0 |
| 27 | 5 | 43.0 | 9.0 | 24.6 | 29598 | 6220 | 17049.0 | 1.0 | 1.0 | 1.0 |
| 30 | 5 | 49.0 | 9.0 | 30.8 | 33700 | 6777 | 21407.0 | 1.0 | 1.0 | 1.0 |
| 32 | 5 | 82.0 | 43.0 | 64.0 | 55582 | 29925 | 43495.0 | 1.0 | 1.0 | 1.0 |
| 35 | 5 | 409.0 | 93.0 | 252.2 | 264069 | 62423 | 163541.0 | 1.0 | 1.0 | 1.0 |
| 37 | 5 | 2136.0 | 268.0 | 1103.4 | 1317354 | 177015 | 682635.0 | 1.0 | 1.0 | 1.0 |
| 40 | 5 | 6303.0 | 343.0 | 2155.6 | 3763041 | 226752 | 1311968.0 | 1.0 | 1.0 | 1.0 |
Tento algoritmus mi ale prisel stale jako velice pomaly, zejmena proto ze ohodnocovaci funkce silne nadhodnocovala slibnost stavu. Je to proto ze nepocita s tim ze mame jen omezene mnozstvi prvku ikterym ji vypocitavame. Udelal jsem proto novou ohodnocovaci funkci, ktera toto bere v potaz a kazdy prvek pridava maximalne jen v takovem mnozstvi v jakem je dostupny a pak prejde na dalsi (mene vyhodny) prvek az do vycerpani kapacity.
Tato funkce je stale pripustna, nebot rozdelenim posledniho prvku na ktery je jeste v batohu k dispozici nenulova vaha docilime horniho odhadu, protoze i v pripade ze bychom dal v batohu nasli prvky ktere by bez puleni daly dohromady zbyvajici vahu, soucet jejich cen by nikdy nebyl tak velky jako zlomek prvku ktery jsme pridali:
Dalsim vylepsenim bylo zkvalitneni pocatecniho reseni. Toho jsem dosahl pouzitim dvou greedy algoritmu, jeden podle pomeru cena/vaha, druhy podle ceny a vybrani toho lepsiho. Takto upraveny algoritmus jiz obstojne fungoval na vsech testovacich datech. Posledni vyznamne vylepseni jeho rychlosti pak bylo uvedomit si vsechny instance jsou v celych cislech. tedy mame-li nejlepsi zname reseni o cene n, nema cenu expandovat uzly ktere maji dolni celou cast ohodnoceni stejne velikou nebo nizsi nez dosud zname reseni.
Temito vylepsenimi jsem algoritmus srazil na vysokou rychlost (dokonce je rychlejsi nez dynamicke programovani), cenou za tuto vykonnost je omezeni pouziti na celociselne instance ktere obsahuji pouze predmety ktere lze do batohu vlozit. Druhe kriterium je trivialne odstranitelne, prvni muzeme zmenit bud vynasobenim vsechn cen a vah tak aby byly celocielne, nebo vypocitanim minimalne cenove odchylky 2 reseni a pocitat pak s ni, neni vsak problem vymyslet si instanci kde toto pujde velice tezko.
Na druhe strane by vsak vysledna vykonnost algoritmu sla zlepsit na mnoha mistech. Nejmarkatnejsi je vkladani uzlu do prioritni fronty coz algoritmus dela naivne se slozitosti n, samozrejme je mozne to udelat se slozitosti log n. Vzhledem k tomu ze implementacnim jazykem je Python, dalsiho vyznamneho zlepseni by se dalo dosahnout rozbalenim volani funkci (volani funkci je v Pythonu obecne velice drahe), globalnich promennych a lambda funkci (samozrejme pro velke a tezko orezavatelne instance jsou tyto upravy zcela zanedbatelne a proto jsem je ani neimplementoval).
zdrojovy kod| 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 | 50 | 0.1 | 0.01 | 0.0242 | 17 | 9 | 12.0 | 1.0 | 1.0 | 1.0 |
| 10 | 50 | 0.1 | 0.02 | 0.062 | 85 | 21 | 34.0 | 1.0 | 1.0 | 1.0 |
| 15 | 50 | 0.2 | 0.03 | 0.0914 | 84 | 31 | 46.0 | 1.0 | 1.0 | 1.0 |
| 20 | 50 | 0.4 | 0.05 | 0.151 | 159 | 41 | 76.0 | 1.0 | 1.0 | 1.0 |
| 22 | 50 | 0.3 | 0.04 | 0.1488 | 137 | 45 | 77.0 | 1.0 | 1.0 | 1.0 |
| 25 | 50 | 0.6 | 0.05 | 0.203 | 268 | 51 | 98.0 | 1.0 | 1.0 | 1.0 |
| 27 | 50 | 0.5 | 0.05 | 0.213 | 237 | 55 | 98.0 | 1.0 | 1.0 | 1.0 |
| 30 | 50 | 1.1 | 0.1 | 0.304 | 485 | 61 | 133.0 | 1.0 | 1.0 | 1.0 |
| 32 | 50 | 1.0 | 0.1 | 0.31 | 474 | 65 | 132.0 | 1.0 | 1.0 | 1.0 |
| 35 | 50 | 1.0 | 0.1 | 0.304 | 331 | 71 | 129.0 | 1.0 | 1.0 | 1.0 |
| 37 | 50 | 0.7 | 0.07 | 0.3294 | 234 | 75 | 135.0 | 1.0 | 1.0 | 1.0 |
| 40 | 50 | 0.9 | 0.1 | 0.374 | 366 | 81 | 151.0 | 1.0 | 1.0 | 1.0 |
Z grafu tohoto algoritmu (specielne z maximalniho casu a poctu navstivenych stavu) vyplyva ze tento algoritmus je jiz mnohem citlivejsi na to jak dana instance vypada, presto vsak i nejhorsi vysledky pro dany soubor jsou prakticky nepomerne s predchozi verzi. V grafech je pocet stavu roven vzdy poctu expandovanych stavu + 2*n za pocatecni greedy algoritmy.
Na nasledujicich grafech je videt srovnani casu vsech porovnavanych algoritmu. Nejhure z nej vysel primitivni branch & bound ktery vykazoval exponencialni zavislost na datech, i kdyz posunul vypocitatelnost o hodne dal (s BFS jsem nebyl schopen resit v rozumnem case ani instance velikosti 20, B&B vypocita 40). Prekvapeni se nekonalo u dynamickeho programovani, ktere vykazovalo ocekavanou zavislost na vypocetnim case, ani u greedy algoritmu ktery byl vylozene linearni.
Co me ale zarazilo byla obrovska rychlost fast B&B algoritmu, ktery bych rychlosti rustu na testovanych datech prirovnal rozhodne spise ke greedy algoritmu nez k dynamickemu programovani, ktere jsem naopak cekal ze ho casem ve vykonnosti predstihne. Dlouho jsem overoval ze pouzite kriterium je opravdu pripustne a ze nemam nikde v kodu chybu, ale na zadny problem jsem neprisel.
Myslim ze tak vyznamna vykonnost algoritmu je zapricinena nalezenim relativne velice kvalitniho reseni na pocatku algoritmu a proto je mozne okamzite silne orezavat (diky diskretnosti problemu viz vyse). Kdyz jsem jakoukoli z techto podminek odstranil, algoritmus na nekterych instancich zacal okamzite vyznamne ztracet na vykonnosti. Patrne je tedy pouze velice dobre vyladen na testovaci data a bude existovat takovy typ instanci, kde bude jeji reseni provedeno v mnohem horsim case. Na dodanych testovacich datech, vsak algoritmus pracuje vyborne.
zdrojovy kod celeho courseworku
