Student: Michał Siatkowski gr. 12 Warszawa, 26.03.08

Prowadzący: Michał Syfert

termin zajęć: środa godz. 10.15-11.00

Zasady programowania strukturalnego - projektowanie

Projekt aplikacji

Temat Projektu:

4.3

Taksówkarz Realizacja programu wyznaczającego najkrótszą drogę pomiędzy dwoma punktami na mapie ulic. Założenia: mapa połączeń drogowych definiowana jest przez podanie współrzędnych (całkowitych) skrzyżowań, drogi definiowane są jako połączenie: skrzyżowanie - skrzyżowanie wraz z określeniem kierunku jazdy (z, do, dwukierunkowa).

Założenia dodatkowe:

1. Na każdym skrzyżowaniu stoi znak z ograniczeniem prędkości, biorąc pod uwagę różne prędkości na poszczególnym drogach, algorytm będzie wyszukiwał drogę najkrótszą(tak jak w podstawowych założeniach i dodatkowo po zmianie trybu drogę najszybszą od skrzyżowania A do B.

2. Program będzie posiadał opcje generowania losowej mapy o podanym rozmiarze.

3. Program będzie posiadał opcje zapisu wygenerowanej mapy z klawiatury do pliku z którego potem może ją wczytać a starą mapę będzie zachowywał w pliku kosz1.xat, kosz2.xat . (prog. przechowuje 2 mapy)

Krótka Charakterystyka

Program musi wyświetlać menu w którym użytkownik będzie miał dostęp do konfiguracji opcji programu (takich jak tryb szybki, wolny itd.) Gdy użytkownik ustawi dogodne dla siebie ustawienia może uruchomić działanie programu. Wpierw program do działania potrzebuje mapy która może otrzymać na 3 sposoby: z pliku, z klawiatury bądź wygenerowaną losowo. Mapa składa się z dwóch „struktur” tablicy dynamicznej skrzyżowań oraz macierzy sąsiedztwa skrzyżowań, które są odpowiednikiem węzłów w grafie. Informacje z macierzy będą przepisywane do listy sąsiedztwa na której bezpośrednio działa algorytm. Cała mapa ma więc strukturę grafu skierowanego. Następnie program posługując się algorytmem Dijkstry znajduje najkrótszą bądź najszybszą drogę między dwoma wcześniej wybranymi skrzyżowaniami. Na koniec wyświetla wynik i umożliwia zapisanie wyników na wyjściu do pliku.

1.Opis algorytmu:

Algorytm Dijkstry

Jest to klasyczny algorytm służący do wyznaczania najmniejszej odległości od jednego ustalonego wierzchołka grafu r (może być on skierowany lub nie) do wszystkich pozostałych wierzchołków, lecz może być wykorzystany w prosty sposób do wyznaczania najkrótszej drogi miedzy dwoma wierzchołkami grafu - jest on najbardziej znanym algorytmem poszukiwania najkrótszej drogi w grafie. Jedynym ograniczeniem w tym algorytmie jest dysponowanie grafem o dodatnich wagach, ale w przypadku zastosowań typu kartografia ograniczenie to nie ma specjalnego znaczenia.

Algorytm ten jest algorytmem zachłannym a jego nazwa pochodzi od nazwiska twórcy -holenderskiego informatyka Edsgera Dijkstry.

Złożoność czasowa algorytmu Dijkstry szacuje się miedzy O(V²) a O(E + VlogV) w zależności od implementacji. (w tym przypadku będzie to O(V2) ponieważ algorytm wykorzystuje proste liniowe porównania)

Opis implementacji algorytmu w postaci pseudokodu:

Procedura Dijkstra (graf G, węzeł źródłowy r):

S - zbiór pusty  

Q - zbiór pusty  

for (każdy węzeł i grafu G(V, E) )

 { 

    D[i] = nieskończoność    //tablica D przechowująca wartości aktualnie najkrótszej   

                //ścieżki od źródła do węzła i  

  

    P[i] = 0      //tablica P przechowująca indeks węzła, który jest   

             //poprzednikiem węzła  i  na najkrótszej ścieżce od źródła do  i    

}  

dodaj źródło (węzeł) r do zbioru Q  

D[r] = 0  

  

while (zbiór Q nie jest pusty)

 {  

    wybierz ze zbioru Q wierzchołek o indeksie i, dla którego wartość D[i] będzie najmniejsza        dodaj wierzchołek i do zbioru S  

  

    for (każdy wierzchołek j sąsiadujący z wierzchołkiem i, który nie należy do S)       

    if  (D[i] +w[i,j] < D[j])   //tzw. Relaksacja, sprawdzamy czy bieżące oszacowanie   

      {                   //najkrótszej drogi do i (tzn. D[i]) może zostać ulepszona

          D[j] = D[i] +w[i,j]              //jeśli przejdziemy przez j (j zostaje poprzednikiem i)

           P[j] = i                

          dodaj węzeł j do zbioru Q  

      }

}

Przykładowe zobrazowanie algorytm w toku swojej pracy.

Źródło to żółty węzeł i algorytm oblicza dla każdego innego węzła najkrótszą drogę od źródła, na końcu wskazujemy do jakiego punktu chcemy dotrzeć i otrzymujemy ze zbioru wyników jeden ten który chcieliśmy otrzymać - najkrótszą drogę do podanego ujścia.

Dla węzłów zielonych i czerwonego drogi są porównane i obliczone, a dla fioletowego i białego dopiero będą.

Bibliografia: http://pl.wikipedia.org/wiki/Algorytm_Dijkstry , 

Algorytmy i Struktury Danych, Barbara Putz, Andrzej Putz jr., Paweł Wnuk

Algorytmy - struktury danych i techniki programowania, Piotr Wróblewski

Aplet który obrazuje działanie algorytmu: http://iair.mchtr.pw.edu.pl/bputz/aisd_cpp/lekcja7/segment3/main_dijkstra.htm

2.Wykaz struktur danych przewidzianych w aplikacji i informacje, jakie dane będą w nich

-struktura o nazwie „cross” określającą skrzyżowania na którą składa się:

struct cross

{

int id; //numer porządkowy skrzyżowania

int x, y; //współrzędne całkowite

bool jest; //zmienna logiczna, ułatwiająca sprawdzenie istnienia skrzyżowania w danym miejscu na planszy

double v; //wartość prędkości obowiązującej na trasie do następnego skrzyżowania

};

-struktura o nazwie „sWezel” określającą drogę (krawędź w grafie) na którą składa się:

struct sWezel (przechowuje dane w liście sąsiedztwa)

{

int numer; // numer wierzchołka

float waga; // waga krawędzi

sWezel *next; // następny element listy

};

-tablica dynamiczna (o rozmiarze n*n)

są w niej przechowywane informacje o skrzyżowaniach

-macierz sąsiedztwa ( o rozmiarze M*M, gdzie: M=n*n)

są w niej przechowywane informacje o tym połączeniach(drogach) miedzy skrzyżowaniami długości dróg oraz informacje o tym czy droga jest jedno czy dwukierunkowa, macierz ta ze wzgledu na swoja przejrzystość służy do wyświetlania na ekranie, zapisywania i wczytywania z plików wyników.

-lista sąsiedztwa (grafu skierowanego)

są do niej przepisywane informacje o drogach z macierzy sąsiedztwa i dalej w tej postaci przechowywane informacje wykorzystuje algorytm Dijkstry

3.Podział na moduły

Krótki opis zawartości poszczególnych modułów(gdzie znajdują się definicje funckji):

Taxi.cpp - zawiera funkcje main

main();

Data.cpp / .h - funkcje tworzące struktury danych, zapisuje ustworzoną mape do plikow

struct cross

{

int id;

int x, y; //struktura

bool jest;

double v;

};

extern n;

extern M;

extern float **W;

void start();

void pokaz_macierz(float**);

void macierz(cross**);

void kopiuj_plik(string Sname1, string Sname2)

void zapisz_macierz(float **w, string nazwa, string kosz)

void zapisz_mape_a(cross **a, string opcja, string nazwa, string kosz)

Map.cpp / .h - funckje tworzące mape, laduje mape z plikow

void pokaz_mape(cross**);

void pokaz_mape_id(cross**);

void zerowanie_mapy(cross);

void gen_map_kl();

void gen_map_plk();

void mapa();

void load_W(string nazwa);

void load_a(string opcja, string nazwa)

Interface.cpp / .h - funkcje wyswietlajace menu, konfiguracje ustawien, itd.

void show_menu();

void zmien_tryb();

void zmien_droge();

void zmien_mape();

void o_prog();

void menu();

Algo.cpp / .h - funkcje na które sklada się właściwe działanie głównego algorytmu

struct sWezel //struktura listy sąsiedztwa grafu skierowanego

{

int numer; // numer wierzchołka

float waga; // waga krawędzi

sWezel *next; // następny element listy

};

void dijkstra(float**); //główny algorytm

void dijkstra_krokowo(float**); //główny algorytm krokowo

4.Interfejs użytkownika

Struktura Menu

MENU GLOWNE

1 ->Start aplikacji

2 - Zmień tryb działania 1.tryb krok po kroku(z podglądem) 2.tryb szybki (bez podglądu)

3 - Sposób wczytywania mapy 1.wczytaj z pliku 2.wczytaj z klawiatury 3.generuj losowo mapę

4 - Sposób znajdowania drogi 1.znajdowanie drogi najkrótszej 2.znajdowanie drogi najszybszej

5 - O Programie

6 - Wyjście

5.wejście/wyjście

pliki wejścia-wyjścia: rozsz. plików wejścia: .tax

mapa1.tax macierz sąsiedztwa (wagi)

mapa2.tax tablica „cross.id” ) //pliki mapa_.tax - przechowują ostatnio zapisaną mape

