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.

Bug się rodzi, kod truchleje

+——————————————————–+
| *Bug sie rodzi, kod truchleje…* |
| |
(Powstawala na pl.listserv.chomor-l i pl.comp.programming)
+——————————————————–+

Bug sie rodzi, kod truchleje,
choc nie w BIOS-a osadzony,
Segfault krzepnie, Flash ciemnieje,
backtrace bedzie nieskonczony!
Wzgardzony, okryty chwala
Smiertelny, DOS nad wiekami
A slowo sie tekstem stalo
I mieszalo procesami.