Problem plecakowy - porównanie algorytmów rozwiązujących binarne zagadnienie plecakowe cd.

2. ALGORYTMY ROZWIÄ„ZUJÄ„CE PROBLEM

2.1. ALGORYTM WYKORZYSTUJÄ„CY SORTOWANIE

Ten sposób rozwiÄ…zania decyzyjnej wersji problemu plecakowego polega na uÅ‚ożeniu przedmiotów wedÅ‚ug malejÄ…cego współczynnika zysk/objÄ™tość i wkÅ‚adaniu ich kolejno do plecaka aż do jego zapeÅ‚nienia. Zaczynamy zatem od przedmiotów „najcenniejszych” – one na pewno znajdÄ… siÄ™ w plecaku. Może siÄ™ jednak zdarzyć tak, że bardzo duży przedmiot nie zmieÅ›ci siÄ™ do plecaka mimo, iż nastÄ™pne w kolejnoÅ›ci weszÅ‚yby bez problemów. Algorytm koÅ„czy wówczas swoje dziaÅ‚anie i rozwiÄ…zanie może być dalekie od optymalnego. Do sortowania wykorzystujemy funkcjÄ™ qsort, która jest uważana za najszybszy algorytm sortowania [3]. ZaletÄ… tego algorytmu jest jego prostota oraz Å‚atwość implementacji.

Na Rys.1 przedstawiony jest schemat blokowy działania tego algorytmu.

2.2. ALGORYTM OPARTY NA PROGRAMOWANIU DYNAMICZNYM

Programowanie dynamiczne jest ulepszeniem metody „dziel i zwyciężaj, która polega na podzieleniu problemu na kilka mniejszych, dajÄ…cych siÄ™ rozwiÄ…zać mniejszym kosztem, a nastÄ™pnie „zÅ‚ożeniu” z nich rozwiÄ…zania [1]. Jednak jeżeli dzielimy zadanie wielkoÅ›ci n na podzadania wielkoÅ›ci n-1, to tych podzadaÅ„ bÄ™dzie n – algorytm rekurencyjny wzrasta wykÅ‚adniczo [2]. ZÅ‚ożoność wykÅ‚adnicza bierze siÄ™ stÄ…d, że problemy, których liczba roÅ›nie wielomianowo, sÄ… obliczane wielokrotnie [1]. Algorytmy „dziel i zwyciężaj” dajÄ… czÄ™sto efektywne rozwiÄ…zania zadaÅ„, szczególnie gdy podzadania sÄ… mniejszymi wersjami zadania wyjÅ›ciowego [2].

Idea programowania dynamicznego polega na tym, że zadanie

Idea programowania dynamicznego polega na tym, że zadanie optymalizacji z n zmiennymi rozkÅ‚adamy na n zadaÅ„ z 1 zmiennÄ…, poszukujÄ…c dla takich zadaÅ„ minimum lub maksimum jednej zmiennej [4]. Korzystamy tu z zasady optymalnoÅ›ci Bellmana – optymalne rozwiÄ…zanie dla k-tego etapu jest również optymalne dla etapów k+1, k+2, ..., n. Jeżeli pierwszy etap oznacza caÅ‚y problem, to zaczynamy od n-tego (najprostszego) [5]. Wykorzystujemy również tzw. wÅ‚asność Markowa: wartość funkcji celu w zadaniach n-etapowych jest sumÄ… wartoÅ›ci uzyskanych w poszczególnych etapach, a wartość uzyskana w j-tym etapie zależy od stanu w etapie poprzednim oraz od decyzji podjÄ™tej w j-tym etapie; nie zależy ona natomiast od tego, jakÄ… drogÄ… doszliÅ›my do stanu j-1 [4]. DziÄ™ki temu, że rozwiÄ…zania mniejszych podzadaÅ„ sÄ… zapamiÄ™tywane, a nastÄ™pnie tylko odczytywane i wykorzystywane do rozwiÄ…zania wiÄ™kszych (a nie, jak w metodzie „dziel i zwyciężaj”, wiÄ™ksze liczone od nowa), zÅ‚ożoność jest wielomianowa. [1].


W naszym przypadku nie potrafimy zawczasu przewidzieć, z których rozwiązań mniejszych podproblemów będziemy korzystać w następnych krokach i dlatego, przygotowując się na każdą ewentualność, rozwiązujemy wszystkie mniejsze problemy. Odpowiadają one mniejszej liczbie rodzajów rzeczy, które pakujemy do plecaka oraz jego mniejszej pojemności. Rozwiązania wszystkich podproblemów umieszczamy w tablicy F, której wiersze odpowiadają kolejnym przedmiotom, czyli są ponumerowane liczbami od 1 do n, a kolumny są kolejnymi pojemnościami plecaka, od 1 aż do maksymalnej dopuszczalnej (b). Każdy element fi,j tej tablicy to maksymalna wartość wypełnienia plecaka o pojemności j (j przebiega od 1 do b), gdy mamy do dyspozycji przedmioty o numerach od 1 do i (i przebiega od 1 do n). Tworzymy również tablicę X o takich samych wymiarach, w której element xi,j określa, czy rzecz o numerze i bierze udział w rozwiązaniu odpowiadającym temu polu, a którego wartość jest zapisana w tablicy F jako fi,j. Na Rys.2 przedstawiony jest schemat blokowy działania tego algorytmu.