Tekst źródłowy strony Sztuczna inteligencja/SI Ćwiczenia 6

== Zadanie 1 ==

Zdefiniować (i naszkicować jej graf) przestrzeń przeszukiwań i sformułować funkcję celu dla przykładowego zadania sortowania tablicy zawierającej 4 elementy <math>\{1,2,3,4\}\,</math>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie''' 
<div class="mw-collapsible-content" style="display:none">
Elementami przestrzeni są permutacje liczb od 1 do 4. Funkcja odległości określona jest przez minimalną liczbę "przestawień" dwóch liczb, przez które można osiągnąć z jednej permutacji drugą (tzn. permutacja 1,2,3,4 jest oddalona o 1 od permutacji 1,2,4,3). Funkcja celu to odległość od permutacji 1,2,3,4.

</div>
</div>

== Zadanie 2 ==

Napisać program rozwiązujący problem komiwojażera. Rozważyć trzy metody rozwiązania: strategię równomiernego kosztu, strategię zachłanną i A*. Uwaga: testując proszę przyjąć stosunkowo niewielkie grafy aby móc doczekać się rozwiązania.

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie''' 
<div class="mw-collapsible-content" style="display:none">
Użyta funkcja heurystyczna znajduje długość <math>l\,</math> najkrótszej z krawędzi, które dostępne są wśród węzłów rozpatrywanego grafu nieobecnych na zbudowanym już fragmencie ścieżki (cyklu); podawane dolne ograniczenie na sumaryczną długość pozostałej (niezbudowanej) cześci cyklu to iloczyn długości znalezionej najkrótszej ścieżki <math>l\,</math> przez pozostałą do dodania ilość krawędzi.

Poniżej znajdują się ścieżki wygenerowane przez kolejno strategie: zachłanną, równomiernego kosztu oraz '''A*''' dla 10 miast z danych obecnych w kodzie źródłowym rozwiązania.

[[Grafika:greedy.png]]
Strategia '''zachłanna''', długość ścieżki: 37.49.

[[Grafika:uniform.png]]
Strategia '''równomiernego kosztu''', długość ścieżki: 32.61.

[[Grafika:astar.png]]
Strategia '''A*''', długość ścieżki: 27.5624.

Kod źródłowy:
[[Media:tsp.cc]]

</div>
</div>

== Zadanie 3 ==

Czy zastosowanie strategii <math>A^*\,</math> daje gwarancję, że pierwsze odwiedzenie węzła będącego celem przeszukiwania odbędzie się po najkrótszej ścieżce?

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie''' 
<div class="mw-collapsible-content" style="display:none">
Nie, taką pewność dawałoby jedynie zastosowanie idealnej funkcji heurystycznej <math>h^*\,</math>. Zastosowanie rzeczywistej funkcji heurystycznej <math>h\,</math> w metodzie <math>A^*\,</math> pozwala na zredukowanie liczby przeszukiwanych węzłów.
</div>
</div>

== Zadanie 4 ==

Które z algorytmów - zachłanny, równomiernego kosztu, A* - dają gwarancję znalezienia najkrótszej ścieżki, jeśli w grafie przestrzeni przeszukiwań nie występują cykle?

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
'''Rozwiązanie''' 
<div class="mw-collapsible-content" style="display:none">
Gwarancję taką dają algorytmy równomiernego kosztu i A*; algorytm zachłanny może znaleźć rozwiązanie nieoptymalne.
</div>
</div>