[ Pobierz całość w formacie PDF ]
.Postępujemy tak mając świadomość, że w pewnych, chociaż mniej prawdopodobnych sytuacjach, zastosowana metoda heurystyczna może utrudnić szybkie znalezienie rozwiązania, a czasem nawet uniemożliwić w ogóle jego znalezienie.Po metody heurystyczne będziemy więc sięgać, gdy nie zależy nam na znalezieniu wszystkich rozwiązań i możemy zadowolić się jednym rozwiązaniem, które jednak musi być znalezione bardzo szybko (typowa sytuacja z gier komputerowych).W innych jeszcze przypadkach, gdy istnienie rozwiązań jest bardzo wątpliwe, warto skorzystać z metod heurystycznych i być może w krótkim czasie znaleźć jakieś rozwiązanie.Jest bardzo wiele rozwiązań heurystycznych, tak jak wiele jest różnych typów algorytmów wymagających usprawnienia.Poniżej omówimy krótko dwie, bardziej ogólne metody heurystyczne.lW odniesieniu do algorytmu poszukującego drogi w labiryncie od pola a do pola b, jeśli wartość a jest mała, a wartość b duża, stosowanie heurystyki mo-głoby polegać na ustawieniu wartości we wszystkich zbiorach Si w porządku malejącym.W ten sposób zapewnilibyśmy wybory pól o dużych wartościach w pierwszej kolejności i większe prawdopodobieństwo poruszania się po krótszej ścieżce a co za tym idzie - szybsze osiągnięcie celu.Przyjmując taką heurystykę musimy mieć świadomość, że przy pewnych szczególnych ograniczeniach, występujących w labiryncie, przyjęcie takiej heurystyki może utrudnić znalezienie rozwiązania.llJeśli problem przedstawiono w postaci drzewa poszukiwań, to warto (jeśli to możliwe) tak przebudować drzewo poszukiwań, aby węzły niskiego stopnia (o najmniejszej liczbie synów) znalazły się bliżej szczytu drzewa.Obrazuje to rys.3.6.llb)lRys.3.6 Drzewo poszukiwań a) w pierwotnej postaci, b) po przebudowieDrzewo b) na rys.6 ma lepsze własności od drzewa a), mimo iż na poziomie 3 oba drzewa zawierają 8 węzłów.W metodach heurystycznych sprawdza się bowiem pewną ilość warunków ograniczających, w celu odrzucenia rozwiązań mniej prawdopodobnych.W drzewie b) jeśli nastąpi to na pewnej wysokości (na rys.3.6 w węźle zaznaczonym strzałką), to większa część poddrzewa zostanie odrzucona i cel szybciej osiągnięty.Tutaj bowiem badanie węzła wskazanego strzałką spowoduje odrzucenie aż sześciu z ośmiu rozwiązań, znajdujących się na liściach, podczas gdy w drzewie a) tylko czterech rozwiązań
[ Pobierz całość w formacie PDF ]
