08 1024x768

path(Z, Z. I).

_paU)(X. Z. I)move(X. Y). not(membor(Y. L)). path(Y. Z. [Y|L]).!.

ihc addinon ofcut mean> ilui (at most) one solution to the graph search is produccd. 0% one sohmon i» produccd bccausc further Solutions occur after the clause path(Z, Z, L) is iaiKhcd |f the uscr asks tor morę Solutions. p<ith(Z. Z. L) faijs, and the sccond path nil »reimokcd to cootinue the (exteustivc) scarch of the graph. W hen the cut is plaćed after the recursne path cali. the cali cannót be reentered (hackcd into) for further scarch.

Importom siile cflccts of the cut aro to make the program run faster and to consctYc mcmory localions. "hen cut is uscd within a prcdtcatc. the pointers in mcmory nccdcd for backtracking to predicatcs to the left of the cut arc not crcatcd. This is, of coursc, bccatsc they will no er be nccdcd. Thus. cut produccs the desired solution. and only the dewed solution. with morę eflicient use of meroory.

The cut can also be uscd with recureion to reinitializc the path cali for further scarch within the graph. This will be dcmonstratcd with the generał scarch algorithms presend in Scction 14.3. For this purposc we also need to dcvclop scvcral abstnict data types.

14.2 Abstract Data Types (ADTs) in PROLOG_

Programming in any cmironmcnt is enhaneed by proccdural abstractions and infomuikc hiding. Bccause tbc set. stack. queue. and priority queue data structures wcrc Ac suppoit constructs for the graph scarch algorithms of Chapters 3.4. and 5. we build thea m PROLOG in the presera scction and then use them in the design of the PROLOG srani algorithms presented later in this chnpter.

Rccursion, lists. and paltem matching. as emphasized throughout this book. arc the pnnury tools for building and scarching graph structures. Thcsc arc the pieccs with \\hicfc we build our ADTs. Ali list handling and recurśivc Processing that dolinę the ADT m “hiddcn” within the ADT abstraction. quite dilTercnt tłum the normal static data structurc.

14.2.1 The ADT Stack

A Mack is a lincar structurc with acccss at one end only. Thus all clcmcnts must be adtkd to. pushed. and rcmoved. popped. from the structurc at that end of acccss. The stack a someńmes rcfcrrcd to as a last-in-first-out (LIFO) data structurc. We saw its use ttj& dcpth-llist scarch in Scction 3.2J. The operators that we will deftne for a stack arc:

1.    Test whether the stack isempty.

2.    Push an demem onio the stack.

3.    Pop. or rerom c. the top element from the stack.

4.    Peek (oflen calkd Top) to sec the top element on the stack without poppiog i-

5.    Membor,stack. which chccks whether an element is in the stack.

PART VI / IANOUAGM FOR Al PROBLEM SOLVING

6. Add .list. which ndds a lisi of element* lo the stack.

Operator* 5 and 6 nury be built from I -4.

We now build thcsc operatora in PROLOG. As just noted we use the lisi primitives:

I. ompty_stack([ J). This predicate can be uscd cithcr to test a stack to sce whether it is empty or to generale a ncw empty stack.

2-4. stack (Top. Stack. (Top j Stack]). This predkate perforros the push. pop. and poek predicatcs depending on the variablc bindings of its argument*. Far instancc. push produccs a ncw stack as the third argument when the fiest twe argument* arc bound. Likcwisc. pop produccs the top element of the stack w hen the third argument is bound to the stack. The sccond argument will then be bound to the ncw stack. once the top element is popped. FinaJly. if we kccp the stack as the third argument, the first argument lets us pcck at its top element.

5.    momber_stack(Element, Stack)member(Eloment. Stack). Thisallows us to dclcrminc whether an element is a mcm ber of the stack. Of coursc. the same rcsult could be produccd by creating a recurehe cali that pceked at the ncxt element of the stack and then. if this element did not match Element popped the stack. This would continue umil the empty stack predicate was tnie.

6.    add list. to _stack(Llst. Stack. Result) :• append(List, Stack. Result). List is added to Stack to producc Result. a ncw stack. Of coursc. the same rcsult could be obiained by popping List and pushing cach element onto a temporary stack umil empty stack is truć of List. \Ve then pop the temporary stack and push cach element onlo the Stack umil empty stack is tnie of the temporary stack. append is dcscribcd in detali in Section 14.8.

A finał predicate for printing a stack in rcverse order i» rovorso print stack This b \xty uscful w hen a stack has. in rcvencd order, the currcnt path from the start State to the prrscnl stale of the graph search. We will see scvcral cxamp!cs of this in the following ubsections.

revors© print stack(S)empty_stack(S).

reverso_print_stack(S) > stack(E. Rest. S). revers© print .stack(Rest). write(E). nl.

14.2.2 The ADT Qucuc

At/ucuc is a first-in-lirst-out (FIFO) data structurc. It is oflcn charactcn/cd as a list wherc element* arc taken olT (dcqucucd) from one end and added to (cnqueucd) at the ocher cod Tbcqucue was uscd for defining brcadth-first scarch in Chapters 3 and 4. The qucuc oper-non arc:

CHAPTER 14 / AN INTROOOCTION TO PROLOG