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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 23: Linia 23:
  
 
[[Grafika:greedy.png]]
 
[[Grafika:greedy.png]]
 +
Długość ścieżki: 37.49.
  
 
[[Grafika:uniform.png]]
 
[[Grafika:uniform.png]]
 +
Długość ścieżki: 32.61.
  
 
[[Grafika:astar.png]]
 
[[Grafika:astar.png]]
 +
Długość ścieżki: 27.5624.
  
 
Kod źródłowy:
 
Kod źródłowy:

Wersja z 03:10, 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