人工智能技术简明教程 教学课件 作者 廉师友 第3章 图搜索与问题求解.ppt

/*状态图搜索通用程序*/ DOMAINS state=领域说明 %例如:state=symbol DATABASE-mydatabase 　　 open(state,integer) 　%用动态数据库实现OPEN表 　　closed(integer,state,integer) %和CLOSED表 　　 res(state) 　　 open1(state,integer) 　　min(state,integer) 　　mark(state) 　　 fail_ CLAUSES search(StartingCity,CitySum): - retractall(_,mydatabase),assert(closed(0,st(［］,0),0,0)), assert(open(st(［StartingCity］,0),0,0,0)),  assert(mark(StartingCity,CitySum)), repeat, searching,!. searching: -  open(State,BackPointer,Gx,_), retract(open(State,_,_,_)),  closed(No,_,_,_),No2=No+1,  asserta(closed(No2,State,BackPointer,Gx)), !,step4(No2,State,Gx). searching: -assert(fail_). result: -not(fail_),closed(_,st(L,_),_,G),write(L,G). result: -beep,write(″sorry dont find a road!″). step4(_,st(L,N),_): -mark(_,StateSum),N=StateSum.  step4(No,State,Gx): -step56(No,State,Gx),!,fail. step56(No,st(L,N),Gx): - %Gx为当前节点的代价 rule(st(L,N),StateY,Grule), %Grule为规则的代价(即边代价) not(open(StateY,_,_,_)), %StateY为扩展得到的子节点 not(closed(_,StateY,_,_)), calculator(N,Gx,Grule,Gy,Fy),  asserta(open(StateY,No,Gy,Fy)),  fail. step56(_, _, _): -sort,!. % 按估价函数值对OPEN表以升序排序 calculator(N,Gx,Grule,Gy,Fy): - Gy=Gx+Grule, %计算子节点的代价值g(y) mark(_,CitySum), mindist(MinD), Hy=(CitySum-N-1)*MinD, %计算子节点的启发函数值h(y) Fy=Gy+Hy,!. %计算子节点的估价函数值f(y)=g(y)+h(y) mindist(MinD): - ? road(_,_,D1),assert(minD(D1)),mindist1,minD(MinD),!. mindist1: -road(_,_,D),pa(D),fail. mindist1: -!. pa(D): -minD(Do),DoD,retract(minD(_)),assert(minD(D)),!. pa(_): -!. sort: -not(open(_,_,_,_)),!. sort: -repeat,open(X,N,G,F),assert(min(X,N,G,F)),p1,not(open(_,_,_,_)),p2. p1: -open(X,N,G,F),p12(X,N,G,F),fail. p1: -min(X,N,G,F), assertz(open1(X,N,G,F)),retract(open(X,N,G,F)),retract(min(_,_,_,_)),!. p12(_,_,G,Fn): -min(_,_,_,Fo),Fo=Fn,!. p12(X,N,G,Fn): -r