SE20101110024

—do uzasadnienia faktu Fi l dysponuj emy faktem (przesłanką) F7 i potrzebny jest fakt F8 (reguła 3);

do uzasadnienia faktu F12 dysponujemy faktem (przesłanką) F10 i potrzebny jest fakt F9 (reguła 4);

do uzasadnienia faktu F8 dysponujemy faktami (przesłankami) FI i F2 (reguła 1);

—    do uzasadnienia faktu F9 dysponujemy faktami (przesłankami) F3, F4 i F5 (reguła 2).

Łatwo zauważyć, że konkluzje K2 moglibyśmy uzasadnić dysponując na przykład zbiorem faktów F9, F10, Fil (w rozumowaniu byłyby wykorzystane reguły 4 i 5).

4.4. INNE STRATEGIE WNIOSKOWANIA

; Przedstawione powyżej podstawowe strategie wnioskowania mogą wytworzyć wrażenie, że poszukiwanie rozwiązań jest w gruncie rzeczy prostą czynnością. Niestety rzeczy wistość jest bardziej skomplikowana,.Grafy poszukiwać bywają bardzo rozbudowane. Znalezienie w nich rozwiązań wymaga specjalnych sposobów postępowania. Jest ich bardzo wiele—omówimy tylko niektóre z nich.    ^!

4.4.1. Uporządkowane i nieuporządkowane procedury poszukiwania rozwiązań

Poszukiwanie rozwiązań w grafie poszukiwań może być dokonywane zgodnie z różnymi metodami, które ze względu na sposób dochodzenia do rozwiązania podzieli sie na:

—    nieuporządkowane procedury poszukiwania (ang. unordered search pro-cedures);

—    uporządkowane procedury poszukiwania (ang. ordered search proce-dures).

Procedury nieuporządkowane mają na celu znalezienie jakiejś ścieżki (ang, some path) w grafie poszukiwań. Zastosowanie procedur uporządkowanych zapewnia nam znalezienie ścieżki optymalnej¹ (ang. optimal path).

Wśród procedur nieuporządkowanych najpopularniejsze są:

—    najpierw w głąb (ang. depth first),

—    najpierw wszerz (ang. breadth first),

—    najpierw najlepszy (ang. best first),

—    wiązka (ang. beam).

pierwszej procedury (najpierw w głąb) jest posuwanie się na coraz HtoW² poziomy w grafie. W momencie konieczności dokonania wyboru ścieżki pi#y|inii)r, się (nie imając żadnej miary jakości postępowania) dowolną zasadę Wybuiii Om przykład zawsze lewy lub zawsze prawy). Postępowanie kończy Wl« Miły osiągniemy rozwiązanie lub stwierdzimy że ścieżka jest “ślepa”.⁶ hottdui h najpierw w głąb daje dobrę efekty wtedy, gdy “ślepe” ścieżki w grafie jHiMiiklwań nie są zbyt głębokie. W takim przypadku unikamy czasochłonnych ptiWrolrtw na wyższe poziomy w grafie w celu odnalezienia punktu startowego ii tkliwych poszukiwań. , jv;b'

ftocrdiim najpierw wszerz'polegam przeglądaniu kolejnych poziomów i gMfiu poszuki wani ;Przeglądanie odbywa się od naj wyższego poziomu w kie-łUIlkll tum/, niższych. Proces kończy się w momencie znalezienia na którymś IpMMmnów rozwiązania. Procedura najpierw wszerz jest efektywna, gdy liczba yślilf/łt² ń (alternatyw) w punktach wyboru nie jest zbyt duża.

|k» zastosowania procedury najpierw najlepszy niezbędne jest pósiadanie HMiłOiltiij miary odległości odrozwiązania. Wykorzystując tę miarę, podejmuje |(| ttecy/k o wyborze kierunku poszukiwań w punktach rozgałęzień. Metoda M |MI s/( /(‘gólnie efektywna, gdy w górnych poziomach grafu poszukiwań Hi²ł#pH|ą źle rokujące ścieżki.

Hówmrż w procedurze wiązka niezbędne jest określenie miary odległości od tmiWlMzama Ideą tej metody jest wybór jedynie dwóch najlepiej rokujących |||it)ę«ioń w punktach wyboru. Ogranicza to znacznie liczbę rozpatrywanych iiiftiek Metoda ta nie jest skuteczna, gdy częściowo dobre ścieżki (od punktu (kWiklkowego do rozpatrywanego poziomu) nie są częściami ostatecznych ilłllfk. (luka Ścieżka w sensie procedury wiązka jest “ślepa”).

lepi r/.cntatywne dla uporządkowanych procedur poszukiwania należy MKiiC;    '

Muzeum Brytyjskie (ang. British Museum),

- otlgtiłęzienia i ograniczenia (ang. branch and bound), pmgmiriowanie dynamiczne (ang. dynamie programming).

Mrlndą Muzeum Brytyjskie¹ polega na sortowaniu i przeglądaniu wszystkich lliurtlwyeh Ścieżek. Daje się więc zastosować tylko wtedy, gdy graf poszukiwań jut niewielki,

hmeduni odgałęzień i ograniczeń opiera się na eliminowaniu ścieżek źle luk-MlMtych, Osiągnięcie jakiegoś rozwiązania nie kończy postępowania, gdyż i kolei binne są pod uwagę wszystkie wcześniej “otwarte” ścieżki. Procedura

47

1

Ścieżki prowadzącej do rozwiązania optymalnego.

2

   ki to takie, którs nie prowadzą do uzyskania rozwiązania,

fi i ²1 ygirmliia n/uwa tej procedury wynika ze skojarzenia, że w Muzeum Brytyjskim jest wiele wnUłininńw 1 Ssząc bezładnie na maszynie w końcu napisalibyśmy coś sensownego, co można tiy ini)ir<( U w muzeum.