Sztuczna inteligencja/SI Ćwiczenia 6: Różnice pomiędzy wersjami
m (→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
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 
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?
daje gwarancję, że pierwsze odwiedzenie węzła będącego celem przeszukiwania odbędzie się po najkrótszej ścieżce?
Rozwiązanie
. Zastosowanie rzeczywistej funkcji heurystycznej 
w metodzie 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
