Darbo tikslas yra išanalizuoti keliaujančio pirklio algoritmo realizacijos galimybes egzistuojančiose navigacinėse sistemose, bei išanalizavus pasirinktus algoritmus keliaujančio pirklio problemai spręsti, parinkti tinkamiausią algoritmą pagal turimus atminties ir skaičiavimo resursus bei problemos sudėtingumą. Tyrimo rezultatai parodė, jog nėra tinkamiausio algoritmo visiems atvejams, nes skirtingose situacijose skirtingi algoritmai rodo geriausius rezultatus. / The investigation had a list of objectives: analyze the capabilities and resources of a range of chosen GPS navigation devices; analyze the needs and requirements of traveling salesman related GPS navigator functions for regular users; analyze what types of TSP algorithms are used in existing navigation software products; analyze the capabilities of various TSP algorithms with regard to used resources and speed of calculations; determine which algorithms are optimal for a range of specific situations. Research of different algorithms led to a conclusion that there is no single algorithm that is always better than the rest. Under different circumstances, different algorithms showed different results. Some were clearly optimal in some situations, while others competed with each other in other situations. The key element to success of an algorithm was how much time it got to do it's calculations. The amount of the input data changed the duration of the calculations but the algorithm function declination rate remained mostly the same with different sets of input data.

Dinaminiai kelio paieškos algoritmai apjungia euristinės ir plečiamos (angl. incremental) paieškos metodus, sprendžiant eiles panašių paieškos uždavinių tiek žinant visą informaciją apie aplinką, tiek neturint jokios informacijos. Yra trys plečiamą paiešką naudojančių algoritmų klasės. Šiame darbe pateikiama trumpa dinaminių kelio paieškos algoritmų, naudojančių plečiamos paieškos metodus analizė. Pagrindinis darbo tikslas – visų trijų plečiamos paieškos klasių algoritmų, kuriuos naudojant gaunamas optimalus kelio paieškos sprendinys aplinkose, kur perėjimų tarp viršūnių svoriai gali didėti ir mažėti, palyginimas. Algoritmai lyginami trijose skirtingose situacijose: stacionarioje, judėjimo link tikslo (angl. goal – directed) bei judančio taikinio (angl. moving – target). Tyrimo rezultatai parodė, jog A* ir FSA* nepasiekiamų viršūnių kiekiui esant ~16000 yra ~23,6% našesni už GAA* ir trečios plečiamos klasės algoritmus, o pasiekiamumą keičiančių viršūnių kiekiui esant ~8000 – 42,3%. Nepasiekiamų viršūnių kiekiui kintant nuo 1000 iki 16000 trečios plečiamos klasės algoritmai yra vidutiniškai ~58,7% našesni už GAA* ir ~54% našesni už A* ir FSA*. Pasiekiamumą keičiančių viršūnių kiekiui kintant nuo 500 iki 8000 trečios plečiamos klasės algoritmai yra vidutiniškai ~69,3% našesni už GAA* ir ~47,8% našesni už A* ir FSA*. / Dynamic path finding algorithms combine heuristic and incremental search methods to solve a series of similar search tasks in both known and unknown environments. There are three classes of incremental search algorithms. In this document we provide a brief summary of dynamic path finding algorithms, that uses incremental search methods, but its main focus is on comparing main algorithms of all three incremental classes, that are guaranteed to give optimal solution in environment where action costs can increase and decrease over time, and showing their strong and weak sides. The algorithms are compared in three different situations: stationary, goal – directed and moving – target. At the end of the document conclusions are given based on performed work. In this paper, research showed that A* and FSA* are ~23,6% more efficient than GAA* and third incremental class algorithms when the amount of untraversable cells is ~16000 and ~42,3% more efficient when the amount of traversability changing cells is ~8000. When the amount of untraversable cells is between 1000 and 16000, the third incremental class algorithms are ~58,7% more efficient than GAA* and ~54% – than A* and FSA*. When the amount of traversability changing cells is between 500 and 8000, the third incremental class algorithms are ~69,3% more efficient than GAA* and ~47,8% – than A* and FSA*.