Batohové algoritmy
Matematika | 12.05.09
Máme k dispozici určitý počet předmětů. U každého známe jeho váhu a cenu. Potřebujeme v batohu s určitou nosností přenést co nejcennější kontraband. Naneštěstí je však celková hmotnost všech předmětů vyšší než nosnost batohu.
Sdílet
Takže, ač neradi, nějaké zboží budeme muset nechat na místě. Jak to udělat, abychom přenesli zboží v co nejvyšší hodnotě?
Dejme tomu, že nosnost batohu je 6 kg. Máme 4 předměty s následujícími vahami a cenami:
3...9
3...9
4...14
5...16
Problém batohu se někdy uvádí jako příklad úlohy, na níž nelze aplikovat tzv. hladový princip (princip horolezce). Tato metoda spočívá v tom, že v každém kroku uděláme „lokálně optimální“ volbu, která nám vzhledem k zadání dá po skočení „kola“ nejlepší pozici do dalšího průběhu. V batohové úloze by to znamenalo, že nejprve vybereme nejcennější předmět, který se ještě do batohu vejde, a v dalším kroku postupujeme stejně. To by znamenalo, že bychom vzali předmět č. 4, s hmotností 5 a cenou 16 – a do batohu by se nám už nic nevešlo. Když naložíme dva první předměty, přeneseme však celkem zboží v hodnotě 18.
Nelze použít ani modifikovaný postup horolezce, kdy u každého předmětu spočítáme poměr cena/váha a pak postupujeme od předmětu relativně nejcennějšího. V tomto případě by byl „nejcennější“ předmět číslo 3, naložili bychom ho do batohu – a zase konec, dokonce ještě s horším výsledkem než v prvním případě.
Úloha o batohu je každopádně řešitelná obtížně, protože patří mezi NP úplné problémy. K dispozici nicméně máme několik heuristických postupů, například tzv. prořezávání stromu. Napadá vás, jak postup řešit pro ještě jednoduché úlohy, kde již nelze použít „výčet“ možností v hlavě?
Zdroj: Jiří Vaníček a kolektiv: Teoretické základy informatiky, Kernberg Publishing, Praha 2007
O knize na stránkách vydavatele
Další články z rubriky
Související články
Nahrává se..
Videa
Chobotnice mění průhlednost stejně rychle jako displej Amazon Kindle
Maskování chobotnice se svou rychlostí vyrovná...
Komentáře
13.05.09, 04:16 pavelhouser
evolucni algoritmy
po pravde receno, tento pristup k problemu se v knize neuvadi - evolucnim algoritmum se zde venuji jen 3 strany. ale stejne mohu knihu doporucit - tedy pro ty, kdo obor nevystudovali, je to spise zakladni prehledova ucebnice, ale prave je dobra ta systematicnost.
12.05.09, 13:14 Kubson
GA
Třeba vhodný genetický algoritmus. Fitness funkce by byla cena batohu. Chromozóm bude binární řetězec o délce velikosti množiny předmětů. Na množině přdmětů bude ostré uspořádání a bity v chromozómu budou odpovídat předmětům. Pokud bude bit 1 patří předmět do batohu, jinak nepatří. Do fitness funkce bude vhodné zakomponovat i velikost přesahu resp. volné místo. Křížení dvoubodové, mutace překlepení jednoho bitu. Velikost pouplace a počet generací by se odvíjel od velikosti problému. Pravděpodobnost mutace a křížení by se musela určit experimentálně.
Napsat vlastní komentář
Pro přidání příspěvku do diskuze se prosím přihlašte v pravém horním rohu, nebo se prosím nejprve registrujte.