13 1024x768

Wc n»n\ prcsent a »hcll structurc for dcpth-flrst scarch in PROLOG, kccping track of hoUi open and dosed and checking cach ne\v statc lo bc surc ił was not piwiowly v «M*od. path has ihroc annimcnts. the Open .stack. Closed._set. mainiaincd os a set. and the Goal statc. The currcnt statc. State, is the ncxt statc on the Open_stack. The stack and set operator* arc found in Scction 14.2.

Scarvh starts by a go prcdicatc that initiali/cs the path cali. Noce that go place* the Stert statc with the nil pa rent. (Start, nil], alonc on Open _stack; Closed_set isempty:

go(Start. Goal)

empty stack(Empty opon).

stack((Start. nil], Empty opon. Open_stack),

empty _set(Closod. sof).

path(Open stack. Closed set. Goal).

The threc-argument path cali is:

peth(Open stack. J

ompty stack (O pen stack). writoCNo sołutlon found willi those rules*). path(Opon stack. Cios od set. Goal)

siack([State. Parent]. Opon stack). State = Goal. writefA Solution is Found!’), nl, phr»tsotution([State. Parent], Closed_set). path(Open stack. Closed..set, Goal) :-

stack([State, Parent], Rost opon stack. Open stack). get_children(Statc. Rest_open_stack. Closed_set. Children). add_list_to_.s«ack(Children. Rest.open stack. New_open_stack). union([[State. Parent]]. Closed_set. New. closed _set). path(New. opon stack. New.closed_set. Goal). I. get_children(Stato. Rost_open_stack. Closod_set. Children) bagof(Cbild. moves<State. Rest opon stnek.

CIosod_sot. Child). Children). moves(State. Rost_open_stack. Closed_sot. [Next. State]) move(Stato. Next),

not(unsafe(Next)>.    % test depends on probłaa

not(membor_ stack([Next, J. Rost_open.stack)). not(member_set((NextJ. Closed_ set)).

Wc assume a set of move rules. and. if ncccssary. nn unsafo prcdicatc:

move(Present_state. Next_stato) :• ...    % test Arst roi*

move(Present stale. Next_state)    % test second aria

The first path cali terminale* scarch when the Opon_stack is empty. which mcans thcrc arc no morc ttaies on the open list to continuc the scarch. Thia usually mdkaKiM the graph ha* bcen cxhaustivcly scarchcd. The second path cali terminale* and prmuctf

ihc sohriion palh whcn the solution b found. Since the tfam of the graph scarch arc main-diiMil as (Siato. ParontJ pairs. prfntsofutfon will go to the Cfosed.set and recurmeły irbuild the solution path. Notę that the soJulion is prirted from Mart lo goal.

printsołotion((Stato. nil). J writo(Stato). nl.

printsolution((Stato. ParontJ, Closed sot)

mombor sot((Poront. Grandparont], Closed set). printsoIution((Parent. GrandparenlJ. Closed .set). wrifofStato). nl.

The tliird path cali uses bagof. a PROLOG prcdicatc standard to most interpreter*, bagof kts us gather all the unifications of a patiem inco a single list. The second parameter to bagof b the panem prcdicatc to be matchcd in the databaae. The fint parameter spoci lics the components of che second parameter that wc trish to colIceŁ For eutnplc. we may be interested in the valucs bound to n single \ariable of a prcdicatc. All bindmgs of the lirst parameter rcsuUing from these matches arc collecicd in a lisi and bound to the third parameter.

In thi* program, bagof collects the States rcnchcd by firing al? of the cnablcd stoduction rules. Of coursc. this is ncccssary to gather all dcsccndants of a pariicular siatę ao that we can add them. in proper order, to open. The second argument of bagof, a ncw prcdicatc named moves. calls che move prcdicMCś 10 generale all the States that may be ■sched using the production rules. The arguments to moves arc the present stale, the open list. the closed set. and a variablc that b the statc rcachcd by a good mow. Bcforc Ktuming this stale. moves checks chał che nem stair. Most b noc a raember of eilher rosi opon stack. open oncc the present statc b rcmovcd. or dosod_set bagof calb movos and cołlccts all the States that mect these conditions. The third argument of bagof Au represents the ncw States that are to be placcd on the Open_8tack.

la some implcmcntaiions. bagof fails whcn no matches exist for the second argument ad ihus the third argument b empty. This can be retnedied by substituting (bagof(X. moves(S. T. C. X), List); List = [ ]) for the currcnt calls to bagof in the codę.

Fmalły. bccause the States of the scarch are represemed as mte-parent pairs. the member chcck prcdicatc*. c.g.. membor_aot. must be revbcd to rcflcct the stmeture of the panem matching. We need to test to sec if a statc-parent pair is idcncica! to the firn element of a list of *tstc-parcnt pairs and then rccur if it isn’t:

mombor sot((Stato. Parent]. [(State. Parentjl J). mombor_sot(X. (_|T]) momber_set(X. T).

M.4.2 Brcadth-First Scarch in PROLOG

We nom present the sheil of an algorithm for brcadth-Unt scarch using explicit open and cłosed lists. The shell can be uscd with the movo rules and unsafa predicaies for sny ***** problem. This algorithm is callcd by:

CHAPT6R 14 / AN INTROOUCTlON TO PHOtOO 627