mapa3.tax tablica „cross.x” - współrzędne x skrzyżowań

mapa4.tax tablica “cross.y” -wpólrzedne y skrzyżowan

mapaV.tax tablica przechowująca czasy przebycia dróg

mapa.tax w tych plikach przechowywane są bieżące ustawienia w menu programu

tryb.tax

droga.tax

pliki wyjscia-wejścia: rozsz. plików wyjścia: .xat

kosz1.xat macierz sąsiedztwa (wagi)

kosz2.xat tablica „cross.id” //pliki kosz_.xat - przechowują „starą” mape

kosz3.xat tablica „cross.x” - współrzędne x skrzyżowań

kosz4.xat tablica “cross.y” -wpólrzedne y skrzyżowan

koszV.xat tablica przechowująca czasy przebycia dróg

temp.xat - przechowuje znalezione najkrótsze bądź najszybsze połączenie przez algorytm

plik wyjścia:

wyniki.xat plik zawierający pożądane wyniki działania programu

6. Sytuacje Wyjątkowe

Program obsługuje jak dotąd wszystkie napotkane sytuacje wyjątkowe poprzez wyświetlenia na ekran że wpisana wartość dla danej zmiennej jest błędna i wymusza na użytkowniku podanie dobrej wartości, dopóki użytkownik nie poda poprawnej wartości program będzie ciągle prosił o poprawną - niezbędną do dalszego poprawnego działania algorytmu głównego.

Przykład - reakcja programu na sytuację wyjątkową:

cerr << "nie ma takiego połączenia, zdefiniuj poprawnie połączenie (nr.sk1(spacja)nr.sk2)" << endl

//powyższy komunikat wewnątrz np. pętli while, do-while które wymuszają podanie poprawnej wartości

7. Zaplanowane testu i przewidywane wyniki

Test będzie przeprowadzany na różnych rodzajach map: małej (2x2), średniej (3x3), dużej (4x4), bardzo dużej (5x5) i w mapach ty będzie różne zagęszczenie połączeń tak by algorytm mógł pokazać swoja szybkość i sprawdzić się w różnych warunkach.

Przewidywane wyniki:

wskazanie najkrótszej drogi miedzy 2 wybranymi połączeniami (tryb szybki)

wskazanie najkrótszych dróg do każdego punktu od źródła i śledzenie za pomocą wyświetlanych informacji o przebiegu algorytmu (np. porównywanie długości połączeń) a następnie wybranie jednego rozwiązania dla konkretnego skrzyżowania końcowego (ujścia)

taxi.cpp(main( ))

data.cpp

data.h

algo.cpp

algo.h

map.cpp

map.h

interface.cpp

interface.h

---