Sztuczna inteligencja/SI Ćwiczenia 6: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| (Nie pokazano 6 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 6: | Linia 6: | ||
'''Rozwiązanie''' | '''Rozwiązanie''' | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
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. | |||
</div> | </div> | ||
</div> | </div> | ||
| Linia 16: | Linia 18: | ||
'''Rozwiązanie''' | '''Rozwiązanie''' | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
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. | |||
[[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]] | |||
</div> | </div> | ||
</div> | </div> | ||
| Linia 21: | Linia 39: | ||
== Zadanie 3 == | == 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? | Czy zastosowanie strategii <math>A^*\,</math> daje gwarancję, że pierwsze odwiedzenie węzła będącego celem przeszukiwania odbędzie się po najkrótszej ścieżce? | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
'''Rozwiązanie''' | '''Rozwiązanie''' | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Nie, taką pewność dawałoby jedynie zastosowanie idealnej funkcji heurystycznej <math>h^*\,</math>. Zastosowanie rzeczywistej funkcji heurystycznej <math>h\,</math> w metodzie <math>A^*\,</math> pozwala na zredukowanie liczby przeszukiwanych węzłów. | |||
</div> | </div> | ||
</div> | </div> | ||
| Linia 36: | Linia 55: | ||
'''Rozwiązanie''' | '''Rozwiązanie''' | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Gwarancję taką dają algorytmy równomiernego kosztu i A*; algorytm zachłanny może znaleźć rozwiązanie nieoptymalne. | |||
</div> | </div> | ||
</div> | </div> | ||
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
