人工智能答案.doc

、f、s、v分别指示农夫、狐狸、小羊、菜,且每个变量只可取值1(表示在左岸)或0(表示在右岸)。问题状态可以四元组(f,w,s,v)描述,设初始状态下均在左岸,目标状态下都到达右岸。从而,问题求解任务可描述为(1,1,1,1)->(0,0,0,0)由于问题简单,状态空间中可能的状态总数为2×2×2×2=16,由于要遵从安全限制,合法的状态只有(除初、目状态外):1110,1101,1011,1010,0101,0001,0010,0100;不合法状态有:0111,1000,1100,0011,0110,1001设计二类操作算子:Lx、Rx,x为o、f、s、v时分别指示农夫独自,带狐狸,带小羊,带菜过河;,故而解答路径可有无数条,但最近的只有二条;)深度优先搜索算法删去原算法的Close表,其它参数和操作同原算法,新算法如下:(1)G:=S;(2)OPEN:=(S);(3)若OPEN表为空,则算法以失败结束;(4)n:=MOVE-FIRST(OPEN);(5)若n是目标状态节点,则搜索成功结束,并给出解答路径;(6)扩展节点n,将非节点n祖先的子节点加到OPEN表的前部,并建立从子节点到父节点n的指针;(7)返回语句(3)。作为该算法的改进,可以保留Close表,,不应再进入OPEN表(因为其指示了不成功的搜索).每当OPEN表中的节点被当前节点n再一次扩展出来时,)爬山法删去OPEN表和Close表以及MOVE-FIRST(OPEN)操作,:(1)G:=n:=s;(2)若n是目标状态节点,则搜索成功结束,并给出解答路径;(3)扩展节点n,对于非祖先的每个子节点ni,计算h(ni),并取h(ni)最小的ni作为n'(下一个要扩展的节点);(4)若h(n)<h(n'),则算法以失败结束;(5)n:=n',返回语句(2)。、2、3,原先由节点1扩展出的节点标记为4;显然,节点2是全新节点,直接建立指向父节点的指针;节点3有二个父节点,经由新父节点到顶节点更近,就将节点3指向原父节点的指针改变为指向新父节点;节点1也有二个父节点,经由新父节点到顶节点更近,就将节点1指向原父节点的指针也改变为指向新父节点;节点4因节点1的指针变动而受影响,改为经由节点1到顶节点更近,所以将节点4指向原父节点的指针改变为指向节点1。4. OPEN和CLOSE表内容循环初始化1234OPEN表(S)(ABCD)(BCDEF)(ICDEFH)(JCDEFH)CLOSE表()(S)(SA)(SAB)(SABI)5(KCDEFHL) (SABIJ)6 (MCDEFHLNP) (SABIJK),L表中只记载皇后所在列,皇后所在行可由在L表中的先后位置指示,例如L=(13)指示两个皇后位置分别为第1行第1列和第2行第3列。搜索图(树)如右图所示:共回溯22次,其中算法第2步的回溯18次,算法第4次的回溯4次。:(1)调用参数改作状态列表S-L,其包含从当前状态到初始状态路径上的所有状态节点;初始时只包含初始状态节点,且每次新状态节点加进S-L时均加到表首。另外,增加指示搜索深度上限的参数d。(2)增设二个回溯点:旧状态出现时回溯(新算法第2句),搜索深度超限时回溯(新算法第3句)。(3)建立新函数FIRST(S-L),取出S-L的表首节点,但该节点不从S-L表中删除;MEMBER(n,TAIL(S-L)),检查n是否在S-L表中出现二次;LENGTH(S-L)指示表长。新算法BACKTRACK(S-L,d)(1)n:=FIRST(S-L);(2)若n是目标状态,则S-L表就记载了解答路径,算法成功终止;(3)若LENGTH(S-L)>d,则算法的本次调用失败,返回;(4)若MEMBER(n,TAIL(S-L))为真,则算法的本次调用失败,返回;(5)若n是失败节点,则算法的本次调用失败,返回;(6)扩展节点n,将生成的子节点置于列表SNL,并按评价函数f(k)=h(k)的值从小到大排序(k指示子节点);(7)若SNL为空,则算法的本次调用失败结束,返回;(8)n'=MOVE-FIRST(SNL);(9)将n'加到S-L表首;(10)BACKTRACK(S-L);(11)返回语句(7);(c)到节点(D)和(L)的连接府的其余部分就是解图,解答为(M,M,M,M,M,M,M,M,M,M)。、L、D、I分别指示朗读、识