AI2.pdf

1 Szukanie

1.1 Wst

Jedn ą z najwa ż niejszych metod informatyki jest szukanie (searching). Trzeci tom fundamentalnego dzieła „The

art of computer programming” Donalda Knutha po ś wi ę cony jest w cało ś ci algorytmom szukania. Konieczno ść

szukania wyst ę puje w problemach dedukcji, rozumowania, wnioskowania, planowania, dowodzenia itp.

Zastosowania metod opartych na szukaniu znale źć mo ż na we wszystkich gał ę ziach AI. Niektórzy uczeni

wszystko, co oparte jest na przeszukiwaniu drzewa mo ż liwo ś ci wi ążą z sztuczn ą inteligencj ą , np. techniki AI w

fizyce czy chemii kwantowej sprowadzaj ą si ę w wi ę kszo ś ci do zastosowania algorytmów szukania. Chocia ż jest

to zbyt daleko id ą ce uogólnienie trzeba stwierdzi ć , ż e algorytmy szukania rozwin ę ły si ę przede wszystkim w

zastosowaniach zwi ą zanych ze sztuczn ą inteligencj ą .

Szukajcie a (by ć mo ż e) znajdziecie! Bez szukania natomiast na pewno nie znajdziecie.

Zanim zaczniemy szuka ć trzeba wiedzie ć gdzie prowadzi ć poszukiwania, tj. jak reprezentowa ć problem, który

chcemy rozwi ą za ć i jak okre ś li ć przestrze ń poszukiwa ń . Mo ż emy tu wyró ż ni ć 3 elementy. Po pierwsze, mamy

jak ąś baz ę danych zawieraj ą cych fakty czy mo ż liwo ś ci, obszar dost ę pnych ruchów. Mog ą w niej by ć tabele,

listy słów, zbiory formuł, sieci semantyczne. Np. dowodz ą c twierdzenia matematyczne mamy baz ę danych

zło ż on ą z aksjomatów, lematów i poprzednio udowodnionych twierdze ń . Korzystaj ą c z tego chcemy doj ść do

dowodzonego twierdzenia. Po drugie, mamy przestrze ń mo ż liwych operacji prowadz ą cych do zmian sytuacji

w tej bazie danych. Sytuacj ę w danym momencie okre ś lamy jako stan bazy danych. Operacje dokonywane s ą

przez operatory powoduj ą ce zmian ę tych stanów, manipuluj ą ce baz ą danych. Przykładem s ą tu reguły

wnioskowania w rachunku logicznym, reguły ruchów w grach, reguły heurystyczne dla upraszczania wyra ż e ń w

rachunku symbolicznym. Trzeci element to strategia kontrolna , okre ś laj ą ca start oraz sposób działania: do

czego i który operator warto zastosowa ć by doj ść do po żą danej sytuacji ko ń cowej (dowodu twierdzenia,

przewagi na planszy w czasie gry). Osi ą ganie celu stosuj ą c odpowiedni ą sekwencj ę operatorów do sytuacji

pocz ą tkowej jest form ą dowodzenia. Ka ż de zastosowanie operatora zmienia sytuacj ę , zmienia si ę baza danych i

mo ż e to wpływa ć na strategi ę . Ta z kolei powinna dopuszcza ć ró ż ne sekwencje operatorów, które wydaj ą si ę

obiecuj ą ce. Poniewa ż sekwencji takich mo ż e by ć bardzo du ż o powstaje problem przeszukiwania.

Mamy 4 typy problemów:

Znany jest stan bazy i znane efekty działania.

Dany jest zbiór mo ż liwych stanów pocz ą tkowych, znane efekty działa ń .

Ograniczona znajomo ść stanów, działania zale ż ne od warunków (np. ograniczona widoczno ść

w trudnym terenie).

Problemy wymagaj ą ce eksploracji: działania tworz ą nowe warunki, potrzeba zdobywania

nowej wiedzy (np. Pathfinder).

Wyró ż nia si ę dwa rodzaje rozumowania. Rozumowanie bezpo ś rednie (do przodu) jest wtedy, gdy stosuje si ę

operatory do faktów znanych by wytworzy ć now ą sytuacj ę , bli ż sz ą sytuacji docelowej, np. mata w szachach lub

uzyskanie przewagi na planszy. Rozumowanie wsteczne wychodzi od celu i stara si ę id ą c do tyłu dotrze ć do

czego ś znanego. Wyobra ż aj ą c sobie drzewiast ą struktur ę schodzimy albo w dół albo do góry ale id ą c do góry

mamy wi ę ksze szanse na trafienie na co ś znanego je ś li nasza baza danych jest ju ż spora. Mo ż emy te ż

zdefiniowa ć podcele, bliskie celowi ko ń cowemu, a do nich pod-podcele, a wi ę c rozbi ć całe rozumowanie na

etapy.

Rozumowanie do przodu okre ś la si ę jako „data driven” lub z dołu do góry. Rozumowanie do tyłu jako „goal

directed” lub z góry na dół. Kombinacje tych dwóch sposobów s ą równie ż spotykane, w szczególno ś ci mo ż na

porównywa ć ró ż nice pomi ę dzy obecnym celem a sytuacj ą w zbiorze wygenerowanych stanów - jest to analiza

ś rodków i celów (means-ends analysis). Z ró ż nicy wnioskuje si ę jaki operator najbardziej warto zastosowa ć by

ja zmniejszy ć , a je ś li nie daje si ę zastosowa ć operatora to wyznacza si ę nowy podcel.

Niezwykle wa ż na jest te ż reprezentacja wiedzy i sytuacji w bazie danych. „State-space representation” to

Wst ę p do Metod Sztucznej Inteligencji

reprezentacja w której u ż ywa si ę bezpo ś redniego rozumowania a operatory tworz ą w ka ż dym kroku jeden nowy

stan (obiekt) w bazie. Rozumowanie wstecz prowadz ą ce do jednego stanu równie ż posługuje si ę tak ą

reprezentacj ą . Je ś li jednak problem dzieli si ę na zbiór podproblemów, np. całkowanie 2/(x 2 -1) rozbija si ę na +,

1/(x-1), -1/(x+1) to mamy reprezentacj ę redukowania problemów (problem-reduction representation).

Najcz ę stsz ą reprezentacj ą sytuacji w grach, gdzie mamy element nieprzewidywalnej odpowiedzi przeciwnika,

jest drzewo gry. Mo ż na te ż spotka ć inne reprezentacje, zale ż nie od specyfik rozwi ą zywanego problemu.

Grafy lub struktury drzewiaste stanowi ą naturalne struktury opisuj ą ce strategie kontroln ą w procesie szukania.

Pocz ą tkowy w ę zeł reprezentuje wyj ś ciow ą sytuacj ę , kolejne zastosowanie operatorów tworzy nowe w ę zły.

Drzewa to szczególne przypadki grafów w których dany w ę zeł ma tylko jednego poprzednika (ojca). Stosuje si ę

te ż ró ż ne specjalne grafy np. grafy i/lub. Z ka ż dym w ę złem wi ąż e si ę pewien opis stanu bazy. Drzewo

wszystkich mo ż liwo ś ci wyznacza przestrze ń szukania. Zwykle d ąż ymy do tego by drzewo tworzone w czasie

szukania było małym podzbiorem całej przestrzeni szukania. Czasami ta przestrze ń jest niesko ń czona a czasem

tylko ogromnie wielka. Np. oceniono liczb ę gier w szachach na 10 120 a w warcabach 10 40 . Jak znale źć drog ę do

rozwi ą zania w tak wielkiej przestrzeni tworz ą c najmniejszy graf szukania?

W prostych przypadkach dobrze działa metoda „wygeneruj i testuj”. Generator nowych stanów czy mo ż liwo ś ci

produkuje hipotezy a tester je sprawdza. Dobre generatory powinny by ć w stanie wygenerowa ć wszystkie

mo ż liwe hipotezy (zupełno ść ), unika ć powtarzania tych samych hipotez oraz u ż ywa ć wszystkich informacji

pozwalaj ą cych wst ę pnie ograniczy ć mo ż liwe hipotezy.

Oczywi ś cie przy szukaniu nale ż y korzysta ć z niepełnej wiedzy czyli wiedzy heurystycznej . Czasami zapobiega

to kombinatorycznej eksplozji drzewa mo ż liwo ś ci. Heurystyczny oznacza „słu żą cy odkryciu”. W AI

heurystyczny oznacza proces mog ą cy - ale nie gwarantuj ą cy - doprowadzi ć do rozwi ą zania, strategi ę , trik,

reguł ę kciuka. Heurystyczny jest wi ę c przeciwstawieniem ś lepego przeszukiwania.

