Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:prolog:prolog_lab:prolog_lab_graphsearch [2011/12/12 08:10] gjn |
pl:prolog:prolog_lab:prolog_lab_graphsearch [2019/06/27 15:50] (aktualna) |
====== - 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. |
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 (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). | 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). |
---- | ---- |
| |
===== 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. |
| |
Algorytmy z obszaru sztucznej inteligencji wyróżniają się tym, że: | Algorytmy z obszaru sztucznej inteligencji wyróżniają się tym, że: |
* często korzystają z heurystyk odelgłościowych (np. opartych na oszacowaniu odległości Euklidesowej i wg metryki ulicznej), | * 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. wezłów zabronionych, | * pozwalają na uwzględnianie dodatkowych ograniczeń, np. węzłów zabronionych, |
* pozwalają na przeszukiwanie przestrzeni o bardzo dużych rozmiarach, | * 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 wywowłania funkcji generującej). | * 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]]. |
| |
* 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. |
| |
{{: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)}} |
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). |
</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). |
| |
| |
== 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):- !. |
* 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. |
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. |
| |
| |
- 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. |
---- | ---- |
| |
===== Inicjowanie programu i zliczanie rozwiązań ===== | ===== - Inicjowanie programu i zliczanie rozwiązań ===== |
| |
Aby ułatwić 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):- |
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). |
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. |
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. |
---- | ---- |
| |
===== 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|Prosty program planowania tras przejadu}} | Prosty program planowania tras przejazdu: {{:pl:prolog:prolog_lab:plan.pl}} |
| |
Przeanalizuj działanie programu. | Przeanalizuj działanie programu. |
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, |
---- | ---- |
| |
===== 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? |
| |
| |
| |
| |
===== 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. |
| |
| Planowanie trasy optymalne z nawrotami: {{:pl:prolog:prolog_lab:plan_f.pl}} |
| |
{{:pl:prolog:prolog_lab:plan_f.pl|Planowanie trasy optymalne z nawrotami}} | ==== Zadania ==== |
| |
| |
=== Zadania === | |
| |
- Przeanalizuj szczegółowo działanie programu; wyświetlaj znalezione trasy. | - Przeanalizuj szczegółowo działanie programu; wyświetlaj znalezione trasy. |
---- | ---- |
| |
===== Algorytmy szukania ===== | ===== - Przeszukiwanie wszerz ===== |
| |
==== DFS ==== | Następujący program pozwala wyznaczać plan metodą wszerz (BFS) |
| |
<code> | {{:pl:prolog:prolog_lab:breadth-first-plan.pl}} |
% Figure 4.7 Program 1 for the eight queens problem. | |
| |
% solution( BoardPosition) if | ==== Zadania ==== |
% BoardPosition is a list of non-attacking queens | |
| |
solution( [] ). | - 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//). |
| |
solution( [X/Y | Others] ) :- % First queen at X/Y, other queens at Others | ===== - Szukanie heurystyczne tras ===== |
solution( Others), | |
member( Y, [1,2,3,4,5,6,7,8] ), | |
noattack( X/Y, Others). % First queen does not attack others | |
| |
noattack( _, [] ). % Nothing to attack | Przeanalizuj działanie programu. |
| Heurystyka jest zadana w ''szukaj_trasy''. |
| Porównaj z wcześniejszymi alg. szukania. |
| |
noattack( X/Y, [X1/Y1 | Others] ) :- | {{:pl:prolog:prolog_lab:traser.pl|}} |
Y =\= Y1, % Different Y-coordinates | |
Y1-Y =\= X1-X, % Different diagonals | |
Y1-Y =\= X-X1, | |
noattack( X/Y, Others). | |
| |
member( Item, [Item | Rest] ). | ===== - Szukanie heurystyczne A* dla 8puzzle ===== |
| |
member( Item, [First | Rest] ) :- | |
member( Item, Rest). | |
| |
% A solution template | Program {{:pl:prolog:prolog_lab:bratko-fig12_3f.pl|}} implementuje algorytm [[wp>A*]]. |
| Zobacz też: [[http://artint.info/html/ArtInt_56.html]] |
| |
template( [1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8] ). | Sam program wymaga podania opisu problemu przez predykat ''s(N,M,C).'': |
</code> | * 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. |
| |
<code> | Poczytaj o [[wp>8-puzzle]]. |
% Figure 11.7 A depth-first search program that avoids cycling. | W opisie tego problemu używamy innej miary odległości niż np. na drodze, tzw. odległości taksówkarskiej |
% solve( Node, Solution): | [[wp>Manhattan_distance]] |
% Solution is an acyclic path (in reverse order) between Node and a goal | |
| |
solve( Node, Solution) :- | Program {{:pl:prolog:prolog_lab:bratko-fig12_6.pl|}} implementuje opis tego problemu do rozwiązania przez w.w. algorytm [[wp>A*]]. |
depthfirst( [], Node, Solution). | |
| |
% depthfirst( Path, Node, Solution): | Przykładowe wywołanie: |
% extending the path [Node | Path] to a goal gives Solution | ?- start1( Pos), bestfirst( Pos, Sol), showsol( Sol). |
| Zobacz rozwiązania dla inne stanów startowych. |
| |
depthfirst( Path, Node, [Node | Path] ) :- | - dodaj inne stany startowe |
goal( Node). | - 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). |
| |
depthfirst( Path, Node, Sol) :- | ===== - Szukanie -- wizualizacja ===== |
s( Node, Node1), | Spróbuj zrealizować wizualizację grafu dla tras przez program Graphviz. |
not member( Node1, Path), % Prevent a cycle | Vide: programy w |
depthfirst( [Node | Path], Node1, Sol). | [[pl:prolog:prolog_lab:prolog_lab_system#metaprogramowanie_i_potoki]] |
</code> | |
| |
| ===== - 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]] |
| |