Sztuczna inteligencja/SI Ćwiczenia 6

From Studia Informatyczne

Spis treści

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.

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

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.