1.2 Reprezentacja problemu w przestrzeni stanów

Reprezentacja to zbiór konwencji dotycz ą cych opisu pewnej klasy rzeczy. Opis problemu wykorzystuje te

konwencje w konkretnym przypadku. Stan systemu jest opisem pozwalaj ą cym na okre ś lenie przyszło ś ci

systemu. W przestrzeni stanów wprowadzi ć mo ż na reprezentacj ę graficzn ą tak, by w ę zły reprezentowały stany

systemu a łuki przej ś cia pomi ę dzy tymi stanami.

Prostym przykładem reprezentacji problemu w przestrzeni stanów mo ż e by ć gra w 8-k ę .

2 1 7

3 8

5 4 6

Przestrze ń stanów liczy sobie 9!/2=181440 elementów. Stan opisywany jest w pełni przez macierz 3 na 3.

Operacje na obiektach polegaj ą na ich przesuwaniu, ale zamiast osobnych operacji na 1 .. 8 lepiej jest

zdefiniowa ć operacje na pustym polu jako ruchy w 4 kierunkach u, d, l, r. Te ruchy to nasz zbiór operatorów O .

Potrzebujemy te ż zbioru stanów wyj ś ciowych S i ko ń cowych G . Problem zdefiniowany jest jako zbiór (S,O,G).

Rozwi ą zanie problemu to sko ń czony ci ą g transformacji lub zastosowa ń operatorów zamieniaj ą cy S w G .

Kolejno ść zastosowa ń operatorów lub nast ę pstwo stanów najlepiej przedstawia si ę w postaci grafu, np. w

problemie w ę druj ą cego komiwoja ż era - jak znale źć najkrótsz ą drog ę przez N miast odwiedzaj ą c ka ż de z nich

dokładnie jeden raz - startujemy od miasta A jako wierzchołku grafu, na drugim poziomie mamy w ę zły AB,

AC, .., na trzecim podw ę zły ABC, ABD, ... ACB, ACD ... i na N-tym mamy N! w ę złów ko ń cowych

obrazuj ą cych wszystkie mo ż liwe drogi. Rozmiary grafów w realnych problemach rosn ą kombinatorycznie,

konieczne s ą wi ę c „inteligentne” metody ich przeszukiwania.

Innym prostym przykładem obrazuj ą cym u ż yteczno ść reprezentacji stanów w postaci grafu jest dzieci ę ca

zagadka: jak przewie źć lisa, g ęś i ziarno mał ą łódk ą na drug ą stron ę rzeki, je ś li zmie ś ci si ę w niej nie wi ę cej ni ż

jedna rzecz (oczywi ś cie oprócz nas). Nale ż y tu rozwa ż y ć wszystkie mo ż liwo ś ci - ka ż da z 3 rzeczy plus

przewo żą cy je farmer mog ą by ć po jednej lub drugiej stronie rzeki, wi ę c mamy 2 4 =16 mo ż liwo ś ci. W ś ród nich

jest 6 niebezpiecznych i 10 akceptowalnych. Na rysunku przedstawiłem tylko mo ż liwo ś ci akceptowalne

Wst ę p do Metod Sztucznej Inteligencji

lis, g ęś , ziarno, farmer

lis, ziarno

g ęś , farmer

lis, ziarno, farmer

g ęś

lis

ziarno

g ęś , ziarno, farmer

lis, g ęś , farmer

ziarno, g ęś , farmer

ziarno

lis

g ęś

lis, ziarno, farmer

g ęś , farmer

lis, ziarno

g ęś , lis, ziarno, farmer

Rys. Graf rozwi ą za ń dla prostego problemu logicznego

pomijaj ą c w ę zły ś lepe, które nie prowadz ą do rozwi ą zania. Zagadka ta znana jest równie ż pod nazw ą problemu

misjonarzy i kanibali i dla wi ę kszej liczby osób lub obiektów nie jest wcale trywialna, gdy ż wymaga tworzenia

po ś rednich etapów, które „oddalaj ą si ę ” od po żą danego rozwi ą zania.

W tym przypadku reprezentacja w przestrzeni stanów jest dobr ą reprezentacj ą prowadz ą c ą do łatwego

rozwi ą zania problemu. Ogólnie mo ż na zauwa ż y ć , ż e:

Dobór odpowiedniej reprezentacji to znaczna cz ęść rozwi ą zania problemu.

