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 [2009/11/29 17:14] ligeza |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== - 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. | ||
| Linia 12: | Linia 12: | ||
| Najprostsza definicja grafu mówi, że graf to para postaci //G=(V,E)//, gdzie //V// jest zbiorem węzłów a //E ⊆ V×V// jest zbiorem łączących je krawędzi. | Najprostsza definicja grafu mówi, że graf to para postaci //G=(V,E)//, gdzie //V// jest zbiorem węzłów a //E ⊆ V×V// jest zbiorem łączących je krawędzi. | ||
| - | Model ten reprezentuje schmatycznie mapę, gdzie w zależności od poziomu abstrakcji węzły mogą np. reprezentować miasta, a krawędzie - łączące je drogi, lub też węzły mogą reprezentować skrzyżowania ulic a krawędzie ulice (lub ich odcinki). | + | Model ten reprezentuje schematycznie mapę, gdzie w zależności od poziomu abstrakcji węzły mogą np. reprezentować miasta, a krawędzie - łączące je drogi, lub też węzły mogą reprezentować skrzyżowania ulic a krawędzie ulice (lub ich odcinki). |
| 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 (ew.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). | ||
| - | Odpowiednio, graf może byc grafem skierowanym, nieskierownym lub mieszanym. | + | Odpowiednio, graf może być grafem skierowanym, nieskierowanym lub mieszanym. |
| Ponadto, z każdą krawędzią może być związany koszt przejazdu (odległość, czas). | Ponadto, z każdą krawędzią może być związany koszt przejazdu (odległość, czas). | ||
| Linia 29: | Linia 29: | ||
| ---- | ---- | ||
| - | ===== 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. | ||
| Linia 55: | Linia 55: | ||
| Zwykle wymaga się aby każdy węzeł leżący na ścieżce przejazdu odwiedzany był tylko raz (brak cykli). | Zwykle wymaga się aby każdy węzeł leżący na ścieżce przejazdu odwiedzany był tylko raz (brak cykli). | ||
| - | Zanych jest wiele algorytmów przeszukiwania grafów. | + | Znanych jest wiele algorytmów przeszukiwania grafów, zarówno w obszarze teorii grafów, badań operacyjnych jak i sztucznej inteligencji. |
| + | |||
| + | Algorytmy z obszaru sztucznej inteligencji wyróżniają się tym, że: | ||
| + | * często korzystają z heurystyk odległościowych (np. opartych na oszacowaniu odległości Euklidesowej i wg metryki ulicznej), | ||
| + | * pozwalają na uwzględnianie dodatkowych ograniczeń, np. węzłów zabronionych, | ||
| + | * 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). | ||
| Zapoznaj się z podstawowymi algorytmami: | Zapoznaj się z podstawowymi algorytmami: | ||
| - | * [[http://pl.wikipedia.org/wiki/Przeszukiwanie_grafu|Algorytmy przeszykiwania 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 algorytme 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]]. | ||
| Linia 70: | 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).// | ||
| ---- | ---- | ||
| - | ===== Grafy i ich preprezentacja w Prologu ===== | + | ===== - Grafy i ich reprezentacja w Prologu ===== |
| - | W Prologu można reprezentowac grafy na kilka sposobów. | + | W Prologu można reprezentować grafy na kilka sposobów. |
| Najprostszą i efektywną metodą jest zadeklarowanie połączeń pomiędzy węzłami grafu w postaci faktów w Prologu. | Najprostszą i efektywną metodą jest zadeklarowanie połączeń pomiędzy węzłami grafu w postaci faktów w Prologu. | ||
| Linia 83: | Linia 102: | ||
| {{: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)}} | ||
| Linia 89: | Linia 107: | ||
| 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). | ||
| Linia 107: | Linia 125: | ||
| </code> | </code> | ||
| - | Jak widać, każda krawędź zapisywana jest w postaci relacji //d(<węzeł_poczatkowy>,<węzeł_końcowy>).// | + | Jak widać, każda krawędź zapisywana jest w postaci relacji //d(<węzeł_początkowy>,<węzeł_końcowy>).// |
| - | W przykładowym grafie istnieje 13 krawędzi. Zgodnie z deklaracją w Prologu, są to krawędzie //skierowane// (dlaczego | + | W przykładowym grafie istnieje 13 krawędzi. Zgodnie z deklaracją w Prologu, są to krawędzie //skierowane// (dlaczego?) |
| 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). | ||
| Linia 122: | Linia 140: | ||
| - | == Zadania == | + | ==== Zadania ==== |
| - Przerysuj pokazany graf na kartce papieru. | - Przerysuj pokazany graf na kartce papieru. | ||
| - | - Znajdź - wspomagając się rysunkiem kilka mozliwych alternatywnych tras przejazdu; zaznacz je na rysunku. | + | - Znajdź - wspomagając się rysunkiem kilka możliwych alternatywnych tras przejazdu; zaznacz je na rysunku. |
| - Spróbuj wyznaczyć //wszystkie// różne trasy przejazdu (nie zawierające cykli); ile ich jest? | - Spróbuj wyznaczyć //wszystkie// różne trasy przejazdu (nie zawierające cykli); ile ich jest? | ||
| ---- | ---- | ||
| - | ===== 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):- !. | ||
| Linia 150: | Linia 168: | ||
| * trasę docelową (Trasa). | * trasę docelową (Trasa). | ||
| - | Pierwszy wariant definiuje zakończenie poszukiwań: gdy znajdziemy się w weżle docelowym, trasa Robocza staje się docelową. | + | Pierwszy wariant definiuje zakończenie poszukiwań: gdy znajdziemy się w węźle docelowym, trasa Robocza staje się docelową. |
| Drugi wariant definiuje sposób szukania trasy: | Drugi wariant definiuje sposób szukania trasy: | ||
| * będąc w węźle //Miasto//, znajdź //NoweMiasto// do którego jest bezpośrednie połączenie (uzywając predykatu //przejazd/2//, | * będąc w węźle //Miasto//, znajdź //NoweMiasto// do którego jest bezpośrednie połączenie (uzywając predykatu //przejazd/2//, | ||
| - | * sprawdź, czy nie było juz odwiedzane (// not(member(NoweMiasto,Robocza)) //), | + | * sprawdź, czy nie było już odwiedzane (// not(member(NoweMiasto,Robocza)) //), |
| * jeżeli tak, zostanie wymuszony nawrót; jeżeli nie, próbuj dalej i w tym celu | * jeżeli tak, zostanie wymuszony nawrót; jeżeli nie, próbuj dalej i w tym celu | ||
| * zaktualizuj trasę roboczą dokładając //NoweMiasto// i kontynuuj szukanie z tego miejsca. | * zaktualizuj trasę roboczą dokładając //NoweMiasto// i kontynuuj szukanie z tego miejsca. | ||
| Linia 161: | Linia 179: | ||
| Zauważ, że: | Zauważ, że: | ||
| - | * trasy reprezentowane sa jako listy, | + | * trasy reprezentowane są jako listy, |
| * konstruowana ścieżka wydłuża się w miarę szukania; dokładane są nowe miasta, | * konstruowana ścieżka wydłuża się w miarę szukania; dokładane są nowe miasta, | ||
| - | * konstruowane sa wszystkie warianty planu - dzięki mechanizmowi nawrotów w Prologu, | + | * konstruowane są wszystkie warianty planu - dzięki mechanizmowi nawrotów w Prologu, |
| * żaden plan nie będzie zawierał cykli. | * żaden plan nie będzie zawierał cykli. | ||
| Linia 169: | Linia 187: | ||
| - Uruchom podany program dla przykładowego grafu; jak zainicjować parametry? | - Uruchom podany program dla przykładowego grafu; jak zainicjować parametry? | ||
| - | - Zadaj w jakiej kolejności wystepują miasta na znalezionych trasach. Dlaczego? | + | - Zadaj w jakiej kolejności występują miasta na znalezionych trasach. Dlaczego? |
| - Wygeneruj przykładowy plan rozwiązania, | - Wygeneruj przykładowy plan rozwiązania, | ||
| - Wygeneruj wszystkie możliwe plany i policz je. | - Wygeneruj wszystkie możliwe plany i policz je. | ||
| Linia 175: | Linia 193: | ||
| ---- | ---- | ||
| - | ===== Inicjowanie programu i zliczanie rozwiązań ===== | + | ===== - Inicjowanie programu i zliczanie rozwiązań ===== |
| - | Aby ułatwic 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):- | ||
| Linia 185: | Linia 203: | ||
| </code> | </code> | ||
| - | Zauważ, że //Start// i //Cel// zamieniły sie miejscami. Dlaczego? | + | Zauważ, że //Start// i //Cel// zamieniły się miejscami. Dlaczego? |
| 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). | ||
| Linia 196: | Linia 214: | ||
| 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. | ||
| Linia 206: | Linia 224: | ||
| 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. | ||
| - Jaka jest kolejność węzłów w wygenerowanych planach? | - Jaka jest kolejność węzłów w wygenerowanych planach? | ||
| - | - W jakiej kolejności (w jakim kierunku) odbywa się rzeczywista genetacja planów? | + | - W jakiej kolejności (w jakim kierunku) odbywa się rzeczywista generacja planów? |
| - Policz ile jest planów dopuszczalnych (programowo) i porównaj wynik z rozwiązaniem ręcznym. | - Policz ile jest planów dopuszczalnych (programowo) i porównaj wynik z rozwiązaniem ręcznym. | ||
| - Zmodyfikuj program tak, aby dla każdego planu wyznaczał jego długość (ilość odwiedzanych węzłów). | - Zmodyfikuj program tak, aby dla każdego planu wyznaczał jego długość (ilość odwiedzanych węzłów). | ||
| - | - Zastanów się jak zeralizować (a może nawet spróbuj) analogiczny program w //Twoim ulubionym języku programowania// (np. Java, C++, Python). Porónaj naklad pracy z kodowaniem w Prologu. | + | - Zastanów się jak zrealizować (a może nawet spróbuj) analogiczny program w //Twoim ulubionym języku programowania// (np. Java, C++, Python). Porównaj nakład pracy z kodowaniem w Prologu. |
| ---- | ---- | ||
| - | ===== Szukanie tras przejazdu pomiędzy miastami w Polsce ===== | + | ===== - Szukanie tras przejazdu pomiędzy miastami w Polsce ===== |
| - | Załączony program pozwala poszukiwac tras przejazdy pomiędzy wybranymi miastami w Polsce. | + | Załączony program pozwala poszukiwać tras przejazdy pomiędzy wybranymi miastami w Polsce. |
| - | {{:pl:prolog:prolog_lab:plan.pl|Proty program planowania tras przejadu}} | + | Prosty program planowania tras przejazdu: {{:pl:prolog:prolog_lab:plan.pl}} |
| Przeanalizuj działanie programu. | Przeanalizuj działanie programu. | ||
| Linia 229: | Linia 247: | ||
| 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, | ||
| Linia 237: | Linia 255: | ||
| ---- | ---- | ||
| - | ===== 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. | ||
| - | {{:pl:prolog:prolog_lab:plan_d.pl|Program wyznaczający długośc trasy}} | + | {{:pl:prolog:prolog_lab:plan_d.pl}} |
| - | === Zadania === | + | ==== Zadania ==== |
| - Uruchom program i przeanalizuj jego działanie. | - Uruchom program i przeanalizuj jego działanie. | ||
| - | - Modyfikując ograniczenie znajdź wybrane trasy optymalne dla zadanego miastat początkowego i doceloweg. | + | - Modyfikując ograniczenie znajdź wybrane trasy optymalne dla zadanego miasta początkowego i docelowego. |
| - | - Zmodyfikuj program tak aby automatycznie modyfikował ograniczenie i znajdował trase optymalną. | + | - Zmodyfikuj program tak aby automatycznie modyfikował ograniczenie i znajdował trasę optymalną. |
| ---- | ---- | ||
| - | ===== 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). |
| - | {{:pl:prolog:prolog_lab:plan_d_opt.pl|Wyznaczanie trasy optymalnej}} | + | Wyznaczanie trasy optymalnej: {{:pl:prolog:prolog_lab:plan_d_opt.pl}} |
| - | Przeanalizuj program i jego działenie. | + | Przeanalizuj program i jego działanie. |
| - | Czy zaproponowana metoda jest efektywna? Na czym polegaja jej niedoskonalości i ograniczenia? | + | Czy zaproponowana metoda jest efektywna? Na czym polegają jej niedoskonałości i ograniczenia? |
| Linia 265: | Linia 289: | ||
| - | ===== 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 trase 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. | ||
| - | {{:pl:prolog:prolog_lab:plan_f.pl|Planowanie trasy optymalne z nawrotami}} | + | Planowanie trasy optymalne z nawrotami: {{:pl:prolog:prolog_lab:plan_f.pl}} |
| - | + | ==== Zadania ==== | |
| - | === Zadania === | + | |
| - Przeanalizuj szczegółowo działanie programu; wyświetlaj znalezione trasy. | - Przeanalizuj szczegółowo działanie programu; wyświetlaj znalezione trasy. | ||
| Linia 280: | 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]] | ||
