AIwiki

Strona Główna

Dla Studentów

Zima / Winter 2021:

Computer Science: Introduction to AI
ISI: Podstawy Sztucznej Inteligencji

Old specialized AI courses

SMaDA/SMaIDA/AIDA

1. semester:

2. semester:

WSHOP -- Development Workshop

Informatyka (EAIiIB)

1. rok:

2. i 3. rok:

4. rok:

Systemy i technologie wirtualizacji

Studia Dr

HeKatE

Public

The KESE workshop (EN only)
Mindstorms (archive)

Prolog Lab

Część główna

Część fakultatywna

Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

--- pl:prolog:prolog_lab:prolog_lab_graphsearch [2013/04/10 07:09]
gjn [Wprowadzenie]
+++ 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 =====
@@ Linia 16: / Linia 16: @@
 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://en.wikipedia.org/wiki/Graph_(mathematics)|Graph (en.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).
@@ 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.
@@ Linia 62: / Linia 62: @@
   * 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).
@@ Linia 70: / Linia 67: @@
   * [[http://pl.wikipedia.org/wiki/Przeszukiwanie_grafu|Algorytmy przeszukiwania w głąb i wszerz]],
-  * [[http://pl.wikipedia.org/wiki/Algorytm_Dijkstry|Klasycznym algorytmie 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]].
@@ Linia 80: / Linia 77: @@
   * plan o najtańszej trasie przejazdu,
   * 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 reprezentacja w Prologu =====
+===== - Grafy i ich reprezentacja w Prologu =====
 W Prologu można reprezentować grafy na kilka sposobów.
@@ Linia 93: / Linia 102: @@
 {{: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)}}
@@ Linia 99: / 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.
-Reprezentacja tego grafy w Prologu ma postać:
+Reprezentacja tego grafu w Prologu ma postać:
-<code>
+<code prolog>
 d(s,g).
 d(s,n1).
@@ Linia 123: / Linia 131: @@
 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
      przejazd(X,Y):- d(X,Y).
@@ Linia 140: / Linia 148: @@
 ----
-===== Poszukiwanie tras przejazdu =====
+===== - Poszukiwanie tras przejazdu =====
 Rozważmy najprostszy program realizujący zadanie poszukiwania tras przejazdu:
-<code>
+<code prolog>
 %%% domknięcie tranzytywne relacji przejazd
      szukaj_trasy(Cel,Cel,Trasa,Trasa):- !.
@@ Linia 185: / Linia 193: @@
 ----
-===== Inicjowanie programu i zliczanie rozwiązań =====
+===== - Inicjowanie programu i zliczanie rozwiązań =====
 Aby ułatwić uruchamianie programu wyposażymy go w klauzulę inicjującą:
-<code>
+<code prolog>
 %%% inicjacja szukania
      plan(Start,Cel,Trasa):-
@@ Linia 199: / Linia 207: @@
 Aby wyznaczyć automatycznie wszystkie plany uzupełnimy program o klauzulę:
-<code>
+<code prolog>
 %%% Find all plans from 's' to 'g'.
      fap(Plans) :- findall(Trasa, plan(s,g,Trasa),Plans).
@@ Linia 206: / Linia 214: @@
 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>).
      fap-assert:- plan(s,g,Plan), assert(p(Plan)), fail.
@@ Linia 227: / Linia 235: @@
 ----
-===== Szukanie tras przejazdu pomiędzy miastami w Polsce =====
+===== - Szukanie tras przejazdu pomiędzy miastami w Polsce =====
 Załączony program pozwala poszukiwać tras przejazdy pomiędzy wybranymi miastami w Polsce.
@@ Linia 247: / 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.
-Program wyznaczający długość trasy: {{:pl:prolog:prolog_lab:plan_d.pl}}
+{{:pl:prolog:prolog_lab:plan_d.pl}}
 ==== Zadania ====
@@ Linia 261: / Linia 275: @@
 ----
-===== 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}}
@@ Linia 275: / 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 trasę optymalna z wykorzystaniem mechanizmu nawrotów w Prologu.
@@ Linia 288: / 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]]

pl/prolog/prolog_lab/prolog_lab_graphsearch.1365570588.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry