Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:prolog_lab:prolog_lab_graphsearch [2009/11/29 16:28] ligeza |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== - LAB: Planowanie tras przejazdu ====== | ||
| - | |||
| - | Celem ćwiczenia jest zapoznanie się z możliwościami wykorzystania Prologu do planowania tras przejazdu oraz poznanie technik poszukiwania ścieżek w grafach i ich implementacji w Prologu. | ||
| - | |||
| - | |||
| - | ===== Wprowadzenie ===== | ||
| - | |||
| - | Modelem przestrzeni poszukiwań dla planowania tras przejazdu jest graf. | ||
| - | |||
| - | Graf to twór matematyczny składający się ze zbioru wierzchołków //V// (ang. nodes, vertices) oraz zbioru krawędzi //E// (ang. links, edges). | ||
| - | |||
| - | Najprostsza definicja grafu mówi, że graf to para postaci //G=(V,E)//, gdzie //V// jest zbiorem węzłów a //E ⊆ V×V// jest zbiorem łączących je krawędzi. | ||
| - | |||
| - | Model ten reprezentuje schmatycznie mapę, gdzie w zależności od poziomu abstrakcji węzły mogą np. reprezentować miasta, a krawędzie - łączące je drogi, lub też węzły mogą reprezentować skrzyżowania ulic a krawędzie ulice (lub ich odcinki). | ||
| - | |||
| - | Zapoznaj się, lub raczej przypomnij sobie ;-) podstawowe wiadomości o grafach. | ||
| - | |||
| - | * [[http://pl.wikipedia.org/wiki/Graf_(matematyka)|Grafy (pl.wikipedia.org)]], | ||
| - | * [[http://en.wikipedia.org/wiki/Graph_(mathematics)|Graph (ew.wikipedia.org)]]. | ||
| - | |||
| - | Pamiętaj, że krawędź grafu może być //skierowana// (modeluje przejazd tylko w jedną stronę; np. ulica jednokierunkowa) lub //nieskierowanym// (modeluje przejazd w obie strony; np. ulica dwukierunkowa). | ||
| - | |||
| - | Odpowiednio, graf może byc grafem skierowanym, nieskierownym lub mieszanym. | ||
| - | |||
| - | Ponadto, z każdą krawędzią może być związany koszt przejazdu (odległość, czas). | ||
| - | |||
| - | Jeżeli dwa węzły grafu połączone są więcej niż jedną krawędzią, krawędzie te muszą być etykietowane dla umożliwienia ich rozróżnienia. | ||
| - | |||
| - | ---- | ||
| - | |||
| - | ===== Poszukiwanie ścieżek ===== | ||
| - | |||
| - | Zadanie planowania tras przejazdu to zadanie polegające na wyznaczeniu drogi łączącej zadany punkt początkowy i pożądany punk docelowy. | ||
| - | |||
| - | Zwykle dążymy do wyznaczenia trasy najkrótszej, najszybszej lub o najniższym koszcie. | ||
| - | |||
| - | Modelem zadania planowania trasy jest //poszukiwanie ścieżki w grafie//. | ||
| - | |||
| - | Zadania planowania trasy definiowane jest jako: | ||
| - | |||
| - | //P = (v_I, v_G, V, E)// | ||
| - | |||
| - | gdzie //v_I// to zadany węzeł początkowy, //v_G// to zadany węzeł docelowy, a //V// oraz //E// definiują graf (przestrzeń poszukiwań). | ||
| - | |||
| - | |||
| - | Rozwiązaniem zadania planowania trasy jest ciąg krawędzi //e_1, e_2,...,e_n//, taki, że: | ||
| - | |||
| - | * //{e_1, e_2,...,e_n} ⊆ E//, | ||
| - | * //e_1// zaczyna się węźle //v_I//, | ||
| - | * krawędź //e_i// kończy się w węźle będącym początkiem krawędzi //e_i+1//, | ||
| - | * krawędź //e_n// kończy się w węźle //v_G//. | ||
| - | |||
| - | Powyższy ciąg krawędzi tworzy //ścieżkę// stanowiącą plan przejazdu. | ||
| - | |||
| - | Zwykle wymaga się aby każdy węzeł leżący na ścieżce przejazdu odwiedzany był tylko raz (brak cykli). | ||
| - | |||
| - | Zanych jest wiele algorytmów przeszukiwania grafów. | ||
| - | |||
| - | Zapoznaj się z podstawowymi algorytmami: | ||
| - | |||
| - | * [[http://pl.wikipedia.org/wiki/Przeszukiwanie_grafu|Algorytmy przeszykiwania w głąb i wszerz]], | ||
| - | * [[http://pl.wikipedia.org/wiki/Algorytm_Dijkstry|Klasycznym algorytme Dijkstry i //problemem najkrótszej ścieżki//]], | ||
| - | * [[http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol009.php|Elegancką prezentacją algorytmu Dijkstry]]. | ||
| - | |||
| - | Plan //dopuszczalny// to plan stanowiący rozwiązanie (ścieżka łącząca węzeł początkowy i docelowy) i ew. spełniający zadane ograniczenia (np. długości, omijania wybranych węzłów zabronionych, przechodzenia przez zadane węzły wymagające odwiedzenia, etc. Plan ten nie musi być 'najlepszy'. | ||
| - | |||
| - | Plan //optymalny// to plan najlepszy w sensie wybranego kryterium, np. | ||
| - | * plan zawierający najmniejszą liczbę węzłów, | ||
| - | * plan realizujący najkrótszą trasę, | ||
| - | * plan o najtańszej trasie przejazdu, | ||
| - | * plan pozwalający na najszybszy przejazd. | ||
| - | |||
| - | ---- | ||
| - | |||
| - | |||
| - | ===== Grafy i ich preprezentacja w Prologu ===== | ||
| - | |||
| - | W Prologu można reprezentowac grafy na kilka sposobów. | ||
| - | |||
| - | Najprostszą i efektywną metodą jest zadeklarowanie połączeń pomiędzy węzłami grafu w postaci faktów w Prologu. | ||
| - | |||
| - | Rozważmy następujący graf: | ||
| - | |||
| - | {{:pl:prolog:prolog_lab:optimal-vs-robust.png|Przykład grafu - model połączeń drogowych}} | ||
| - | |||
| - | |||
| - | {{:pl:prolog:prolog_lab:optimal-vs-robust.pdf|Przykład grafu - model połączeń drogowych (.pdf)}} | ||
| - | |||
| - | W grafie tym istnieje jedna ścieżka optymalna (lewa krawędź) oraz wiele ścieżek dopuszczalnych przechodzących przez węzły n1-n6. | ||
| - | |||
| - | Reprezentacja tego grafy w Prologu ma postać: | ||
| - | |||
| - | <code> | ||
| - | d(s,g). | ||
| - | d(s,n1). | ||
| - | d(s,n2). | ||
| - | d(n1,n2). | ||
| - | d(n1,n4). | ||
| - | d(n1,n3). | ||
| - | d(n2,n3). | ||
| - | d(n3,n4). | ||
| - | d(n3,n5). | ||
| - | d(n4,n5). | ||
| - | d(n4,n6). | ||
| - | d(n5,n6). | ||
| - | d(n6,g). | ||
| - | </code> | ||
| - | |||
| - | Jak widać, każda krawędź zapisywana jest w postaci relacji //d(<węzeł_poczatkowy>,<węzeł_końcowy>).// | ||
| - | |||
| - | W przykładowym grafie istnieje 13 krawędzi. Zgodnie z deklaracją w Prologu, są to krawędzie //skierowane// (dlaczego | ||
| - | |||
| - | Aby zadeklarować możliwość przejazdu w obie strony, należy zdefiniować //domknięcie symetryczne// relacji połączenie //d/2//. | ||
| - | |||
| - | <code> | ||
| - | %%% domknięcie symetryczne relacji d/2 | ||
| - | |||
| - | przejazd(X,Y):- d(X,Y). | ||
| - | |||
| - | przejazd(X,Y):- d(Y,X). | ||
| - | </code> | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
| - | |||
