220 221 (7)

220    8 Mytleuie i nrzniązywame problemów

wszystko pozwala mu wysunąć hipotezę na temat rodzaju uszkodzenia, czasu naprawy oraz jej kosztu.

Przeszukiwanie heurystyczne nie daje 100% pewności znalezienia rozwiązania. Dużą zaletą metod heurystycznych jest jednak to, że pozwalają postępować w sposób bardziej ekonomiczny. Pozwalają także — w* pewnych warunkach — wykrywać nowe algorytmy. Przytoczmy w tym miejscu anegdotę związaną ze słynnym matematykiem Gaussem. Otóż nauczyciel matematyki Gaussa był osobą dość leniwą. Pewnego dnia chciał odpocząć w czasie lekcji i kazał uczniom obliczyć sumę wszystkich kolejnych liczb od 1 do 100. Zadanie to jest bardzo żmudne i łatw^fo popełnić w nim błąd. Wszyscy uczniowie pracowicie dodawali 1+2+3+4...+99+100. Większość z nich popełniła błędy. Jeden tylko Gauss (ku rozpaczy leniwego nauczyciela) szybko podał prawidłowy wynik — 5050. Zauważył on, że jeśli weźmiemy szereg od 1 do 100, to suma skrajnych elementów zawsze wynosi 101 (1+100, 2+99, 3+98,... itd.). Ponieważ mamy 50 takich par, możemy więc łatwo obliczyć sumę, mnożąc 101 przez 50. Młody Gauss wykrył ten nowy algorytm dzięki zastosowaniu metod heurystycznych. Badania eksperymentalne przeprowadzone przez Schmucka (1990) wykazały, że zdolność do tworzenia nowych heurystyk związana jest z indywidualnymi właściwościami jednostki. Stwierdził on, że łatwiej je tworzą ludzie cechujący się szybkim przebiegiem procesów poznawczych. Dzieje się tak dlatego, że ich umysł w trakcie pracy nad jakimś problemem ma „wolne moce przerobowe", które może poświęcić na wymyślanie nowych, bardziej ekonomicznych algorytmów.

(3) Przeszukiwanie oparte na zasadzie bliskości. Tą nazwą opatruje się grupę technik, w których poszukuje się odpowiedniej ścieżki rozwiązania przez wprowadzanie modyfikacji do ścieżki poprzedniej. Tego typu przeszukiwanie ma charakter konserwatywny. Występuje ono w kilku odmianach (Reynolds, Flagg, 1983):

(a)    Metoda „ciepło—zimno". Nazwa pochodzi od dobrze wszystkim znanej dziecięcej zabawy, polegającej na tym. że chowa się jakiś przedmiot, a osobie, która go szuka, podaje się informację o bliskości tego przedmiotu za pomocą określeń „ciepło" i „zimno". Gdy mechanik nie wie, co zepsuło się w* samochodzie klienta, a informacje klienta są bezwartościowe diagnostycznie, sam włącza silnik i przykładając doń ucho stara się wykryć źródło podejrzanych stuków. Im będzie bliżej tego źródła, tym stukanie będzie głośniejsze.

(b)    Metoda „wspinaczki". Metodę tę opiszemy w sposób metaforyczny, odwołując się do przykładu Reynoldsa i Flagga (1983). Załóżmy, że jesteśmy ślepi i mamy wejść na górę. Stawiając każdy krok czujemy, czy podążamy w górę, czy też w dół. Gdy idziemy w dół, zmieniamy kierunek tak, by iść w górę. W końcu osiągamy taki punkt, z którego wszystkie drogi zbiegają w dół. Oznacza to, że jesteśmy na szczycie. Problem jednak polega na tym, że nie musi to być najwyższy szczyt w okolicy — a w'ięc osiągnięte w ten sposób rozwiązanie nie musi być rozwiązaniem najlepszym.

(c) Metoda analizy w kategoriach środków i celów. Po ustaleniu celu staramy się określić, jakimi środkami należy go osiągnąć. Następnie ustalamy podcele, czyli cele cząstkowe, które się osiągnie po zastosowaniu kolejnych środków. Po osiągnięciu jednego podcelu sprawdzamy, czy zbliżyliśmy się do celu końcowego, i dobieramy odpowiedni środek, aby osiągnąć następny podcel.

Nie zawsze jest tak, że osiągnięcie kolejnego podcelu przybliża nas do celu końcowego. Osiągając niektóre podcele pozornie się od celu końcowego oddalamy, ale tylko po to, by się w następnym ruchu do niego zbliżyć. Jako przykład przytoczymy tak zwany problem wieży w Hanoi (Glass, Holyoak, Santa, 1979). Na ryc. 8.5 przedstawiono stan początkowy.

Ryc. 85. Stan początkowy w przypadku wieży w Hanoi (źródło: Reynolds, Flagg, 198‘3, S. 247)

Zadanie polega na tym, by krążki 1, 2, 3, znajdujące się na pręcie A, przenieść na pręt C. Dopuszczalne jest przenoszenie tylko jednego krążka na inny pręt. Nie wolno doprowadzić do tego, by na którymkolwiek pręcie większy krążek znajdował się nad mniejszym. Czytelnik może rozwiązać ten problem samodzielnie. Rozwiązanie problemu obejmuje następujące kroki:

(1)    Krążek 1 na pręt C.

(2)    Krążek 2 na pręt B.

(3)    Krążek 1 na pręt B.

(4)    Krążek 3 na pręt C.

(5)    Krążek 1 na pręt A.

(6)    Krążek 2 na pręt C.

(7)    Krążek 1 na pręt C.

W kroku 3 i 5 ruchy mają charakter paradoksalny, ponieważ krążek 1 oddala się od pręta C. Takie ruchy wynikają ze struktury zadania, w którym występuje hierarchia podcel ów. Cel końcowy — przenieść krążki 1, 2 i 3 z pręta A na pręt C — rozłożony jest na kolejne podcele:

(1)    Przenieść krążek 3 na pręt C.

(2)    Przenieść krążek 2 na pręt C.

(3)    Przenieść krążek 1 na pręt C.

Tym podcelom podporządkowane są następne podcele — np. „uwolnić krążek 3 spod krążków, które go zakrywają". Ten podcel generuje już konkretne ruchy. Ruchy te pozwalają realizować strategiczne podcele, ale