Je ś li liczba w ę złów ro ś nie eksponencjalnie lub kombinatorycznie mówimy, ż e zagadnienie jest nieobliczalne.

Od reprezentacji sytuacji zale ż y cz ę sto bardzo wiele. Rozwa ż my dla przykładu nast ę puj ą ce zadanie: czy 31

domin mo ż e pokry ć wszystkie pola szachownicy z której usuni ę to 2 rogi? Mamy tu bardzo wiele mo ż liwo ś ci ale

wystarczy zauwa ż y ć , ż e domino pokrywa zawsze biało/czarne pole a usuwamy dwa pola o tym samym kolorze.

Jak znale źć w konkretnym przypadku odpowiedni ą reprezentacj ę problemu tak, by dał si ę łatwo rozwi ą za ć , albo

przynajmniej lepsz ą reprezentacj ę ni ż która ś z ogólnie stosowanych? Jest to cz ę sto najtrudniejsza cz ęść pracy.

Dobra reprezentacja uwidacznia relacje pomi ę dzy istotnymi elementami lub stanami, pozwala na ujawnienie si ę

wszystkich wi ę zów ograniczaj ą cych mo ż liwe relacje, nieistotne szczegóły zostaj ą usuni ę te, powinna by ć przy

tym zrozumiała, kompletna (zawieraj ą ca wszystko, co potrzeba do rozwi ą zania), zwi ę zła i pozwalaj ą ca na

Wst ę p do Metod Sztucznej Inteligencji

efektywne wykorzystanie w modelu komputerowym.

1.3 Redukcyjna reprezentacja problemu

Podstawowymi strukturami s ą tu nie stany, ale cele, czyli opisy problemu. Pocz ą tkowy opis problemu poddaje

si ę serii transformacji, a ż dochodzimy do problemów elementarnych. Redukcyjna reprezentacja składa si ę wi ę c

Opisu pocz ą tkowego problemu

Zbioru operatorów transformuj ą cych dany problem na problemy cz ą stkowe

Zbioru problemów elementarnych

Przykład: Wie ż a z Hanoi

Mamy trzy wielko ś ci kr ąż ków, A, B, C, i trzy kołki , i, j, k . W tym przypadku problem przesuni ę cia n>1

kr ąż ków z i na k rozbija si ę na podproblemy:

Przesu ń stos n-1 klocków z i na j

Przesu ń jeden klocek z i na k

Przesu ń stos n-1 klocków z j na k

Problemem elementarnym jest oczywi ś cie przesuni ę cie pojedynczego klocka. Opis problemu zawiera dane: ile

jest klocków na stosie do przesuni ę cia, z którego kołka, na który kołek. Rozwi ą zanie mo ż emy znowu

przedstawi ć przy pomocy drzewa. Pewnym uogólnieniem prostych drzew s ą grafy AND/OR, na których

zaznacza si ę , czy dany problem daje si ę rozwi ą za ć , je ś li wszystkie podproblemy daj ą si ę rozwi ą za ć (w ę zeł

AND), czy te ż wystarczy rozwi ą za ć tylko jeden z nich (w ę zeł OR).

Któr ą z tych dwóch reprezentacji - opisu problemów czy przestrzeni stanów - nale ż y u ż y ć jest kwesti ą wygody.

Mo ż na tłumaczy ć problemy z jednej reprezentacji do drugiej ale cz ę sto w jednej z nich łatwiej si ę daj ą

rozwi ą za ć ni ż w drugiej. Jest wiele innych metod reprezentacji do których wrócimy w nast ę pnym rozdziale,

gdy ż metody reprezentacji wiedzy to centralne zagadnienie sztucznej inteligencji.

1.4 Metody szukania na

lepo

Reprezentacja stanów, reprezentacja redukcyjna i inne metody prowadz ą w praktyce do tych samych

problemów tj. do konieczno ś ci szukania rozwi ą zania w obszernej przestrzeni mo ż liwych stanów lub mo ż liwych

zastosowa ń operatorów redukuj ą cych. Jest wiele metod prowadzenia takiego szukania (szczegółowe omówienie

zawiera ksi ąż ka Bolca i Cytowskiego). Ograniczymy si ę tutaj tylko do podstawowych metod przeszukiwania

„na ś lepo”. Szukanie drogi w grafie prowadz ą cej od pocz ą tkowego w ę zła do w ę zła, który jest celem daje si ę

przedstawi ć jako proces tworzenia drzewa poszukiwa ń . Drzewo jest szczególnym rodzajem grafu w którym

