《人工智能作业题解答》由会员分享,可在线阅读,更多相关《人工智能作业题解答(11页珍藏版)》请在金锄头文库上搜索。
1、人工智能作业题解答人工智能作业题解答第三章 图搜索与问题求解 1、何为状态图和与或图?图搜索与问题求解有什么关系?解:按连接同一节点的各边间的逻辑关系划分,图可以分为状态图和与或图两大类。其中状态图是描述问题的有向图。在状态图中寻找目标或路径的基本方法就是搜索。2、综述图搜索的方式和策略。解:图搜索的方式有:树式搜索,线式搜索。其策略是:盲目搜索,对树式和不回溯的线式是穷举方式,对回溯的线式是随机碰撞式。启发式搜索,利用“启发性信息”引导的搜索。3、什么是问题的解?什么是最优解?解:能够解决问题的方法或具体做法成为这个问题的解。其中最好的解决方法成为最优解。4、什么是与或树?什么是可解节点?什
2、么是解树?解:与或树:一棵树中的弧线表示所连树枝为“与”关系,不带弧线的树枝为或关系。这棵树中既有与关系又有或关系,因此被称为与或树。可解节点:解树实际上是由可解节点形成的一棵子树,这棵子树的根为初始节点,叶为终止节点,且这棵子树一定是与树。解树:满足下列条件的节点为可解节点。 终止节点是可解节点; 一个与节点可解,当且仅当其子节点全都可解;一个或节点可解,只要其子节点至少有一个可解。5、设有三只琴键开关一字排开,初始状态为“关、开、关” ,问连接三次后是否会出现“开、开、开”或“关、关、关”的状态?要求每次必须按下一个开关,而且只能按一个开关。请画出状态空间图。注:琴键开关有这样的特点,若第
3、一次按下时它为“开” ,则第二次按下时它就变成了“关” 。解:设 0 为关,1 为开6、有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸,但受下列条件限制:1)船太小,农夫每次只能带一样东西过河。2)如果没农夫看管,则狼要吃羊,羊要吃菜。请设计一个过桥方案,使得农夫、狼、羊、菜都不受损失地过河。画出相应状态空间图。提示:(1)用四元组(农夫、狼、羊、菜)表示状态,其中每个元素都可为 0 或 1,用 0 表示在左岸,用 1 表示在右岸。(2)把每次过河的一次安排作为一个算符,每次过河都必须有农夫,因为只有他可以划船。解:设 A=(A1,A2,A3,A4)为状态 A1:表示农夫的位置,=0:
4、未过河、=1:已过河A2:表示狼的位置,=0:未过河、=1:已过河A3:表示菜的位置,=0:未过河、=1:已过河 A4:表示羊的位置,=0:未过河、=1:已过河具体的过河方案为:(1)农夫、羊从左岸-右岸,留下羊-一人回到左岸(2)农夫、菜从左岸-右岸,留下菜-农夫、羊回到左岸(3)农夫、狼从左岸-右岸,留下菜、狼-农夫一人回到左岸(4)农夫、羊从左岸-右岸相应的状态空间图为:(0,0,0,0) (1,0,0,1)(0,0,0,1) (1,0,1,1) (0,0,1,0)(1,1,1,0) (0,1,1,0) (1,1,1,1)其中(0,0,0,0)为初始状态, (1,1,1,1)为终止状态。
5、7、请阐述状态空间的一般搜索过程。OPEN 表与 CLOSED 表的作用是什么?解:OPEN 表:用于存放刚生成的节点;CLOSE 表:用于存放将要扩展或已扩展的节点8、广度优先搜索与深度优先搜索各有什么特点?解:(1)广度优先搜索就是始终先在同一级节点中考查,只有当同一级节点考查完之后,才考查下一级节点。或者说,是以初始节点为根节点,向下逐级扩展搜索树。所以,广度优先策略的搜索树是自顶向下一层一层逐渐生成的。(2)深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进,直到不能再前进(到达叶子节点或受到深度限制)时,才从当前节点返回到上一级节点,沿另一方向又继续前进。这种方
6、法的搜索树是从树根开始一枝一枝逐渐形成的。深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝,深度优先搜索如果误入无穷分枝(即深度无限),则不可能找到目标节点。所以,深度优先搜索策略是不完备的。另外,应用此策略得到的解不一定是最佳解(最短路径)。广度优先搜索与深度优先搜索都属于盲目搜索。9、图 3-32 是五大城市间的交通示意图,边上的数字是两城市间的距离。用图搜索技术编写程序,求解以下问题:(1)任找一条西安到北京的旅行路线,并给出其距离。(2)找一条从西安到北京,必须经途上海的路径。(3)找一条从西安到北京,必须经途上海,但不能去昆明的路径。解:domainsp=string
7、 d=integerpp=p* predicatesroad(p,p,d)path(p,p,pp,d)member(p,pp) clausespath(X,Y,L,D):-road(X,Y,D),L=X|Y.path(X,Y,L,D):-road(X,Z,D1),%从当前点向前走到下一点 Znot(member(Z,L),path(Z,Y,Z|L,D2),D=D1+D2.%再找 Z 到出口 Y 的路径member(X,X|_).member(X,_|T)if member(X,T).road(A,B,D):-road(B,A,D). %因为没向图road(“西安”,”北京”,1165). ro
8、ad(“西安”,”上海”,1511).road(“西安”,“广州” ,2129). road(“西安”,”昆明”,1942).road(“昆明”,”北京”,3179). road(“昆明”,”上海”,2677).road(“昆明”,“广州”,2216). road(“北京”,”广州”,2510).road(“上海”,”北京”,1462). road(“广州”,“上海”,1511).(1)path(“西安”,”北京”,L,D),write(L,D).(2)path(“西安”,”北京”,L,D),member(“上海”,L),write(L,D).(3)path(“西安”,”北京”,L,D),me
9、mber(“上海”,L),not(member(“昆明”,L), write(L,D).10、何谓估价函数?在估价函数中,g(x)和 h(x)各起什么作用?解:估价函数的任务是估计待搜索节点的重要程度,给它们排定次序。g(n)是起始点到达 n 的实际路径代价,h(n)就是 n 到达目标点最短路径的启发函数。11、局部择优搜索与全局择优搜索的相同处与区别是什么?解:(1)相同:利用启发函数制导的一种启发式搜索方法。在OPEN 表中保留所有已生成而未考察的节点,并用启发函数 h(x)对它们全部进行估价,从中选出最优节点进行扩展,而不管这个节点出现在搜索树的什么地方。(2)区别:局部择优搜索扩展节点
10、 N 后仅对 N 的子节点按启发函数值大小以升序排序,再将它们依次放入 OPEN 表的首部。12、设有如图 3-24 所示的一棵与或树,请指出解树;并分别按和代价及最大代价求解树代价;然后,指出最优解树。解:按和代价的解树:左树:G(D)=4、G(A)=7、G(S0)=12右树:G(B)=8、G(S0)=15按最大代价的解树: 左树:G(D)=2、G(A)=6、G(S0)=11右树:G(B)=8、G(S0)=15两种方法均说明右树是最优解树。14、传教士和野人问题。有三个传教士和三个野人一起来到河边准备渡河,河边有一条空船,且传教士和野人都会划船,但每次最多可供两人乘渡。河的任何一岸以及船上一
11、旦出现野人人数超过传教士人数,野人就会把传教士吃掉。为安全地渡河,传教士应如何规划渡河方案?试给出该问题的状态图表示,并用 PROLOG 语言编程求解之。若传教士和野人的数目均为五人,渡船至多可乘三人,请定义一个启发函数,并给出相应的搜索树。解:(1)设计该问题的状态。例如:(左岸牧师数,左岸野人数),(右岸牧师数,右岸野人数),船的位置)。 (2)定义目标状态。这里是:(0,0),(3,3),1)(3)描述可能的动作。船上所能够载人的状态就是可能的操作。用谓词 move/2 表示。 (4)判断合法状态(5)深度优先搜索三个传教士和三个野人的示例程序如下:move(1,0).move(0,1)
12、.move(0,2).move(2,0).move(1,1).legal(X,Y,_):-legal1(X),legal1(Y).legal1(X,Y):-X=:=0,Y=0,!.legal1(X,Y):-Y=:=0,X=0,!.legal1(X,Y):-X=Y,X=0,Y=0.update(X,Y,0),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1 is C+E,D1 is D+F,A1 is A-E,B1 is B-F,Statu1=(A1,B1),(C1,D1),1).update(X,Y,1),Move,Statu1):-(A,B)=X,(C,
13、D)=Y,(E,F)=Move,C1 is C-E,D1 is D-F,A1 is A+E,B1 is B+F,Statu1=(A1,B1),(C1,D1),0).connect(Statu,Statu1):-move(X,Y),update(Statu,(X,Y),Statu1),legal(Statu1).findroad(X,X,L,L):-write(L).findroad(X,Y,L,L1):-connect(X,Z),not(member(Z,L),findroad(Z,Y,Z|L,L1).用文字表示:左 右 船上2 个野人去,1 个野人回 3 传,1 野 1 野 1 野2 个野人去,1 个野人回 3 个传 2 野 1 野 2 个传教士去,1 个野人与 1 个传教士回 1 野 1 传 1 传 1 野 1 传,1 野 2 个传教士去,1 个野人回 3 个传 2 野 1 野 2 个野人去,1 个野人回 3 个传 1 野 2 个野人去,完成