《人工智能第二次作业》由会员分享，可在线阅读，更多相关《人工智能第二次作业（7页珍藏版）》请在金锄头文库上搜索。
1、1迷宫实例迷宫实例S迷宫算符 上，右，下，左S2S4 S5 S6S8 规则(S5,S2) (S5,S6) (S5,S8) (S5,S4)迷宫状态空间图如下：S02road(S0,S1) ,road(S1,S2) ,road(S1,S4) ,road(S1,S0) ,road(S2,S3) ,road(S2,S5) ,road(S2,S1) ,road(S3,S2) ,road(S4,S1) ,road(S4,S7) ,road(S5,S2) ,road(S5,S8) ,road(S6,Sg) ,road(S6,S9) ,road(S7,S4) ,road(S7,S8) ,road(S8,S5)
2、 ,road(S8,S9) ,road(S8,S7) ,road(S9,S6) ,road(S9,S8) Open 表 节点 父节点 S0 0=无 S1 1=S0 S2 2=S1 S4 2=S1 S3 3=S2 S5 3=S2 S7 4=S4 S8 6=S5 S8 7=S7 S9 8=S8 S7 8=S8 S5 9=S8S1S3S2S444S7S5S7S8S8S9SgS6S5S2S9SgS3S63S9 9=S8 S6 10=S9 S4 11=S7 S2 12=S5 S6 13=S9 Sg 14=S6 S3 16=S2 Sg 17=S6Closed 表 编号 节点 父节点 18 Sg 14=S6
3、 17 S6 13=S9 16 S2 12=S5 15 S4 11=S7 14 S6 10=S9 13 S9 9=S8 12 S5 9=S8 11 S7 8=S8 10 S9 8=S8 9 S8 7=S7 8 S8 6=S5 7 S7 4=S4 6 S5 3=S2 5 S3 3=S2 4 S4 2=S1 3 S2 2=S1 2 S1 1=S0 1 S0 0=无 0 S0 0=无Res mark Fail_ S0 Sg fail_=fail_() S1 S2 S5 S8 S9 S6 Sg分支界限树如下(由于节点全部展开所以两个树相同)S04Prolog 代码trace DOMAINS state
4、=symbol DATABASE-mydatabase open(state,integer) %OPEN 表 closed(integer,state,integer) %CLOSED 表 res(state) %S0Sg 的结果路径节点 mark(state) %放目标节点 fail_%等价 fail_() PREDICATES solve search(state,state) result searching step4(integer,state) step56(integer,state) equal(state,state) repeat resulting(integer) r
5、ule(state,state) road(state,state)S1S3S2S444S7S5S7S8S8S9SgS6S5S2S9SgS3S65GOAL Solve. CLAUSES solve:-search(s0,sg),result. 搜索 search(Begin,End):-retractall(_,mydatabase), assert(closed(0,Begin,0), assert(open(Begin,0), %步 1 将初始节点放入 OPEN 表assert(mark(End),repeat,searching,!. result:-not(fail_), retrac
6、t(closed(0,_,0),closed(M,_,_), resulting(M),!. % 输出解 result:-beep,write(“sorry dont find a road!“).searching:-open(State,Pointer),%步 2 若 OPEN 表空, 则失败,退出 retract(open(State,Pointer),closed(No,_,_),No2=No+1, asserta(closed(No2,State,Pointer),!,step4(No2,State). searching:-assert(fail_). %步 3 取 OPEN 中第
7、一个节点,给其编号，放入 CLOSED 表 %步 4 若当前节点为目标节点, 则成功，转步 2step4(_,State):-mark(End),equal(State,End). %步 4 若当前节点不是目标节点, 则判断该节点是否可扩展？step4(No3,State):-step56(No3,State),!,fail. %步 5 若当前节点不可扩展, 转步 2step56(No4,StateX):- rule(StateX,StateY), %步 6 扩展当前节点 X 得 Y not(open(StateY,_), %考察 Y 是否已在 OPEN 表中 not(closed(_,Sta
8、teY,_), %考察 Y 是否已在 CLOSED 表中 assertz(open(StateY,No4),fail.%可改变搜索策略 step56(_,_):-!. equal(X,X). repeat. repeat:-repeat. resulting(N):- closed(N,X,M),asserta(res(X),resulting(M). resulting(_):-res(X),write(X),nl,fail. resulting(_):-!.rule(X,Y):-road(X,Y).road(S0,S1) .road(S1,S2) .road(S1,S4) .road(S1,S0) .road(S2,S3) .road(S2,S5) .road(S2,S1) .road(S3,S2) .road(S4,S1) .road(S4,S7) .road(S5,S2) .road(S5,S8) .road(S6,Sg) .road(S6,S9) .road(S7,S4) .road(S7,S8) ,road(S8,S5) .road(S8,S9) .road(S8,S7) .road(S9,S6) .road(S9,S8). 6程序运行图如下编译成功其中的一个步骤7最后结果
