Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:prolog:prolog_lab:prolog_lab_graphsearch [2013/04/10 07:23] gjn [9 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 ====== | |
| ====== - 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. | 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. |
* 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).// |
| |
---- | ---- |
Następujący program pozwala wyszukiwać trasy metodą wgłąb (go) i wgłąb z wyliczaniem 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:breadth-first-plan.pl}} | {{:pl:prolog:prolog_lab:depth-first-plan.pl}} |
| |
===== - Wyznaczanie długości trasy ===== | ===== - Wyznaczanie długości trasy ===== |
---- | ---- |
| |
| ===== - 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]] |
| |