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 12:38] gjn przywrócono poprzednią wersję |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 312: | Linia 312: | ||
| - 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]]. | ||
| + | |||
| + | |||
| ---- | ---- | ||
