人工智能作业—迷宫问题.doc

人工智能大作业 班级：13111 学号：13111 姓名：一、问题描述在如图所示的迷宫，找出从起点（1,1）到终点（4,4），要求步数最小.1：初始状态，入口处。2：目标状态，出口处3：操作方式 下上右左二、解题步骤：1：设估价函数：f(n)=g(n)+h(n);g(n)=d(n);h(n)=|Yg-xn|+|Yg-yn|;:2： 将迷宫问题转化为格子问题3：按照操作步骤得到状态空间树如下：11,1g=0,h=7,f=75,1161514131211105,25,34,34,24,12,187654325,44,43,43,33,11,2g=1,h=6,f=72,2g=2,h=5,f=73,2g=3,h=4,f=79g=4,h=5,f=9g=4,h=3,f=7g=5,h=2,f=7g=5,h=6,f=11g=5,h=4,f=9g=6,h=1,f=7g=6,h=3,f=9g=7,h=0,f=7g=7,h=2,f=9g=8,h=1，f=9g=9,h=2,f=11,g=10,h=3,f=134 根据状态空间树得到open表，close表如下：节点父节点f(n)1无7217327437949547657767877169111099111091211913129141311151413编号节点父节点f(n)887777676657554744373327221711无7根据上表得出路径为s1-s2-s3-s4-s5-s6-s7-s8-sgtracedomainsstate=symboldatabase-mydatabaseopen(state,integer)closed(integer,state,integer)res(state)mark(state)fail_predicatessolvesearch(state,state)resultsearchingstep4(integer,state)step56(integer,state)equal(state,state)repeatresulting(integer)rule(state,state)road(state,state)goalsolve.clausessolve:-search(s0,sg),result.search(Begin,End):-retractall(_,mydatabase),assert(closed(0,Begin,0),assert(open(Begin,0),assert(mark(End),repeat,searching,!.result:-not(fail_),retract(closed(0,_,0),closed(M,_,_),resulting(M),!.result:-beep,write(sorry dont find a road!).searching:-open(State,Pointer),retract(open(State,Pointer),closed(No,_,_),No2=No+1,asserta(closed(No2,State,Pointer),!,step4(No2,State).searching:-assert(fail_).step4(_,State):-mark(End),equal(State,End).step4(No3,State):-step56(No3,State),!,fail.step56(No4,StateX):-rule(StateX,StateY),not(open(StateY,_),not(closed(_,StateY,_),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(