Zad�n�
- 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.
- Pokud mo�no, prezentujte algoritmy jako body v plo�e, jej� sou�adnice jsou v��e uveden� krit�ria.
Postup experimentu
Nejprve jsem sjednotil �lohy Batoh 1 a Batoh 2 do jedin�ho projektu. P�idal jsem druh� v�stup do kter�ho se ukl�daj� pr�m�rn� hodnoty po�tu operac� v p��pad� exaktn�ch metod a relativn�ch chyb v p��pad� heuristik.
Pro generov�n� instanc� jsem pou�il Webov� gener�tor instanc� probl�mu batohu (stránka již neexistuje). V p�ede�l�ch �loh�ch jsme porovn�vali v�po�etn� n�ro�nost algoritm� v z�vislosti na velikosti instance. Proto jsem se soust�edil na z�sk�n� z�vislosti v�po�etn� n�ro�nosti a chyby v z�vislosti na pom�rn� kapacit� batohu a granularit� vkl�dan�ch v�c�. Pro experimenty jsem pou�il toto nastaven� (pokud nen� uvedeno jinak):
Velikost instance: 20, Po�et instanc�: 50, Maxim�ln� v�ha v�ci: 100, Maxim�ln� cena v�ci: 250
Nam��en� hodnoty a v�sledky
V tabulce a grafech jsou zobrazeny pr�m�rn� hodnoty.
Tabulka: Z�vislost v�po�etn� n�ro�nosti na kapacit� batohu (pro velikost instance = 15)
| pom�r sum�rn� v�hy ke kapacit� batohu / algoritmus | BF | B&B | Dynamick� prog. | GP |
|---|---|---|---|---|
| 0,1 | 345,5 | 304,2 | 1137 | 15 |
| 0,2 | 1817,4 | 1131,3 | 2238 | 15 |
| 0,3 | 5932,9 | 2566,1 | 3606 | 15 |
| 0,4 | 14287,2 | 3322,5 | 4387,5 | 15 |
| 0,5 | 21961,7 | 3187,8 | 5793 | 15 |
| 0,6 | 28282,3 | 2664,5 | 7099,5 | 15 |
| 0,7 | 31672,4 | 1178,9 | 8038,5 | 15 |
| 0,8 | 32642,6 | 539,7 | 9402 | 15 |
| 0,9 | 32760,5 | 285,5 | 10243,5 | 15 |
Dle m�ho n�zoru nem� praktick� v�znam zde uv�d�t ve�ker� nam��en� hodnoty. Daleko lep�� vypov�daj�c� hodnotu maj� grafy, kter� n�sleduj�.
Za zm�nku pouze stoj� porovn�n� v�po�etn� slo�itosti Hrub� s�ly (BF) s ostatn�mi algoritmy.
Graf 1: Z�vislost v�po�etn� n�ro�nosti na kapacit� batohu (pro velikost instance = 15)
Nastaven� gener�toru: Velikost instance: 15, Po�et instanc�: 10, Maxim�ln� v�ha v�ci: 100, Maxim�ln� cena v�ci: 100
Graf 2: Z�vislost v�po�etn� n�ro�nosti na kapacit� batohu (pro velikost instance = 20)
Graf 3: Z�vislost v�po�etn� n�ro�nosti na granulrit� instance (p�evaha mal�ch v�c�)
Charakter granularity nastaven na "V�ce mal�ch v�c�".
Graf 4: Z�vislost v�po�etn� n�ro�nosti na granulrit� instance (p�evaha velk�ch v�c�)
Charakter granularity nastaven na "V�ce velk�ch v�c�".
Graf 5: Z�vislost relativn� chyby na kapacit� batohu (pro velikost instance = 15)
Velikost instance: 15, Po�et instanc�: 10, Maxim�ln� v�ha v�ci: 100, Maxim�ln� cena v�ci: 100
Graf 6: Z�vislost relativn� chyby na kapacit� batohu (pro velikost instance = 20)
Graf 7: Z�vislost relativn� chyby na granularit� instance
Z�v�r
Z grafu 1 a 2 je dob�e patrn�, �e algoritmus v�tv� a hranic (B&B) dosahuje nejhor�� v�po�etn� n�ro�nosti pokud je pom�r sum�rn� v�hy ke kapacit� batohu roven 0,3 a� 0,5.
D�le je patrn� line�rn� z�vislost v�po�etn� n�ro�nosti dynamick�ho programovan�. Ta je vypo�tena jako rozm�r pole, tj. kapacita x po�et v�c�. Po�et v�c� je konstantn�, ale m�n� se kapacita batohu, c�m� je ovlivn�no m��en�. Pokud by gener�tor zachoval kapacitu konstantn�, byla by i z�vislost konstantn�.
Chyba heuristiky se zmen�uje s rostouc�m pom�rem sum�rn� v�hy ke kapacit� batohu. Naproti tomu o z�vislosti chyby heuristiky na granularit� nem��eme z proveden�ho experimentu nic usoudit, hodnoty jsou t�m�� n�hodn�.