Jasně. Ale rozhodující je, jakou část prostoru vážně projdeš a jaká se odřízne. Pokud budeš permutace generovat postupně, budeš tímpádem procházet strom a můžeš jedním krokem odříznout obrouvskou část prostoru.
Tak pokud hledáte optimum, tak neuříznete skoro nic. Že se nějaká permutace zdá býti dobrá na začátku, ještě neznamená, že bude dobrá na konci. Tenhle problém jsme měli v semestrálce na VŠ a byly tam speciálně připravené desítky zadání, na kterých se pak ukazovaly takovéhle chyby. Nevím, zda to dám z hlavy správně, ale zkusím:
X1 = 40
X2 = 40
X3 = 20
X4 = 75
X5 = 55
X6 = 55
Velikost úložiště je 100.
Na začátku stromu dám U1 = X1 + X2 + X3, plně využité. Pokud zbytek stromu uříznu, tak skončím s tím, že X4, X5 i X6 budou mít úložiště vlastní. Celkem 4 úložiště. Přitom stačí 3 (X1 + X5, X2 + X6, X3 + X4), z nichž ale ani jedno nebude plné. Fakt, že se mi ten první "baťoh" podaří krásně na 100% vyplnit, ještě nic neznamená, řezat nesmím. A teď opačné cvičení - na všech permutacích zjistit prostor. Zjistíte, že jich polovina bude 4 a méně. Pokud tedy jako první netrefíte právě to optimální, tak oříznete jen necelou polovinu listů.
Nenechte se zmást hledáním do hloubky, to sice obecně řeže, ale vy se v něm budete pohybovat hodně hluboko a řezat jen zbytky. A pak dospějete ke zjištění, že díky algoritmu to není O(2^n), ale "jen" O(2^(n/2)) = O(2^n)
52 Odpovědí
13302 Zhlédnutí