Implementacja wybranych algorytmów poszukiwania ścieżki na platformie Android

Celem niniejszej pracy dyplomowej było zaimplementowanie wybranych
algorytmów wyznaczania najkrótszej ścieżki w języku Java dla urządzeń pracujących pod
kontrolą systemu Android. Opracowana aplikacja testowa pozwala na sprawdzenie
poprawności implementacji algorytmów. Umożliwia użytkownikowi zaprojektowanie
mapy z przeszkodami oraz zdefiniowanie punktów: startowego i docelowego.
W pracy zamieszczono opis wybranych zagadnień z teorii grafów, omówiono
wybrane algorytmy poszukiwania optymalnej ścieżki: algorytm A* dzielący mapę na
siatkę jednakowych figur oraz algorytmy Forda-Bellmana oraz Dijkstry pracujące na
grafach tworzonych na podstawie mapy. W dalszej części zaprezentowane zostały
wykorzystane narzędzia do opracowania projektu – środowisko Eclipse oraz platforma
Android, a także opisana została implementacja algorytmów i budowa aplikacji testowej.
Ostatni rozdział został poświęcony analizie wyników działania algorytmów.
Przeanalizowano m.in. czas potrzebny na wyznaczenie optymalnej ścieżki dla różnych
rozmiarów map na wybranych do testów urządzeniach mobilnych. Zwrócono także uwagę
na nakład obliczeniowy, zapotrzebowanie na zasoby pamięciowe, wady i zalety
zaimplementowanych algorytmów oraz obszary ich zastosowań.

The aim of this thesis was to implement selected shortest path algorithms in Java for
devices running under Android OS(Operating System). The developed test application allows
users to check the correctness of the implementation of the algorithms. The test application
also allows designing maps with obstacles and defining start and end points for the paths.
In this thesis three algorithms for path planning are discussed: the A* algorithm which
divides the map into a grid of identical figures and the Bellman-Ford and Dijkstra's algorithms
which work on graphs created from the map. The thesis also includes review of the tools used
for developing the application for Android OS - the Eclipse and information on the Android
platform itself. The main thesis chapters discuss the implementation of the path planning
algorithms and tests of the developed application. Analysis of the tests results includes the
time required to determine the optimal path for different sizes of maps for a number of
different mobile devices. The summary of the dissertation compares the computational effort,
demand for resources, advantages, disadvantages and suggested application areas of the
implemented algorithms.