| Abstract: |  Bakalářská práce se zabývá problémem hledání nejkratších cest v~polygonální doméně.
Studovaný problém je motivován úlohami plánování cesty pro mobilní roboty v~geometrické reprezentaci pracovního prostředí robotu. V~práci jsou nejdříve představeny základní přístupy řešení problému hledání nejkratší cesty. Na přehled přístupů navazuje detailní popis algoritmu, který je inspirován optimálním algoritmem hledání nejkratší cesty, jež využívá teselaci volného prostoru založenou na Voroného diagramu. Tato teselace rozděluje volný prostor na trojúhelníky a jednoduché polygony a tvoří základní urychlující strukturu pro dotazy na nejkratší cesty mezi dvěma libovolnými body ve volném prostoru. Vlastní konstrukce nejkratší cesty využívá přepočítaného grafu viditelnosti a tzv. kritických bodů určených z~expanze funnelů. Tento algoritmus byl implementován a v~práci jsou uvedeny výsledky ověřujících experimentů správnosti implementace a skutečné výpočetní náročnosti. Mimoto je v~práci uvedeno porovnání výpočetní náročnosti algoritmu s~přístupy založenými na konstrukci grafu viditelnosti a také aproximačním algoritmem poskytujícím odhad nejkratší cesty. V~závěru experimentů je pak posouzen vliv výpočtu nejkratší cesty na řešení úlohy obchodního cestujícího technikou samoorganizující se neuronovou sítí.
|
|---|