Grafų teorijos problema ieškant trumpiausio kelio
Rymkevičius, Petras |
Baigiamajame magistro darbe yra aprašyta bei atlikta trumpiausio kelio suradimo algoritmų analizė. Taip pat atlikta užduočiai įgyvendinti reikalingų įrankių pasirinkimo, kaip automatizuotų projektavimų sistemų ir programavimo kalbų analizė. Buvo domėtasi dirbtiniu intelektu, ir įgyvendinta programiniu būdu agento veikimas ieškant trumpiausio kelio, turint pradžios ir pabaigos tašką brėžinyje. Sukurta programa analizuoja brėžinį tarp pradžios ir pabaigos taškų, išskleidžia galimus kelius taip sudarydama grafą, bei suranda trumpiausią kelią jame. Ši užduotis yra tinkamas agento veikimo pavyzdys brėžinyje. Praktikoje tai gali būti taikoma ieškant mažiausių sąnaudų kabelių tiesimui, renkantis trumpiausią maršrutą planuojant išvyką arba kaip vieną iš fizinių užduočių robotų veikimui patobulinti.Darbo apimtis - 54 puslapiai teksto be priedų, 18 iliustracijų, 6 lentės, 33 bibliografiniai šaltiniai.Atskirai pridedami darbo priedai.
In this master thesis the finding of the shortest path algorithm analysis is described and performed. Also the analysis of required tools selection, as computer-aided design systems and programming language is performed. The interest was taken in the artificial intelligence and the agent's performance of finding the shortest path, which was implemented by program, while having the star and the end points on the drawing. The program analyzing the drawing between the star and the end points, outlining the possible paths and drawing the graph, and finding the shortest path on it was established. This task is an appropriate example of the agent's performance in the drawing. In practice, it can be used to find the lowest cost of cable construction, choosing the shortest rout when panning a trip or as a natural task to improve the functioning of the robot. The size of this work is 53 pages without appendixes, 18 illustrations, 6 tables and 33 bibliographic sources. The appendixes are presented separately.