Sztuczna inteligencja/SI Ćwiczenia 6: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniam (→Zadanie 2) |
m (→Zadanie 2) |
||
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]] | ||
− | + | Strategia '''zachłanna''', długość ścieżki: 37.49. | |
[[Grafika:uniform.png]] | [[Grafika:uniform.png]] | ||
− | + | Strategia '''równomiernego kosztu''', długość ścieżki: 32.61. | |
[[Grafika:astar.png]] | [[Grafika:astar.png]] | ||
− | + | 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