Sztuczna inteligencja/SI Ćwiczenia 6: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 20: Linia 20:
 
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.
 
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.
+
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]]
 
[[Grafika:greedy.png]]
Długość ścieżki: 37.49.
+
Strategia '''zachłanna''', długość ścieżki: 37.49.
  
 
[[Grafika:uniform.png]]
 
[[Grafika:uniform.png]]
Długość ścieżki: 32.61.
+
Strategia '''równomiernego kosztu''', długość ścieżki: 32.61.
  
 
[[Grafika:astar.png]]
 
[[Grafika:astar.png]]
Długość ścieżki: 27.5624.
+
Strategia '''A*''', długość ścieżki: 27.5624.
  
 
Kod źródłowy:
 
Kod źródłowy:

Aktualna wersja na dzień 03:13, 30 wrz 2006

Zadanie 1

Zdefiniować (i naszkicować jej graf) przestrzeń przeszukiwań i sformułować funkcję celu dla przykładowego zadania sortowania tablicy zawierającej 4 elementy

Rozwiązanie

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

Zadanie 3

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

Rozwiązanie

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