35 1024x768

Dcpch-lirsl scarch may be implcmentcd by modifying brcadth-first scarch to maiotain opon as a si3ck. This iunply m\olvcs rcvcrsing ihc order oflhc argumentu to append.

15.4.2 Bcsi-First Search

Ucst-lirst scarch nu> be implcmentcd through Mraightforwanł modidcalions to the brcadth-tir>( search algorithm. Spccifically. the heuristie cvaluation is savcd along v%ith cach statc. The tupies on "opon* are then sorted according to this cvaluation. The data typc dcfinitiorts for statc records are an extcnsion of thosc used in brcadth-first scarch:

(dofun build-record (State parani dopth weight)

(Hat stata parem depth weight))

(dofun get-state (state-tupto) (nth 0 state-tuple))

(defun get-parent (state-tuplo) (nth 1 state-tuple))

(dofun get-depth (state-tuplo) (nth 2 state-tuplo))

(defun get-weight (state-tuplo) (nth 3 state-tuple))

(defun rotrieve-by-state (State list)

(cond ((nuli list) nil)

((equal State (get-state (car list))) (car list))

(t (retrieve-by-state State (cdr list)))))

best-first and generate-descendants are defined:

(dofun best-first ()

(cond ((nuli "open*) niI)

(I (let ((siato (car "open")))

(so*q "closed" (eona stato "closod"))

(cond <(equal (get-state stato) "goal") (build-solution "goal"))

(t (sotq "opon*

(insert-by-weight

(genorato-doscondants (get-state stato)

(♦ 1 (got-dopth stato)) *movos") (cdr "opon")))

(best-first)))))))

(dofun generate-descendants (stato depth moves)

(cond ((nuli moves) nil)

(t (let ((chlld (funcall (car moves) State))

(rest (generate-descendants State depth (cdr moves)»)

(cond ((nuli chlld) rest)

((retrieve-by-state chlld rest) rest)

((retrieve-by-state chlld "open") rest)

(<retrieve-by-state chlld "closod") rest)

(t (cons (build-rocord chlld State depth

(♦ depth (heuristie chlld))) rest)))))))

The only dificrcnccs bctwccn best-first and breadth-flrst scarch are the usc of insert-by-weight to sort the records on "open* by heuristie wcights and the computation of scarch depth and heuristie wcights in generate-descendants.

PART VII LANGUAGES FOR Al PROBLEM SOLVING

Compktion of best-first rcquirc» a dctiniiion of 1nsert*by weight Tlris functton ukcs an uinołtcd list of State records and insert* them. one M a limę. into thor ippropiiac poation* in “open*. It also reąuires a problcm-spccific defintion of heurfetic. This foaction tak es a stale and. using the global 'goal*. computrt a hcuiuńc «rt|ta for that tute. We tcave the dcllnition of thcsc functiom as an cxćicise for the reader.

1S.5 Pattem Matching in L1SP_,

panem matching is an important Al mcthodology that has alrcady bcen (foeuwed in the PROLOG chaptcrs and the discussion of production systems. In this Mdion sc impłement a reeurshe pattem matchcr and usc it to build a pattcm-dircctcd rcuicv»l functioo for a jimplc databasc.

The hcart of this rctricval system is a funetkw callcd mat eh. wtuch takes as uguments two s-cxpcessions and returns t if the espressioas niaich. Matching rcquim that both exprcssions have the same ttmeture. as »cłl as hsviag idemkal atonw in corresponding positions. In addition. match alkms the indusion of \ariabJcs. dcnotćd by ?. in an s-cxpcession. Variablcs are allowcd to match with any s-cxpre*sion. cithcr a Iw or anatom, bul do not savc bindings. as with fuli unification. Examplcsofthedesiredbcbav-ior for match appear bclow. If the cxamplcs secm rcmmnccnl of the PROLOG europie* ii Chitpter 14. this is bccause match is actually a simplified \cnaoa of the unification alforithm that forms the hcart of PROLOG, as wdl as mam other pattcm-dircctcd Al syv kitu. In Scction 15.6 we cxpand match mto the fuli unification algorithm by aBoariag ■amed variab!cs and returning a list of bindings rcąuircd fora match.

>    (match '(likes bill winę) '(likes bill wina)) t

>    (match '(likes bill winę) '(Ukos bill młlk)) ii

>    (match '(likes bill ?) '(likes bill wino))    : example wHh a variable

t

>    (match '(likes ? winę) '(likes bill ?))    : notę variab1es in bolh wprossions

I

>    (match '(likes bill ?) '(likes bill (prolog lisp smalitalk)) t

>    (match '(likes ?) '(likes bill winę)) nfl

match is uscd to deftne a funciion callcd get*matches. which takes as arpuacnts tao s<xprcssions. The first argument is a panem to be matebed agama ckmeats of the wond s-cxprcssion. which musi be a list. get-matches returns a hst of the element* of 6c list that match the first argument In the csampfe belo*, get-matches t$ uscd to *tńc%e records from an employee database as dcscribed carlicr m this charter

Becausc the database is a large and rebthely compk* s-c\prcs»ion. me hme bouad it to the global variablc ‘database* and usc that \ariabk as an argument to get-matches. This was donc to improvc readability of Ute cxampłes-

715

CHAPTER15 / AM MTROOUCTION TO USP