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 $\{1,2,3,4\}$

Rozwiązanie

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.

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.

Rozwiązanie

Użyta funkcja heurystyczna znajduje długość $l$ 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 $l$ 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.

Strategia zachłanna, długość ścieżki: 37.49.

Strategia równomiernego kosztu, długość ścieżki: 32.61.

Strategia A*, długość ścieżki: 27.5624.

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

Zadanie 3

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

Rozwiązanie

Nie, taką pewność dawałoby jedynie zastosowanie idealnej funkcji heurystycznej $h^{*}$. Zastosowanie rzeczywistej funkcji heurystycznej $h$ w metodzie $A^{*}$ pozwala na zredukowanie liczby przeszukiwanych węzłów.

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?

Rozwiązanie

Gwarancję taką dają algorytmy równomiernego kosztu i A*; algorytm zachłanny może znaleźć rozwiązanie nieoptymalne.