|
|
pl:prolog:prolog_lab:prolog_lab_graphsearch [2013/04/17 07:18] gjn heurystyki |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2019/06/27 15:50] |
| |
====== - 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ć: | |
| |
<code prolog> | |
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ł_początkowy>,<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 prolog> | |
%%% domknięcie symetryczne relacji d/2 | |
przejazd(X,Y):- d(X,Y). | |
przejazd(X,Y):- d(Y,X). | |
</code> | |
| |
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: | |
| |
<code prolog> | |
%%% 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). | |
</code> | |
| |
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ą: | |
| |
<code prolog> | |
%%% inicjacja szukania | |
plan(Start,Cel,Trasa):- | |
szukaj_trasy(Cel,Start,[Cel],Trasa). | |
</code> | |
| |
Zauważ, że //Start// i //Cel// zamieniły się miejscami. Dlaczego? | |
| |
Aby wyznaczyć automatycznie wszystkie plany uzupełnimy program o klauzulę: | |
| |
<code prolog> | |
%%% Find all plans from 's' to 'g'. | |
fap(Plans) :- findall(Trasa, plan(s,g,Trasa),Plans). | |
</code> | |
| |
Aby wyznaczyć automatycznie wszystkie plany i zapisać je do pamięci uzupełnimy program o klauzulę: | |
| |
<code prolog> | |
%%% Find all plans and assert; p(<plan>). | |
fap-assert:- plan(s,g,Plan), assert(p(Plan)), fail. | |
fap-assert. | |
</code> | |
| |
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. | |
| |
===== - 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]] | |
| |