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.

NapiProject (linux) – skrypt rekurencyjny

Motywacja

Alternatywą dla znanego wszystkim programu NapiProject pod linuksa (poza odpalaniem Napi przez Wine) jest programik napisany w pythonie autorstwa panów(tak mniemam): gim,krzynio,dosiu,hash.
Programik mimo, iż działa wzorowo nie ma opcji przeszukiwania rekurencyjnego katalogów, czyli w uproszczeniu: podaj_katalog -> znajdź_filmy -> znajdź_do_nich_napisy. W takim właśnie uproszczeniu i bez fajerwerków (sprawdzania np. czy katalog istnieje etc) działa poniższy skrypcik.

Skrypt wygląda następująco:

#!/bin/bash
#—————————————#
#skrypt by spas (spassite.wordpress.com)#
#—————————————#
dir=”/katalog/z/filmami/”
ext=”.avi”; #rozszerzenie do wyszukania
find $dir -name “*.avi” | while read file
do
name=`echo $file | sed ‘s/.avi//’`; #utnij rozszerzenie
file=`echo $file | sed ‘s/ /\ /’`;
if [ ! -e "${name}.txt" ]; then #czy napis jeszcze niepobrany?
echo “${name}.avi”
./napi.py “$file”; #wywolaj skrypt dla filmów bez napisów
fi
done

Aby uruchomić skrypt:

chmod +x plik_z_powyższym_skryptem.sh
./plik_z_powyższym_skryptem.sh

Do jego działania niezbędny jest napi.py w tym samym katalogu co skrypt, oraz paczka “p7zip-full” (sudo aptitude install p7zip-full), bez której napi.py nie będzie poprawnie pobierać napisów.

Lista życzeń (czyt. co zrobię jak będę miał chwilkę):

• sprawdzanie, czy katalog istnieje
• ścieżka do katalogu odczytywana ze zmiennych wywołania
• obsługa wielu rozszerzeń
• …

Pliki do pobrania:

napi.py – program ściągający napisy do pobrania