Sztuczna inteligencja/SI Ćwiczenia 6

Z Studia Informatyczne
< Sztuczna inteligencja
Wersja z dnia 03:04, 30 wrz 2006 autorstwa Jarabas (dyskusja | edycje) (Rozwiązanie zadania 2)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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