Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:prolog:prolog_lab:prolog_lab_graphsearch [2013/04/10 12:34] gjn [3 Szukanie w AI] |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2019/06/27 15:50] (aktualna) |
| |
====== - LAB: Przeszukiwanie grafów i planowanie tras przejazdu ====== | ====== - LAB: Przeszukiwanie grafów i planowanie tras przejazdu ====== |
| |
===== - Szukanie w AI ===== | ===== - Szukanie w AI ===== |
| |
* proszę poczytać o metodach szukania w AI można znaleźć w podręczniku [FCA]: [[http://artint.info/html/ArtInt_46.html|3 States and Searching]] 3.6-3-7 | 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 ===== | ===== - Obsługa list w Prologu ===== |
- 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]]. |
| |
| |
| |
---- | ---- |