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

mu obchodního cestujícího tím, že umožňuje systematicky vyhodnocovat a aktualizo vat hodnoty, což v konečném důsledku vede k nalezení optimální trasy. Dynamické programování vyžaduje časový zdroj (tj. časovou náročnost) O(n 2 ⋅ 2 n ) a prostorový zdroj (tj. prostorovou náročnost) O(n ⋅ 2 n ) . Jakmile n dosáhne určité hod noty, náročnost se dramaticky zvyšuje. To znamená, že kromě menších problémů se dynamické programování využívá jen zřídka. [5.17] Vázaný algoritmus Vázaný algoritmus je algoritmus, který je široce aplikovaný jako vyhledávací me toda. Řídí vyhledávací proces skrze účinné omezovací limity, které umožňují najít opti mální řešení hlavní stromové struktury co nejrychleji. Hlavní aspekt tohoto algoritmu spočívá v nastavení omezení. Různé omezující hranice mohou generovat různé varianty algoritmu, které se vztahují na imaginární větve stromu. Algoritmus s omezením však není ideální pro řešení komplexních a složitých problémů. Přibližný algoritmus pro řešení TSP Vzhledem k tomu, že použití exaktního algoritmu pro vyřešení problému ob chodního cestujícího (TSP) je velmi limitované vzhledem k jeho výpočetní náročnosti a exponenciální časové složitosti, často se upřednostňuje použití aproximačních algo ritmů či heuristických algoritmů. Tyto algoritmy poskytují rychlejší a praktičtější ře šení TSP, i když za cenu menší přesnosti. Výsledek takového algoritmu lze posoudit z hlediska jeho kvality, která se vyjadřuje jako poměr dosažené délky trasy k optimální délce trasy – vztah (5.6). Tato kvalita může být vyjádřena jako procentuální odchylka od optimálního řešení nebo jako relativní chyba. Kde C je označení pro celkovou trasu stanovenou přibližným algoritmem; C* je představuje optimální trasu, ∈ značí maximální poměr mezi trasami přibližného a opti málního řešení za nejhorších podmínek. Hodnota ∈ > 1,0 , přičemž, jestliže ∈ se blíží hodnotě 1,0, tím je algoritmus efektivnější. Mezi metody přibližného algoritmu pro řešení problému obchodního cestujícího (TSP) patří několik významných přístupů. Mezi tyto metody patří [5.14]: • Interpolační algoritmus, • Algoritmus „Clark & Wright“ • Algoritmus „Double spanning tree“, • Algoritmus „Christofides“, Interpolační algoritmus – představuje efektivní nástroj pro minimalizaci celkové délky trasy a dosažení optimálního řešení problému obchodního cestujícího (TSP). Tato metoda využívá interpolace mezi jednotlivými body v grafu pro nalezení optimální trasy. Interpolační algoritmus se snaží aproximovat ideální trasu pomocí hladké křivky, která prochází všemi body v grafu. Tímto způsobem lze minimalizovat celkovou délku trasu • Algoritmus „r – opt“, • hybridní algoritmus.

68