ka ż dy z w ę złów ma tylko jednego rodzica. Dzi ę ki temu w ę zły drzewa mo ż na uto ż sami ć z drogami. Drzewo ma

swój korze ń (root node) i li ś cie, czyli w ę zły nie maj ą ce swoich nast ę pników lub dzieci. Okre ś lanie poddrzewa

danego w ę zła nazywa si ę te ż rozwijaniem w ę zła. O w ę złach, które nie s ą do ko ń ca rozwini ę te mówi si ę , ż e s ą

„otwarte” a o całkowicie rozwini ę tych „zamkni ę te”. W drzewie okre ś li ć mo ż na ś redni ą liczb ę rozgał ę zie ń

(branching factor). Je ś li wynosi ona k to rozwini ę cie w ę zła na gł ę boko ść d prowadzi ś rednio do k d nowych

w ę złów, czyli do eksplozji kombinatorycznej. Jedynie dla prostych przypadków mo ż na wyliczy ć wszystkie

mo ż liwe ś cie ż ki drzewa przeszukiwa ń i wybra ć z nich najlepsze rozwi ą zanie. Skrajnie ró ż na wersja tej metody,

okre ś lanej jako „generuj rozwi ą zanie i testuj czy jest wła ś ciwe” polega na przypadkowym wyborze jednego z

rozwi ą za ń i sprawdzeniu, czy jest ono wła ś ciwe. W literaturze ameryka ń skiej takie post ę powanie okre ś la si ę

nazw ą „ procedury Brytyjskiego muzeum ” - szanse na znalezienie jakiego ś obiektu w ogromnym Muzeum

Brytyjskim przypadkowo bł ą dz ą c po salach i magazynach s ą bardzo małe. Potrzebne s ą bardziej systematyczne

podej ś cia.

Wst ę p do Metod Sztucznej Inteligencji

1.1.4. Szukanie „w gł

b”

Podstawowym rodzajem przeszukiwania grafów jest szukanie w gł ą b. Je ś li w danej sytuacji wszystkie

posuni ę cia lub wszystkie kolejne stany s ą równie prawdopodobne to robimy nast ę pny krok tworz ą c, na grafie

przedstawiony jako przesuni ę cie si ę na kolejny, ni ż szy poziom, a ż dochodzimy do poziomu, na którym nie ma

ju ż dalszych mo ż liwych przekształce ń . Je ś li poziom ten reprezentuje wła ś ciwe rozwi ą zanie zako ń czyli ś my

proces szukania. Formalny algorytm wygl ą da nast ę puj ą co:

Utwórz jednoelementow ą list ę składaj ą c ą si ę z ś cie ż ki o zerowej długo ś ci wychodz ą cej z korzenia

spacja

L D

M W Y

G P

Drzewo binarne (drzewo Huffmana) obrazuj ą ce minimaln ą liczb ę bitów potrzebn ą do zakodowania litery w

j ę zyku angielskim (uwzgl ę dniaj ą c cz ę sto ś ci wyst ę powania liter). Algorytm przeszukiwani a w gł ą b pozwoli

szybko odnale źć litery zakodowane przy pomocy du ż ej liczby pocz ą tkowych zer, algorytm szukania w szerz

litery o najbardziej oszcz ę dnym kodowania ale litery o najmniej oszcz ę dnym kodowaniu jest stosunkowo trudno

znale źć (w tak małym drzewie nie ma z tym oczywi ś cie problemu).

Dopóki pierwsza ś cie ż ka na li ś cie nie ko ń czy si ę na w ęź le zawieraj ą cym cel, lub lista nie jest pusta:

•

Usu ń pierwsz ą ś cie ż k ę ; utwórz wszystkie ś cie ż ki wychodz ą ce z ko ń cowego w ę zła

•

Odrzu ć ś cie ż ki zawieraj ą ce p ę tle

Je ś li który ś z nowo utworzonych w ę złów jest celem zako ń cz p ę tl ę

Dodaj na szczyt listy pozostałe ś cie ż ki

Je ś li znaleziono rozwi ą zanie to ogło ś sukces i podaj ś cie ż k ę prowadz ą c ą do celu, w przeciwnym przypadku

ogło ś kl ę sk ę .

Program pami ę ta dane o kolejnych odwiedzanych w ę złach i wybranych łukach, co pozwala na cofanie si ę po

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: