To jest stara wersja strony!
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.
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.
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.
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:
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:
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.
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:
