UMĚLÁ INTELIGENCE V AUTOMOTIVE / David et al.

optimalizace, plánování a rozhodování. Mezi tyto klíčové disciplíny patří lineární al gebra, teorie diferenciálních rovnic, matematická analýza, matematické programování, teorie grafů a sítí, teorie optimálního řízení, teorie užitku, teorie hromadné obsluhy, teorie her, simulace a imitační modelování. Většina efektivních postupů vyžaduje využití moderních počítačových technolo gií. Proto se soustředíme na vytváření algoritmů a softwaru s využitím umělé inteligence k zlepšení jejich výkonu. V operačním výzkumu jsou používány různé typy modelů k simulaci, analýze a optimalizaci různých procesů a systémů. Mezi nejběžnější typy modelů patří deter ministické modely, které pracují s pevnými vstupy a předpokládají známé vztahy mezi vstupy a výstupy, a stochastické modely, které zahrnují náhodné proměnné a pravděpo dobnostní distribuce. Dále lze v operačním výzkumu nalézt diskrétní modely, které se zaměřují na pro blémy s diskrétními hodnotami. Tyto modely se zaměřují na optimalizaci a plánování v situacích, kde jsou k dispozici pouze omezené možnosti a rozhodnutí musí být pro vedena na základě diskrétních hodnot. Tento přístup umožňuje efektivní řešení mnoha reálných problémů, jako například plánování výroby, distribuce zásob, optimalizace tras nebo rozhodování v podmínkách neurčitosti. Jedním z takových to problémů je pro blematika obchodního cestujícího, na jehož řešení byla aplikována umělá inteligence. 5.3 PROBLEMATIKA OBCHODNÍHO CESTUJÍCÍHO Problém obchodního cestujícího (anglicky travelling salesman problem – TSP) představuje náročný diskrétní optimalizační problém. Jeho matematický výraz a zobec nění spočívá v úkolu určit nejkratší dostupnou trasu, která projde všemi body hodno ceného diagramu. Zjednodušená formulace problému: máme určitý počet bodů (např. měst, pra covišť apod.) vzájemně propojených (např. silnicemi) s různými délkami. Cílem je určit nejkratší trasu, která prochází všemi body pouze jednou a vrátí se zpět do bodu výchozího. [5.17] Matematická formulace: v ohodnoceném úplném grafu najděte nejkratší hamil tonovskou kružnici. Problémem není tak vymezit nějaký způsob, jak najít nejkratší trasu – takový postup je v podstatě zřejmý: stačí prozkoumat všechny potenciální trasy mezi danými body a vybrat tu nejkratší. Problém spočívá v tom, že jak se zvyšuje počet bodů, expo nenciálně se zvyšuje i počet možných tras, což vede k enormnímu zvýšení výpočetního času na počítačích, který se stává absolutně nesnesitelným již při nízkém počtu desítek bodů. Hlavní komplikací je tedy vývoj algoritmu pro hledání nejkratší trasy, který by byl efektivní z hlediska času. [5.17] Navíc v běžné verzi tohoto problému nepožadujeme, aby v grafu byla dodržována trojúhelníková nerovnost. Problém obchodního cestujícího (TSP) je jedním z nejznámějších a nejstudova nějších problémů v oblasti optimalizace. Tento problém ve své optimalizační formě se

64