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

řadí mezi tzv. NP (nedeterministicky polynomiální) problémy, což znamená, že není známý způsob, jak rychle nalézt přesné řešení pro každý problém. Zároveň je nejisté, jestli lze najít způsob, jak rychle nalézt toto řešení, který by byl úměrný nějaké mocnině počtu prvků. Je zřejmé, že se jedná o komplexní problém, který nelze předvídat, pokud vezme me v potaz, že výpočetní proces, který má schopnost se ve každé fázi rozvětvit do růz ných směrů, by mohl začít na určitém místě a rozdělit výpočet do různých částí podle počtu možných cest z tohoto místa. Při dalším postupu by bylo možné pokračovat podobným způsobem, s výjimkou tras, které vedou, k již navštíveným místům. V případě existence n bodů by byly zkou mány všechny možné cesty v n krocích a počet větví by dosáhl nejvýše (n – 1)! K řešení těchto problémů se v běžném provozu často používají různé nepřesné heuristické přístupy, jako například genetické algoritmy, simulované žíhání nebo konti nuální neuronové sítě. [5.17] Přestože to může znamenat odchýlení od hledání dokonalého řešení, tímto způ sobem je nalezeno řešení v čase, které lze aplikovat v praxi. Obecná představa heuristických algoritmů nenabízí záruku dokonalé shody s op timální trasou, avšak existují prakticky použitelné (polynomiální) algoritmy, které do káží toto zajistit pro metrický problém obchodního cestujícího (například Christofidův algoritmus, který je schopen definovat trasu, jež je maximálně o 50% delší než nejkratší možná). Problém s rozhodováním je velmi obtížný a nelze ho jednoduše vyřešit. Je složitý a vyžaduje mnoho času a úsilí. Dokonce i když najdeme možné řešení, musíme vynalo žit spoustu úsilí na jeho ověření, abychom se ujistili, že splňuje naše požadavky. V případě malého množství středových prvků lze uplatnit základní postupy. Ty sice neposkytují vysokou efektivitu, ale jsou rychlé, nevyžadují mnoho výpočetních a paměťových zdrojů a úspěšně dokončí danou úlohu. Když je třeba určit nejlepší cestu, třeba pomocí metody „brute force“, musíme počítat s tím, že to bude vyžadovat obrovské množství paměti a velké výpočetní zatížení procesoru. Metoda „brute force“, tzv. metoda hrubé síly prozkoumává každou dostup nou možnost a vybírá z nich tu s nejoptimálnějšími parametry. [5.17] Mnozí vědci se již dlouho věnují tomuto problému, i když byl původně předsta ven v roce 1932. Zatím se však nepodařilo objevit žádné efektivní a univerzální řešení. Přestože TSP reprezentuje pouze otázku nejkratšího okruhu, v běžném světě se setká váme s mnoha reálnými problémy, které odpovídají TSP. Abychom lépe porozuměli tématu, následující pasáž poskytne vysvětlení potenciálních případů. [5.11] Příklad 1 – Distribuce dodávek ze skladu na montážní stanoviště Distribuce dodávek ze skladu na montážní stanoviště je jedním z příkladů prů myslové logistiky a distribuce zásilek. V kontextu optimalizace transportní trasy se větši nou využívá tzv. TSP, jelikož umožňuje minimalizovat čas a náklady spojené s doručová ním zásilek. V případě, že vůz musí sbírat zásilky na n různých lokacích, lze tuto situaci analyzovat jako problém obchodního cestujícího (TSP). Při řešení tohoto problému

65