Porównanie algorytmów przeszukiwania przestrzeni

Zadanie:

W pewnej przestrzeni należy zaprogramować znajdywanie ścieżki pomiędzy punktem startowym a metą (jedną z kilku). Należy zaimplementować parę algorytmów ślepych i heurystycznych (z pamięcią).

Do programowania wybrałem język Java i środowisko Netbeans.

Problemy i ich rozwiązania:

Należało jakoś odzwierciedlić przestrzeń (graf) w programie. Użyłem do tego tablicy 2-wymiarowej, której pola odzwierciedlały zdyskretyzowaną mapę. Wartości pól to koszt przejścia przez pola mapy. Tablica przechowywana była w klasie “mapa”, w której umieściłem jeszcze inne dane dotyczące mapy, jak wymiary x i y itp.

Kolejnym krokiem było wymyślenie sposobu na przechowywanie trasy. Stworzyłem najpierw klasę ‘punkt’, która miała odzwierciedlać jeden punkt na trasie, oraz klasę ‘trasa’ – przechowującą punkty. Dzięki temu mogłem bez problemu w algorytmach dodawać i odejmować punkty na trasie oraz na bieżąco liczyć jej koszt. (przy użyciu metod tych klas)

Należało jeszcze stworzyć klasę odpowiedzialną za wyświetlanie map, kolejną do zbierania statystyk (np uśredniony czas 30 przebiegów jednego algorytmu) oraz jeszcze jedną do odczytu mapy z pliku i tłumaczenia jej na tabelę zrozumiałą przez algorytmy.

Z tym wszystkim zaplecze już mniej więcej było gotowe.

Niezbędne było jeszcze przygotowanie map, tak by nie były losowe i jednocześnie nie faworyzowały algorytmów, aby wyniki nie były przekłamane.

Mapka w pliku tekstowym wyglądała tak:

• w – woda
• d – droga
• g – góry
• l – las
• . – trawa
• s – start
• m – meta

Odzwierciedlenie ich kosztów w programie było mniej więcej zgodne z intuicją np. drogą szybciej niż łąką, górami wolniej niż lasem.

wwwwwwwwwwwggggg................gggggggwwwwwwwwwww
wwwwwwwwwwwggggg.....g.....g....gggggggwwwwwwwwwww
wwwwwwwwwwwggggg.....g...g......gggggggwwwwwwwwwww
wwwwwwwwwwwggggg.......g........gggggggwwwwwwwwwww
wwwwwwwwwwwggggg.....g..........gggggggwwwwwwwwwww
.....l.l..........................................
...lggggggggggggggg...........gggggggggggggggg....
..l.ggggggggggggggg...........ggggggggggggggggl...
l...ggggwwwwwwwwwww.....s.....wwwwwwwwwwwwgggg....
....ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwgggg.l.l
....ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwgggg.l..
....ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwgggg..l.
....ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwgggg....
l...ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwgggg.l.l
.l..ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwgggg....
..l.ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwgggl.g..
....ggggwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwg.......
...lgggggggggggggggggggggggggggggggggggggg..gg....
....gggggggggggggggggggggggggggggggggggggglggg.g..
.l...l..........l.....g......l.....lll...........g
..l....l.l........g.g..............l..........g...
.....l.....l........l....llg.......lll............
...l..................l......g.....lll............
wwwwwwwwwwwwwwwlwwwww...l.....wwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwlllwww.........wwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwllww......l..wwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwllll.....l..wwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwww..l...l..wwwwwwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwwwwww.........wwwwwwwwwwwwwwwwwwww
lllll.......................................llllll
lllll.gggggggggggg.....l...l....ggggggggggg.llllll
lllll.gggggggggggg.......l......ggggggggggg.llllll
lllll.gggggggggggg.....l...l....ggggggggggg.llllll
lllll.gggggggggggg...l......l...ggggggggggg.llllll
lllll.gggggggggggg..............ggggggggggg.llllll
lllm..................ggddgg..................llll
lllll.................ggddgg................llllll
lllllllllllllll.......ggddgg.......lllllllllllllll
lllllllllllllll.......ggddgg.......lllllllllllllll
wwwwwwwwwwwwwwww......ggddgg.......wwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwggggggggddgggggggggwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwggggggggddgggggggggwwwwwwwwwwwwwww
wwwwwwwwwwwwwwww......gg..gg.......wwwwwwwwwwwwwww
wwwwwwwwwwwwwwww......gg..gg.......wwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwgggg.........ggggggwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwgggg.........ggggggwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwgggm.........ggggggwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwgggggggggggggggggggwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwgggggggggggggggggggwwwwwwwwwwwwwww
wwwwwwwwwwwwwwwwgggggggggggggggggggwwwwwwwwwwwwwww

A to jej wersja po przetrawieniu w programie z nałożoną trasą (punkt mapy to jeden kwadracik 5×5px):

Przyszła kolej na implementację algorytmów.

Zaimplementowałem cztery metody (każda jako osobna klasa dziedzicząca po klasie ‘mapa’) i mały bonus:

• po szerokości
• po głębokości
• zachłanna
• A*
• metoda mrówkowa (jako bonus) – będąca dość ciekawym algorytmem genetycznym

Opisy każdego z tych algorytmów nietrudno znaleźć w internecie, także daruję sobie wykład.

Procedura testowa:

Testy przeprowadzałem na swoim laptopie, przy wyłączonych programach mogących wpłynąć na obciążenie procesora i przekłamanie czasu obliczeń. Dla pewności wynikiem algorytmu dla każdej mapy były średnie z od 30 – 300 przebiegów (w zależności od rozmiaru mapy) algorytmu. Czynniki brane pod uwagę to koszt tras, czas wyszukiwania i ilość punktów trasy.

Ogólne wyniki algorytmów:

Zachowanie się metody po głębokości dla różnego ustawienia kolejności kierunków (cztery kierunki = 16 kombinacji. Poniżej przedstawiłem efekty tylko czterech kombinacji):

Aplikacja jeszcze w starszej wersji:

Podsumowanie:

Zadanie było bardzo ciekawe, szczególnie, że niektóre z tych algorytmów można zaimplementować do bardziej złożonych problemów. Dobitnie dało mi ono do zrozumienia, jak nieoptymalny jest przegląd całkowity wszystkich rozwiązań, który dla większych map jakie przygotowałem, trwał by latami albo i dłużej. Obecnie pracuję również nad algorytmem genetycznym dla problemu plecakowego, które/y może również tu przedstawię.