Lista przedmiotów z materiałami udostępnionymi dla studentów

Dla_studentów
  • Increase font size
  • Default font size
  • Decrease font size

Ewa Morzyńska

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


Implementation of selected shortest path algorithms on a mobile phone with Android OS


Opiekun pracy dyplomowej: dr inż. Piotr Skulimowski
Praca dyplomowa inżynierska obroniona 2013-02-18
Streszczenie pracy dyplomowej:
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ń.
Abstract:
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.