Student: Łukasz Kinel gr. 17 Warszawa, 10.VI.2008

Prowadzący: prof. nadzw. dr hab. inż. Barbara Putz

Termin zajęć: wtorek 11.15-12.15

Zasady programowania strukturalnego - projektowanie

Dokumentacja końcowa projektu

cz. I - ogólna

1. Temat (w postaci podanej przez prowadzącego)

Napisać program, który dla grafu zadanego listą węzłów i reprezentującego mapę gry z przeszkodami generuje najkrótsze przejście między dwoma zadanymi punktami, dwiema metodami dla porównania:
- metodą Dijkstry
- metodą A* (A star)

2. Założenia dodatkowe (nie określone w temacie, przyjęte przez autora) - o ile są

W celu porównania obu algorytmów umieszczę w nich licznik węzłów, które algorytm badał oraz przetestuje działanie algorytmu A* dla 2 funkcji heurystycznych (funkcji typu Manhattan oraz oszacowania odległości dwóch węzłów przez obliczenie standardowej euklidesowej ich odległości). Mapę gry będzie reprezentować tablica 2-wymiarowa wypełniona cyframi 0,1,2 oraz 3, gdzie 0 oznaczać będzie przeszkody, 1 miejsca, w których przeszkód nie ma, 2 punkt startowy, 3 punkt docelowy. Każda niezerowa komórka tablicy będzie reprezentować 1 węzeł grafu. Wagi połączeń miedzy pomiędzy węzłami grafu będą się rozkładać następująco(rys. obok):

10 - jeśli poruszamy się po boku komórki

14 - jeśli poruszamy się po przekątnej komórki.

Zakładam, że sposób poruszania się po mapie odpowiada ruchom króla na szachownicy tj. jedyne możliwe ruchy to w gore, w dół, na boki oraz po przekątnych zawsze o 1 pole (w tablicy odpowiada to ruchowi nie dalej niż do sąsiedniej komórki).

cz. II - wejście/wyjście

3. Format danych wejściowych

Rozmiary mapy będą podawane przez użytkownika. Mapa będzie generowana losowo a następnie informacje o jej wyglądzie będą wypisywane do pliku dane_wejsciowe.txt (w postaci: ilość pól na mapie położenie pola startowego położenie pola końcowego ilość krawędzi a następnie lista krawędzi w postaci: węzeł pierwszy węzeł drugi waga krawędzi) a tablica reprezentująca mapę zostanie wypisana do pliku tablica.txt. Następnie dane wejściowe będą wczytywane z pliku przez odpowiedni algorytm i na ich podstawie powstanie graf.

4. Format danych wyjściowych

Program będzie wypisywał na ekranie długość najkrótszej drogi pomiędzy zadanymi punktami, jej przebieg (w postaci tablicy, w której pola oznaczone literą „x” oznaczać będą szukaną drogę) oraz wydajności obu algorytmów w postaci liczby węzłów, które dany algorytm badał w trakcie wykonywania.

cz. III - struktury danych

5. Wykaz struktur danych przewidzianych w aplikacji i informacje, jakie dane będą w nich przechowywane, spośród poniższych:

• pliki tekstowe wejściowe i wynikowe

Plik wejściowy: tablica.txt - przechowywane w nim będą rozmiary mapy oraz jej wygląd.

Plik wejściowy: dane_wejsciowe.txt - przechowywane w nim będą dane niezbędne do przetworzenia tablicy reprezentujące mapę na graf

• tablice dynamiczne

• Tablica reprezentująca mapę gry

• Tablica d[] przechowująca długość drogi z węzła startowego do danego

• Tablica p[] przechowująca poprzednik danego węzła na najkrótszej ścieżce

• Tablica QS[] wskazująca przynależność danego węzła do zbioru Q (false) lub S (true)

• Tablica L[] - lista węzłów sąsiadujących z danym

• Tablica h[] - w algorytmie Astar przechowuje szacunkową drogę z danego węzła do mety

• Tablica tab[][] - tablica reprezentująca mapę gry

• tablice statyczne - brak

• dynamiczne struktury listowe, proste i zaawansowane

W swojej aplikacji użyje 1 struktury niezbędnego do utworzenia grafów.

Zawierać ona będzie:

• numer porządkowy wierzchołka (integer)

• waga krawędzi (integer)

• następny element listy (wskaźnik)

• drzewa binarne (BST, AVL, RBT) lub inne - brak

6. Rysunki uzupełniające - np. w przypadku zaawansowanych struktur listowych

2	1	0	1	1	0	1	1
1	1	0	0	0	0	1	1
1	1	1	1	1	0	0	1
1	1	1	1	0	1	0	1
0	0	0	1	0	0	1	0
1	1	1	1	1	0	1	0
1	1	0	0	0	0	1	1
1	1	0	1	1	0	1	3

Zamiana danych z tablicy w graf będzie wyglądać następująco:







cz. IV - algorytmy

7. Wykaz algorytmów, które będą zastosowane

Algorytm tworzący na podstawie tablicy liczbowej listę (nie w sensie programistycznym) krawędzi niezbędną do stworzenia grafu..

Algorytm Dijkstry.

Algorytm A*.

8. Zwięzły, poglądowy opis ważniejszych algorytmów

Algorytm A* to algorytm przeszukiwania grafu, odnajdujący najkrótszą ścieżkę pomiędzy dwoma danymi wierzchołkami grafu (lub między wierzchołkiem początkowym a dowolnym innym wierzchołkiem spełniającym dany warunek). Wykorzystuje heurystykę, przy przeszukiwaniu grafu najpierw sprawdza najbardziej obiecujące jeszcze nie odkryte wierzchołki.

W algorytmie Dijkstry pamiętany jest zbiór Q wierzchołków, dla których nie obliczono jeszcze najkrótszych ścieżek do punktu początkowego s, oraz wektor D[i] odległości od wierzchołka s do i. Początkowo zbiór Q zawiera wszystkie wierzchołki a wektor D jest pierwszym wierszem macierzy wag krawędzi A.
Algorytm przebiega następująco:

1. Dopóki zbiór Q nie jest pusty wykonuj:

2. Pobierz ze zbioru Q wierzchołek v o najmniejszej wartości D[v] i usuń go ze zbioru.

3. Dla każdego następnika i wierzchołka v dokonaj relaksacji ścieżki, tzn. sprawdź, czy D[i]>D[v]+A[v,i], tzn. czy aktualne oszacowanie odległości do wierzchołka i jest większe od oszacowania odległości do wierzchołka v plus waga krawędzi (v,i). Jeżeli tak jest, to zaktualizuj oszacowanie D[i] przypisując mu prawą stronę nierówności (czyli mniejszą wartość).

9. Sieć działań wybranych algorytmów - jeśli upraszcza lub zastępuje opis

10. Oszacowanie kosztu algorytmów (wskazane)

Złożoność czasowa algorytmu Dijkstry szacuje się na n^2. Złożoność czasowa algorytmu A* waha się miedzy n^2 a nlogn (zależnie od funkcji heurystycznej użytej w algorytmie).

cz. V - implementacja

11. Podział aplikacji na moduły i powiązania między modułami

• gen.cpp - moduł zawiera 2 funkcje: generuj oraz main

• dj.cpp - moduł zawiera funkcję dj

• a1.cpp - moduł zawiera funkcję a1

• a2.cpp - moduł zawiera funkcję a2

• mod.h - plik nagłówkowy, w którym zadeklarowana jest struktura (służąca do tworzenia grafów) oraz łączący pozostałe moduły w całość

12. Funkcje realizowane przez moduły

1. int main() - komunikuje się z użytkownikiem oraz wywołuje pozostałe funkcje

2. void generuj (int x, int y) - na podstawie parametrów formalnych (przekazujących do funkcji rozmiary mapy) „x” i „y” generuje losowo tablicę reprezentującą mapę gry (int tab[x][y]) oraz wypisuje ją w konsoli i do pliku tablica.txt. Następnie na podstawie wygenerowanej tablicy wypisuje do pliku dane_wejsciowe.txt informacje niezbędne do stworzenia grafów (położenie startu i mety oraz krawędzie i ich wagi).

3. bool dj() - wczytuje dane z pliku dane_wejsciowe.txt i na ich podstawie tworzy graf ważony. Następnie za pomocą algorytmu Dijkstry znajduje najkrótszą drogę ze startu do mety (w trakcie szukania liczy ilość relaksowanych węzłów) oraz wypisuje informację o długości drogi (lub jej braku) i jej przebieg w konsoli. W zależności od istnienia drogi funkcja zwraca wartość true/false.

4. void a1() - działa tak samo jak funkcja „void dj()”, tylko, że zamiast algorytmu Dijksty do znalezienia najkrótszej drogi ze startu do mety wykorzystuje algorytm Astar korzystający z funkcji heurystycznej liczącej odległość euklidesową między węzłami .

5. void a2() - działa tak samo jak funkcja „void dj()”, tylko, że zamiast algorytmu Dijksty do znalezienia najkrótszej drogi ze startu do mety wykorzystuje algorytm Astar korzystający z funkcji heurystycznej typu Manhattan.

1. Zmienne globalne - brak.

2. Zakres wykonywanych prac

Program prosi użytkownika o podanie danych wejściowych. Następnie wywołuje funkcje generuj oraz dj, jeśli funkcja dj zwróci wartość true (istnieje droga ze startu do mety) wywoływane są funkcje a1 i a2 (co robią poszczególne funkcje zostało opisane w punkcie 12). Po wywołaniu funkcji program pyta czy użytkownik chce wygenerować kolejną mapę. Jeśli odpowiedź jest pozytywna program czyści konsolę (komenda system(`'cls'');) oraz prosi o ponowne podanie wymiarów mapy (powrót do pytania wykonany za pomocą pętli while), jeśli negatywna program wyświetla napis końcowy i kończy pracę.

3. Opis funkcjonalności aplikacji

Pogram jest bardzo funkcjonalny. Rola użytkownika sprowadza się do podania 2 liczb z przedziału 5-39 o czym informuje instrukcja na początku programu oraz informacja przed każdym kolejnym podaniem wymiarów mapy. Program sprawdza poprawność wpisywanych danych (jedynie zakres liczbowy, jeśli użytkownik poda inne znaki niż liczby program zawiesza się). Wyniki działania wypisywane są w konsoli.

4. Załączniki

1. Pliki z kodem źródłowym:

• gen.cpp

• dj.cpp

• a1.cpp

• a2.cpp

• mod.h

1. Pliki z danymi testowymi - brak (ze względu na małą ilość danych dla poszczególnych testów umieszczę je w pierwszym wersie pliku z danymi wynikowymi).

2. Pliki z danymi wynikowymi: w folderze „testy” znajdują się pliki z danymi wynikowymi o nazwach test(n).txt (n - numer testu).

3. Pliki dodatkowe: na płycie umieściłem plik projektu gen.dev oraz wersję elektroniczną tej dokumentacji o nazwie projektZAP_dokumentacja_koncowa_Łukasz_Kinel_gr17.doc

---