Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:prolog:prolog_lab:prolog_lab_graphsearch [2013/04/10 07:07] gjn [Znajdowanie trasy optymalnej] |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2013/04/17 07:21] gjn [15 Szukanie heurystyczne A* dla 8puzzle] |
====== - 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. | ====== - 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 ===== | ===== - Wprowadzenie ===== |
| |
Modelem przestrzeni poszukiwań dla planowania tras przejazdu jest graf. | Modelem przestrzeni poszukiwań dla planowania tras przejazdu jest graf. |
Zapoznaj się, lub raczej przypomnij sobie ;-) podstawowe wiadomości o grafach. | 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)]], | * [[http://pl.wikipedia.org/wiki/Graf_(matematyka)|Grafy (pl.wikipedia.org)]], |
* [[http://en.wikipedia.org/wiki/Graph_(mathematics)|Graph (en.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). | 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). |
---- | ---- |
| |
===== Poszukiwanie ścieżek ===== | ===== - 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. | Zadanie planowania tras przejazdu to zadanie polegające na wyznaczeniu drogi łączącej zadany punkt początkowy i pożądany punk docelowy. |
* pozwalają na przeszukiwanie przestrzeni o bardzo dużych rozmiarach, | * 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). | * pozwalają na przeszukiwanie przestrzeni zadanych niejawnie (nowe węzły lub stany pojawiają się w wyniku wywołania funkcji generującej). |
| |
| |
| |
| |
| |
| |
* [[http://pl.wikipedia.org/wiki/Przeszukiwanie_grafu|Algorytmy przeszukiwania w głąb i wszerz]], | * [[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://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]]. | * [[http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol009.php|Elegancką prezentacją algorytmu Dijkstry]]. |
| |
* plan o najtańszej trasie przejazdu, | * plan o najtańszej trasie przejazdu, |
* plan pozwalający na najszybszy przejazd. | * 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 ===== | ===== - Grafy i ich reprezentacja w Prologu ===== |
| |
W Prologu można reprezentować grafy na kilka sposobów. | W Prologu można reprezentować grafy na kilka sposobów. |
| |
{{:pl:prolog:prolog_lab:optimal-vs-robust.png|Przykład grafu - model połączeń drogowych}} | {{: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)}} | {{: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. | 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ć: | Reprezentacja tego grafu w Prologu ma postać: |
| |
<code> | <code prolog> |
d(s,g). | d(s,g). |
d(s,n1). | d(s,n1). |
Aby zadeklarować możliwość przejazdu w obie strony, należy zdefiniować //domknięcie symetryczne// relacji połączenie //d/2//. | Aby zadeklarować możliwość przejazdu w obie strony, należy zdefiniować //domknięcie symetryczne// relacji połączenie //d/2//. |
| |
<code> | <code prolog> |
%%% domknięcie symetryczne relacji d/2 | %%% domknięcie symetryczne relacji d/2 |
przejazd(X,Y):- d(X,Y). | przejazd(X,Y):- d(X,Y). |
| |
| |
== Zadania == | ==== Zadania ==== |
| |
- Przerysuj pokazany graf na kartce papieru. | - Przerysuj pokazany graf na kartce papieru. |
---- | ---- |
| |
===== Poszukiwanie tras przejazdu ===== | ===== - Poszukiwanie tras przejazdu ===== |
| |
Rozważmy najprostszy program realizujący zadanie poszukiwania tras przejazdu: | Rozważmy najprostszy program realizujący zadanie poszukiwania tras przejazdu: |
| |
<code> | <code prolog> |
%%% domknięcie tranzytywne relacji przejazd | %%% domknięcie tranzytywne relacji przejazd |
szukaj_trasy(Cel,Cel,Trasa,Trasa):- !. | szukaj_trasy(Cel,Cel,Trasa,Trasa):- !. |
---- | ---- |
| |
===== Inicjowanie programu i zliczanie rozwiązań ===== | ===== - Inicjowanie programu i zliczanie rozwiązań ===== |
| |
Aby ułatwić uruchamianie programu wyposażymy go w klauzulę inicjującą: | Aby ułatwić uruchamianie programu wyposażymy go w klauzulę inicjującą: |
| |
<code> | <code prolog> |
%%% inicjacja szukania | %%% inicjacja szukania |
plan(Start,Cel,Trasa):- | plan(Start,Cel,Trasa):- |
Aby wyznaczyć automatycznie wszystkie plany uzupełnimy program o klauzulę: | Aby wyznaczyć automatycznie wszystkie plany uzupełnimy program o klauzulę: |
| |
<code> | <code prolog> |
%%% Find all plans from 's' to 'g'. | %%% Find all plans from 's' to 'g'. |
fap(Plans) :- findall(Trasa, plan(s,g,Trasa),Plans). | 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ę: | Aby wyznaczyć automatycznie wszystkie plany i zapisać je do pamięci uzupełnimy program o klauzulę: |
| |
<code> | <code prolog> |
%%% Find all plans and assert; p(<plan>). | %%% Find all plans and assert; p(<plan>). |
fap-assert:- plan(s,g,Plan), assert(p(Plan)), fail. | fap-assert:- plan(s,g,Plan), assert(p(Plan)), fail. |
Pełny program znajdziesz tutaj: {{:pl:prolog:prolog_lab:plan-robust-count.pl|}} | Pełny program znajdziesz tutaj: {{:pl:prolog:prolog_lab:plan-robust-count.pl|}} |
| |
=== Zdania === | ==== Zdania ==== |
| |
- Przeanalizuj elementy i działanie programu. | - Przeanalizuj elementy i działanie programu. |
---- | ---- |
| |
===== Szukanie tras przejazdu pomiędzy miastami w Polsce ===== | ===== - Szukanie tras przejazdu pomiędzy miastami w Polsce ===== |
| |
Załączony program pozwala poszukiwać tras przejazdy pomiędzy wybranymi miastami w Polsce. | Załączony program pozwala poszukiwać tras przejazdy pomiędzy wybranymi miastami w Polsce. |
Wypróbuj działanie. | Wypróbuj działanie. |
| |
=== Zadania === | ==== Zadania ==== |
| |
- Zmodyfikuj program tak, aby generowane plany omijały wybrane (zadeklarowane) miasta zabronione, | - Zmodyfikuj program tak, aby generowane plany omijały wybrane (zadeklarowane) miasta zabronione, |
---- | ---- |
| |
===== Wyznaczanie długości trasy ===== | ===== - 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. | Następujący program pozwala wyznaczać długość znalezionych tras. |
| |
Program wyznaczający długość trasy: {{:pl:prolog:prolog_lab:plan_d.pl}} | {{:pl:prolog:prolog_lab:plan_d.pl}} |
| |
=== Zadania === | ==== Zadania ==== |
| |
- Uruchom program i przeanalizuj jego działanie. | - Uruchom program i przeanalizuj jego działanie. |
---- | ---- |
| |
===== Znajdowanie trasy optymalnej ===== | ===== - Znajdowanie trasy optymalnej ===== |
| |
Następujący program pozwala automatycznie wyznaczać długość znalezionych tras oraz trasę optymalną. | 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}} | Wyznaczanie trasy optymalnej: {{:pl:prolog:prolog_lab:plan_d_opt.pl}} |
| |
| |
===== Znajdowanie trasy optymalnej z wykorzystaniem nawrotów ===== | ===== - 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. | 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}} |
| |
{{:pl:prolog:prolog_lab:plan_f.pl|Planowanie trasy optymalne z nawrotami}} | ==== 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//). |
| |
=== Zadania === | ---- |
| |
| ===== - 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. | - 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//). | - 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]] |
| |