Představte si skupinu měst, spojených silnicemi různých délek. Jak nalézt nejkratší cestu, která navštíví každé město právě jednou? Třeba pomocí mravenců.
Na začátku vypustíte z prvního města skupinu mravenců a dáte jim za úkol obejít všechna města právě jednou. Mravenci se nejprve na každé křižovatce rozhodují úplně náhodně a jejich nalezená řešení proto nebudou moc dobrá.
Síla mravenců je ale ve feromonech, které po cestě vypouštějí. Čím kratší je cesta, kterou konkrétní mravenec našel, tím víc feromonů na jejích silnicích zanechá.
Mravence takhle vyšlete ještě několikrát, ale teď už je necháte s větší pravděpodobností vybírat "voňavější" silnice.
Postupně bude chodit po kratších (a tedy lepších) cestách stále více mravenců a pokud budete mít štěstí, možná takhle najdete dokonce i optimální řešení.
Hledání nejkratší cesty mezi skupinou měst tak, abychom každé navštívíli právě jednou, je úloha, které se v informatice říká problém obchodního cestujícího. Patří do skupiny problémů, na které neexistuje algoritmus, který by je uměl efektivně vyřešit.
Typicky se proto používají nějaké heuristiky, které se snaží najít když ne optimální, tak alespoň co nejlepší řešení. Jeden z přístupů jsou různé algoritmy inspirované přírodou, jako například zde popsaná optimalizace mravenčí kolonií.
- Pro vkládání komentářů se musíte přihlásit
O těch mravencích jsem to
Aries
O těch mravencích jsem to věděla, ale ne že se to takhle využívá. Zajímavé
Ty jsi blesk. Optimální grafy
mila_jj
Ty jsi blesk. Optimální grafy hledal třeba český profesor Borůvka. Moc pěkné drabble.
Jé, co se tu člověk všechno
Lee
Jé, co se tu člověk všechno nedozví, to je hrozně fajn. :)