====== - LAB: Przeszukiwanie grafów i 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 schematycznie 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.
* [[wp>Graph_(mathematics)]].
* [[http://pl.wikipedia.org/wiki/Graf_(matematyka)|Grafy (pl.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 być grafem skierowanym, nieskierowanym 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).
Znanych jest wiele algorytmów przeszukiwania grafów, zarówno w obszarze teorii grafów, badań operacyjnych jak i sztucznej inteligencji.
Algorytmy z obszaru sztucznej inteligencji wyróżniają się tym, że:
* często korzystają z heurystyk odległościowych (np. opartych na oszacowaniu odległości Euklidesowej i wg metryki ulicznej),
* pozwalają na uwzględnianie dodatkowych ograniczeń, np. węzłów zabronionych,
* pozwalają na przeszukiwanie przestrzeni o bardzo dużych rozmiarach,
* pozwalają na przeszukiwanie przestrzeni zadanych niejawnie (nowe węzły lub stany pojawiają się w wyniku wywołania funkcji generującej).
Zapoznaj się z podstawowymi algorytmami:
* [[http://pl.wikipedia.org/wiki/Przeszukiwanie_grafu|Algorytmy przeszukiwania w głąb i wszerz]],
* [[http://pl.wikipedia.org/wiki/Algorytm_Dijkstry|Klasycznym algorytmie 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.
===== - Szukanie w AI =====
Więcej o metodach szukania w AI można znaleźć w podręczniku
* [FCA]: [[http://artint.info/html/ArtInt_46.html|3 States and Searching]]
===== - Obsługa list w Prologu =====
Na zajęciach wykorzystujemy wbudowane predykaty do obsługi list.
Zobacz dokumentację SWI: [[http://www.swi-prolog.org/pldoc/doc_for?object=section%282,%27A.12%27,swi%28%27/doc/Manual/lists.html%27%29%29|A.12 library(lists): List Manipulation]]
Możesz też zawsze przeczytać pomoc, np. //help(append).//
----
===== - Grafy i ich reprezentacja w Prologu =====
W Prologu można reprezentować 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 grafu w Prologu ma postać:
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).
Jak widać, każda krawędź zapisywana jest w postaci relacji //d(,).//
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//.
%%% domknięcie symetryczne relacji d/2
przejazd(X,Y):- d(X,Y).
przejazd(X,Y):- d(Y,X).
Tak więc, każda krawędź umożliwia przejazd w obie strony.
==== Zadania ====
- Przerysuj pokazany graf na kartce papieru.
- Znajdź - wspomagając się rysunkiem kilka możliwych alternatywnych tras przejazdu; zaznacz je na rysunku.
- Spróbuj wyznaczyć //wszystkie// różne trasy przejazdu (nie zawierające cykli); ile ich jest?
----
===== - Poszukiwanie tras przejazdu =====
Rozważmy najprostszy program realizujący zadanie poszukiwania tras przejazdu:
%%% domknięcie tranzytywne relacji przejazd
szukaj_trasy(Cel,Cel,Trasa,Trasa):- !.
szukaj_trasy(Miasto,Cel,Robocza,Trasa):-
przejazd(Miasto,NoweMiasto),
not(member(NoweMiasto,Robocza)),
szukaj_trasy(NoweMiasto,Cel,[NoweMiasto|Robocza],Trasa).
Predykat //szukaj_trasy/4// ma 4 parametry:
* aktualny węzeł (Miasto),
* węzeł docelowy (Cel),
* cząstkową trasę aktualną (Robocza),
* trasę docelową (Trasa).
Pierwszy wariant definiuje zakończenie poszukiwań: gdy znajdziemy się w węźle docelowym, trasa Robocza staje się docelową.
Drugi wariant definiuje sposób szukania trasy:
* będąc w węźle //Miasto//, znajdź //NoweMiasto// do którego jest bezpośrednie połączenie (uzywając predykatu //przejazd/2//,
* sprawdź, czy nie było już odwiedzane (// not(member(NoweMiasto,Robocza)) //),
* jeżeli tak, zostanie wymuszony nawrót; jeżeli nie, próbuj dalej i w tym celu
* zaktualizuj trasę roboczą dokładając //NoweMiasto// i kontynuuj szukanie z tego miejsca.
Zauważ, że:
* trasy reprezentowane są jako listy,
* konstruowana ścieżka wydłuża się w miarę szukania; dokładane są nowe miasta,
* konstruowane są wszystkie warianty planu - dzięki mechanizmowi nawrotów w Prologu,
* żaden plan nie będzie zawierał cykli.
=== Zadania ===
- Uruchom podany program dla przykładowego grafu; jak zainicjować parametry?
- Zadaj w jakiej kolejności występują miasta na znalezionych trasach. Dlaczego?
- Wygeneruj przykładowy plan rozwiązania,
- Wygeneruj wszystkie możliwe plany i policz je.
----
===== - Inicjowanie programu i zliczanie rozwiązań =====
Aby ułatwić uruchamianie programu wyposażymy go w klauzulę inicjującą:
%%% inicjacja szukania
plan(Start,Cel,Trasa):-
szukaj_trasy(Cel,Start,[Cel],Trasa).
Zauważ, że //Start// i //Cel// zamieniły się miejscami. Dlaczego?
Aby wyznaczyć automatycznie wszystkie plany uzupełnimy program o klauzulę:
%%% Find all plans from 's' to 'g'.
fap(Plans) :- findall(Trasa, plan(s,g,Trasa),Plans).
Aby wyznaczyć automatycznie wszystkie plany i zapisać je do pamięci uzupełnimy program o klauzulę:
%%% Find all plans and assert; p().
fap-assert:- plan(s,g,Plan), assert(p(Plan)), fail.
fap-assert.
Jaka to konstrukcja? Na czym polega jej działanie?
Pełny program znajdziesz tutaj: {{:pl:prolog:prolog_lab:plan-robust-count.pl|}}
==== Zdania ====
- Przeanalizuj elementy i działanie programu.
- Jaka jest kolejność węzłów w wygenerowanych planach?
- W jakiej kolejności (w jakim kierunku) odbywa się rzeczywista generacja planów?
- Policz ile jest planów dopuszczalnych (programowo) i porównaj wynik z rozwiązaniem ręcznym.
- Zmodyfikuj program tak, aby dla każdego planu wyznaczał jego długość (ilość odwiedzanych węzłów).
- Zastanów się jak zrealizować (a może nawet spróbuj) analogiczny program w //Twoim ulubionym języku programowania// (np. Java, C++, Python). Porównaj nakład pracy z kodowaniem w Prologu.
----
===== - Szukanie tras przejazdu pomiędzy miastami w Polsce =====
Załączony program pozwala poszukiwać tras przejazdy pomiędzy wybranymi miastami w Polsce.
Prosty program planowania tras przejazdu: {{:pl:prolog:prolog_lab:plan.pl}}
Przeanalizuj działanie programu.
Rozbuduj jego bazę wiedzy - dodaj nowe miasta.
Wypróbuj działanie.
==== Zadania ====
- Zmodyfikuj program tak, aby generowane plany omijały wybrane (zadeklarowane) miasta zabronione,
- Zmodyfikuj program tak, aby generowane plany uwzględniały przejazd przez wybrane (zadeklarowane) miasta konieczne do odwiedzenia,
- Zmodyfikuj program tak, aby generowane były jedynie plany o ograniczonej długości (liczba odwiedzanych miast.
----
===== - Szukanie DFS z wyznaczeniem głębokości =====
Następujący program pozwala wyszukiwać trasy metodą wgłąb (go) i wgłąb z wyliczaniem głębokości.
{{:pl:prolog:prolog_lab:depth-first-plan.pl}}
===== - Wyznaczanie długości trasy =====
Następujący program pozwala wyznaczać długość znalezionych tras.
{{:pl:prolog:prolog_lab:plan_d.pl}}
==== Zadania ====
- Uruchom program i przeanalizuj jego działanie.
- Modyfikując ograniczenie znajdź wybrane trasy optymalne dla zadanego miasta początkowego i docelowego.
- Zmodyfikuj program tak aby automatycznie modyfikował ograniczenie i znajdował trasę optymalną.
----
===== - Znajdowanie trasy optymalnej =====
Następujący program pozwala automatycznie wyznaczać długość znalezionych tras oraz trasę optymalną (branch and bound).
Wyznaczanie trasy optymalnej: {{:pl:prolog:prolog_lab:plan_d_opt.pl}}
Przeanalizuj program i jego działanie.
Czy zaproponowana metoda jest efektywna? Na czym polegają jej niedoskonałości i ograniczenia?
----
===== - Znajdowanie trasy optymalnej z wykorzystaniem nawrotów =====
Następujący program pozwala wyznaczać długość znalezionych tras oraz znajduje trasę optymalna z wykorzystaniem mechanizmu nawrotów w Prologu.
Planowanie trasy optymalne z nawrotami: {{:pl:prolog:prolog_lab:plan_f.pl}}
==== Zadania ====
- Przeanalizuj szczegółowo działanie programu; wyświetlaj znalezione trasy.
- Porównaj efektywność tego programu z poprzednim na wybranych przykładach (użyj meta predykatu //time/1//).
----
===== - Przeszukiwanie wszerz =====
Następujący program pozwala wyznaczać plan metodą wszerz (BFS)
{{:pl:prolog:prolog_lab:breadth-first-plan.pl}}
==== Zadania ====
- Przeanalizuj szczegółowo działanie programu; wyświetlaj znalezione trasy.
- Porównaj efektywność tego programu z poprzednim na wybranych przykładach (użyj meta predykatu //time/1//).
===== - Szukanie heurystyczne tras =====
Przeanalizuj działanie programu.
Heurystyka jest zadana w ''szukaj_trasy''.
Porównaj z wcześniejszymi alg. szukania.
{{:pl:prolog:prolog_lab:traser.pl|}}
===== - Szukanie heurystyczne A* dla 8puzzle =====
Program {{:pl:prolog:prolog_lab:bratko-fig12_3f.pl|}} implementuje algorytm [[wp>A*]].
Zobacz też: [[http://artint.info/html/ArtInt_56.html]]
Sam program wymaga podania opisu problemu przez predykat ''s(N,M,C).'':
* N bieżący stan w przestrzeni stanów
* M następny stan
* C koszt N->M
Wymagane jest też podanie heurystyki ''h(N,H)'' - gdzie H to heurystyczna estymacja kosztu najlepszej trasy z N do celu.
Poczytaj o [[wp>8-puzzle]].
W opisie tego problemu używamy innej miary odległości niż np. na drodze, tzw. odległości taksówkarskiej
[[wp>Manhattan_distance]]
Program {{:pl:prolog:prolog_lab:bratko-fig12_6.pl|}} implementuje opis tego problemu do rozwiązania przez w.w. algorytm [[wp>A*]].
Przykładowe wywołanie:
?- start1( Pos), bestfirst( Pos, Sol), showsol( Sol).
Zobacz rozwiązania dla inne stanów startowych.
- dodaj inne stany startowe
- dodaj liczenie kroków.
- jakie mogą być inne heurystyki?
- jak użyć tego programu do tras na mapie (miasta)? czy potrafisz opisać/przenieść problem z wcześniejszych zadań (mapa miast w Polsce).
===== - Szukanie -- wizualizacja =====
Spróbuj zrealizować wizualizację grafu dla tras przez program Graphviz.
Vide: programy w
[[pl:prolog:prolog_lab:prolog_lab_system#metaprogramowanie_i_potoki]]
===== - Szukanie -- synteza =====
Przeczytaj lab [[pl:prolog:prolog_lab:classicsearch]].
Spróbuj użyć programu [[http://www.aispace.org/search/|AIspace: search]]
najprościej [[http://www.aispace.org/search/version4.5.3/search.jar|wersji JAR]].
----
===== If u want 2 know more vel zadanie domowe =====
* należy wiedzieć na czym polega problem TSP: [[wp>Travelling_salesman_problem]]
* jak się go formalizuje z użyciem grafów [[wp>Travelling_salesman_problem#As_a_graph_problem]]
* dlaczego jest ważny, np. z punktu widzenia złożoności obliczeniowej [[wp>Travelling_salesman_problem#As_a_graph_problem/complex]]
* czym jest ścieżka Hamiltona [[wp>Hamiltonian_cycle]]