Problémy a algoritmy
Řešení problému batohu
(3. úloha)

Zadání

• Naprogramujte řešení 0/1 problému batohu metodou větví a hranic tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria.
• Naprogramujte řešení 0/1 problému batohu nebo alespoň 0/1 exaktního problému batohu bez cen metodou dynamického programování.
• Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/hmotnost s testem nejtěžší věci.

Popis algoritmů

Metoda větví a hranic
Jak je již z názvu patrné, tato metoda se snaží "ořezat" neperspektivní větve stromu řešení a tím zlepšit exponenciální složitost algoritmu. Snahou je samozřejme větve ořezat co nejvíce větví a co nejblíže kmeni, ale samozřejmě neuříznout větev se správným řešením. Protože můj jednodušší algoritmus neměl pro větší počet věcí dobré výsledky, vytvořil jsem nakonec algoritmy dva.

První algoritmus je založena na testu, zda je v prozkoumávané větvi možno dosáhnout celkové ceny lepší, než je dosavadní maximum (přidáním všech věcí dané větve). Algoritmus lze rozdělit na dvě části:
V části přípravné jsou věci seřazeny (je použito řazení dle poměru cena/váha, které se prokázalo jako nejvýhodnější, ale je samozřejmě možno použít řazení dle jiného kritéria) a poté je pro seřazené věci vytvořeno pole "cen větví" - posledním prvek je cena poslední věci, předposlední poslední + předposlední věc,..., které je pak používáno v při rozhodování.
Druhá část je standardní průchod stavovým prostorem (řešení hrubou silou) doplněné o ořezávací podmínku - pro pokračování v prozkoumávání větve je nutno, aby cena větve (uložená v pomocném poli) sečtená s aktuální cenou věcí v batohu byla větší než dosud dosažené maximum.

Algoritmus druhý je mírnou modifikací prvního. K odhadu ceny větve se nevyužívá součet cen všech zbývajících věcí ve větvy, ale pouze těch, které se do batohu "opravdu vejdou". Samozřejmě není možné přidat pouze věci, které se skutečně vejdou (to by byla heuristika cena/váha), ale řešení je jednoduché - věc, která se do batohu nevejde celá, je přidána z poměrné části. Základní podmínkou však nadále zůstává počáteční seřazení věcí, u této metody nutně podle poměru cena/váha.
Pro zmenšení počtu výpočtů odhadu ceny větve je tato hodnota předávána při rekurzivním řešení. Odhad je totiž nutné přepočíst pouze pro ty větve, kdy věc není přidána - odhad počítá s postupným přidáním všech věcí, které se do batohu vejdou.
Dle mého názoru je hodnotící funkce tohoto algoritmu (tedy odhad ceny větve) nejlepší možnou - v lineárním čase najde relativně velmi přesný odhad ceny. Celý algoritmus pak strom řešení až neočekávaně dobře prořeže.

Složitost těchto algoritmů je však bohužel stále exponenciální, velmi záleží na parametrech jednotlivých instancí, tedy na tom, jak dobře se nám povede stavový prostor prořezat.

Dynamické programování
Tato metoda je založena na zapamatovávání si dílčích výsledků již vyřešených podproblémů, které tedy není nutno počítat znovu. Z toho jsou patrné dvě základní "vlastnosti" metody - má podstatně vyšší paměťovou náročnost a je ji možbo použít pouze na problémy, které jsme schopni rozložit na dílčí podproblémy.

Můj algoritmus vychází z násedujícího rozkladu: dílčím problémem je problém P(n, weight), který řeší problém batohu pro prvních n věcí, přičemž aktuální kapacita batohu je weight, a vrací cenu zvoleného optimálního řešení podproblému. Řešením je potom řešení dílčího problému P s celkovým počtem věcí (count) a celkovou nosností batohu (capacity). Pro zapamatování výsledků je tedy nutno alokovat pole o velikosti (count + 1) * (capacity + 1).
Řešení dílčího podproblému přitom zjistíme jednoduše - zkusíme vyřešit problém s přidáním a s nepřidáním n-té věci a zvolíme lepší řešení. Srovnáváme tedy ceny P(n-1, weight) (bez n-té) a P(n-1, weight-weights[n(-1)])+prices[n(-1)] (s n-tou) a zvolíme výhodnější řešení.

Metodu je obecně možno řešit buď zdola - postupně počítáme všechny hodnoty pole, přičemž poslední prvek je výsledek, nebo shora - začneme od výsledné pozice a dopočítáváme pouze ty hodnoty, které pro výpočet opravdu potřebujeme. Druhá metoda se zdá jednoznačně méně náročná, ale je nutno si uvědomit, že před zahájením výpočtu je pro tuto metodu nutno vyplnit celé pole "undefined" hodnotou, což zabere nějaký čas a zvýší (teoretickou) složitost výpočtu (samotný výpočet je samozřejmě o něco časově náročnější, ale ne o mnoho). V mém algoritmu byl zvolen postup shora.

Dalším drobným problémem metody je zjištění skutečně přítomných věcí v batohu, protože teprve po vyřešení obou možností dílčích podproblémů je vybrána výhodnější větev. Tento problém jsem vyřešil "kódováním" výběru podvětve - pokud byla při řešení podproblému zvolena větev s přidáním n-té věci, je výsledek podproblému do pole uložen s kladným znaménkem, jinak se záporným. Po skončení výpočtu je poté přítomnost jednotlivých věcí zrekonstruována průchodem pole (opět od posledního prvku) právě podle znamének výsledku, které jednoznačně určí další prvek pole, který tvoří optimální řešení.

Velkou výhodou metody je její výpočetní složitost - O(count*capacity), která je v podstatě lineární s počtem věcí, i když lze spíše očekávat kvadratickou závislost, protože pro většinu instancí je kapacita batohu funkcí (většinou lineární) počtu věcí.

Heuristika cena/hmotnost + nejtěžší věc
Tato metoda je založena na již uvedené heuristice dle poměru cena/hmotnost, která seřadí věci dle tohoto kritéria a poté přidá postupně všechny věci, které se do batohu vejdou. Modifikace spočívá v tom, že po vyřešení pomocí této heuristiky se otestuje, zda by nebylo vhodnější do batohu zabalit pouze nejtěžší věc. Pokud ano, batoh se "vysype" a je zabalena pouze tato věc.

Předností této jednoduché modifikace je zaručení dosažení minimálně 50% optimálního řešení za přijatelnou cenu.

K dispozici jsou celkové zdrojové kódy pro řešení problému batohu (všechny algoritmy + pomocné funkce pro čtení a ukládání dat) a samotné algoritmy (všechny, včetně první úlohy), vyjmuté z tohoto souboru pro snazší orientaci. Kód byl bez problémů kompilován v MS Visual C++ 6.

Výsledky měření

Uvažované metody
Rozhodl jsem se v této úloze nesrovnávat pouze nové metody, ale i metody vytvořené v rámci první úlohy. Pro zmenšení velikosti tabulek jsem zvolil pro metody "kódová jména". V následující tabulce naleznete jejich přiřazení k jednotlivým metodám.
Pro vyhodnocování metod se vedle času běhu algoritmu, který není vždy přesný a může být ovlivněn vnějšími vlivy, používá též počet kroků (, na který algoritmus nalezl požadované řešení. Do počtu kroků nezahrnuji vždy všechny operace (např řazení věcí, ...) a proto jsem se rozhodl v tabulce též uvést, jaké kroky se u té které metody počítají.

Srovnání časové a výpočetní složitosti
Následující tabulka ukazuje srovnání časové složitosti všech mnou vytvořených algoritmů pro řešení problému batohu, včetně algoritmů z první úlohy. Hodnoty jsou průměry z měření 50-ti instancí pro každý počet věcí - zkušebních dat zadaných s úlohou. Pro větší přehlednost jsem též hodnoty z tabulky vynesl do grafů, které naleznete pod tabulkou.

Z naměřených dat je jasně patrná exponenciální složitost hotší metody větví a hranic a též její závislost na konkrétních instancích, která se projevila poklesem složitosti u instancí pro 15 a 37 věcí.
Velkým překvapením je malá složitost "ideálního" algoritmu pro metodu větví a hranic. Exponenciální závislost není z průběhu jasně patrná, ale domnívám se, že pro velký počet se exponenciální složitost projevovat začne. Podrobnější rozbory budou součástí čtvrté úlohy.

Též byla ověřena kvadratická složitost metody dynamického programování - s rostoucím počtem věcí kapacita batohu u testovacích instancí roste.

Shodnost průměrných hodnot obou heuristických metod je pochopitelná, test nejtěžší věci se samozřejmě uplatní jen u několika instancí, ale je nutno podotknout, že metoda s testem nejtěžší věci opravdu snížila velikost chyby pod 50%. Změna chyby se však na testovaných instancích výrazněji projevila jen u instancí s čtyřmi věcmi, proto zde nebudu uvádět srovnání chyby, které bude součástí čtvrté úlohy.

Závěr

Všechny vytvořené metody jsou plně funkční a připraveny pro testování ve čtvrté úloze. Velkým překvapením byla velmi malá složitost "ideálního" algoritmu metody větví a hranic, který má značne lepší výsledky než dynamické programování. Je však třeba podotknout, že problém batohu pro 40 instancí není zdaleka tak rozsáhlým problémem.

Teoretické předpoklady u všech metod byly potvrzeny. Podrobnější rozbor výsledků naleznete v předchozí části, další rozbory jsou součástí čtvrté úlohy.

Soubory:
    batoh.cpp         ... zdrojové kódy pro řešení problému batohu
    algoritmy.txt   ... zdrojové kódy metod (výběr z předchozího souboru)