Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:prolog:prolog_lab:prolog_lab_graphsearch [2013/04/10 07:23] gjn [7 Wyznaczanie długości trasy] |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== - 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. | ||
| Linia 76: | Linia 77: | ||
| * 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).// | ||
| ---- | ---- | ||
| Linia 246: | Linia 259: | ||
| 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 ===== | ||
| Linia 264: | Linia 277: | ||
| ===== - 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}} | ||
| Linia 289: | Linia 302: | ||
| ---- | ---- | ||
| + | ===== - 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]] | ||
