2091577343

9. Schemat działania Graph

Traversera

zbiór stanów i reguł przechodzenia od jednego stanu do drugiego. Algorytm winien przekształcać kolejne stany i sprawdzać, czy wśród nowo powstałych znajduje się ten, który może być uznany za ewentualne rozwiązanie (rys. 9).

Graph Traverser został użyty do rozwiązywania wielu zadań natury praktycznej, których istota zbliżona jest do problemu łamigłówki ośmiopolowej. W ten sposób m.in. ustalono miejsca postoju ciężarówek w garażu z uwzględnieniem kolejności ich wjazdów i wyjazdów, oraz rozwiązano tzw. problem komiwojażera: znalezienie najkrótszej drogi przy objeżdżaniu pewnej ilości miast. Na rys. 10 widać kolejne etapy zbliżania się maszyny do poprawnego wyniku. Z początku (a) trasa jest zupełnie przypadkowa i jej umowna długość wynosi 17 724; w połowie procesu (b) obliczeniowego trasa zostaje skrócona do 8420; rezultat końcowy (c) jest już owym poszukiwanym minimum 4192.

Charakterystyczne dla tego typu problemów jest również zadanie „przelewania”: jak odmierzyć 6 litrów wody mając naczynia 9- i 4-lit-

53