第三章图搜索与问题求解
1、何为状态图和与或图？图搜索与问题求解有什么关系？
解：按连接同一节点的各边间的逻辑关系划分，图可以分为状态图和与或图两大类。其中状态图是描述问题的有向图。在状态图中寻找目标或路径的基本方法就是搜索。
2、综述图搜索的方式和策略。
解：图搜索的方式有：树式搜索，线式搜索。
其策略是：盲目搜索，对树式和不回溯的线式是穷举方式，对回溯的线式是随机碰撞式。
启发式搜索，利用“启发性信息”引导的搜索。
3、什么是问题的解？什么是最优解？
解：能够解决问题的方法或具体做法成为这个问题的解。其中最好的解决方法成为最优解。
4、什么是与或树？什么是可解节点？什么是解树？
解：与或树：一棵树中的弧线表示所连树枝为“与”关系，不带弧线的树枝为或关系。这棵树中既有与关系又有或关系，因此被称为与或树。
可解节点：解树实际上是由可解节点形成的一棵子树，这棵子树的根为初始节点，叶为终止节点，且这棵子树一定是与树。
解树：满足下列条件的节点为可解节点。 ①终止节点是可解节点； ②一个与节点可解，当且仅当其子节点全都可解；③一个或节点可解，只要其子节点至少有一个可解。
5、设有三只琴键开关一字排开，初始状态为“关、开、关”，问连接三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关，而且只能按一个开关。请画出状态空间图。
注：琴键开关有这样的特点，若第一次按下时它为“开”，则第二次按下时它就变成了“关”。
解：设0为关，1为开。
6、有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：
1）船太小，农夫每次只能带一样东西过河。2）如果没农夫看管，则狼要吃羊，羊要吃菜。
请设计一个过桥方案，使得农夫、狼、羊、菜都不受损失地过河。画出相应状态空间图。
提示：（1）用四元组（农夫、狼、羊、菜）表示状态，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。
2）把每次过河的一次安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。
解：设a=（a1，a2，a3，a4）为状态
a1：表示农夫的位置，=0：未过河、=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，0）为初始状态，（1，1，1，1）为终止状态。
7、请阐述状态空间的一般搜索过程。open表与closed表的作用是什么？
解：open表：用于存放刚生成的节点；close表：用于存放将要扩展或已扩展的节点。
8、广度优先搜索与深度优先搜索各有什么特点？
解：（1）广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考查完之后，才考查下一级节点。或者说，是以初始节点为根节点，向下逐级扩展搜索树。
所以，广度优先策略的搜索树是自顶向下一层一层逐渐生成的。
2）深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进，直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。深度优先搜索亦称为纵向搜索。
由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝(即深度无限)，则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解(最短路径)。
广度优先搜索与深度优先搜索都属于盲目搜索。
9、图3-32是五大城市间的交通示意图，边上的数字是两城市间的距离。用图搜索技术编写程序，求解以下问题：
1）任找一条西安到北京的旅行路线，并给出其距离。
2）找一条从西安到北京，必须经途上海的路径。
3）找一条从西安到北京，必须经途上海，但不能去昆明的路径。
解：domains
p=string
d=integer
pp=p*
predicates
road(p,p,d)
path(p,p,pp,d)
member(p,pp)
clauses
path(x,y,l,d):-road(x,y,d),l=[x|[y]].
path(x,y,l,d):-
road(x,z,d1),%从当前点向前走到下一点z
not(member(z,l)),path(z,y,［z|l］,d2),d=d1+d2.%再找z到出口y的路径。
member(x,［xmember(x,［_t］)if member(x,t).
road(a,b,d):-road(b,a,d). 因为没向图road(“西安”,”北京”,1165). road(“西安”,”上海”,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,dmember(“上海”,l),not(member(“昆明”,l)),write(l,d).
10、何谓估价函数？在估价函数中，g(x)和h(x)各起什么作用？
解：估价函数的任务是估计待搜索节点的重要程度，给它们排定次序。
g(n)是起始点到达n的实际路径代价，h(n)就是n到达目标点最短路径的启发函数。
11、局部择优搜索与全局择优搜索的相同处与区别是什么？
解：（1）相同：利用启发函数制导的一种启发式搜索方法。
在open表中保留所有已生成而未考察的节点，并用启发函数h（x）对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。
2）区别：局部择优搜索扩展节点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、传教士和野人问题。有三个传教士和三个野人一起来到河边准备渡河，河边有一条空船，且传教士和野人都会划船，但每次最多可供两人乘渡。河的任何一岸以及船上一旦出现野人人数超过传教士人数，野人就会把传教士吃掉。
为安全地渡河，传教士应如何规划渡河方案？试给出该问题的状态图表示，并用prolog语言编程求解之。
若传教士和野人的数目均为五人，渡船至多可乘三人，请定义一个启发函数，并给出相应的搜索树。
解：1）设计该问题的状态。例如：
((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人数),船的位置)。（2）定义目标状态。这里是：
((0,0),(3,3),1)（3）描述可能的动作。船上所能够载人的状态就是可能的操作。用谓词move/2表示。
（4）判断合法状态（5）深度优先搜索三个传教士和三个野人的示例程序如下：
move(1,0).
move(0,1).
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,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个野人去，完成。
人工智能作业
人工智能 由自然探索于创新课程所想。管理学院李先同 201200272120 人工智能是一个大家看似并不陌生的字眼，我们平时所用的手机，电影中的科幻元素无不充斥着人工智能。由此人工智能变成为了一个人人都知道，却又都不甚了解的事物。通过这学期自然探索与创新课程的学习，我了解到了人工智能的发展简史，更对...
人工智能作业
2014 人工智能 作业 1 提交时间10 21 1 食草动物与食肉动物问题。3只食草动物与3只食肉动物在河一边，并有一条船。船能坐一至两只动物。船不能空载。目标是，把每只动物送到河对岸，并且留在某岸边或者船上的食肉动物数不能多于食草动物数。请将此问题转换成一个搜索问题 a.定义一个状态表示。b.给...
人工智能作业
1.何谓估价函数，在估价函数中，g n 和h n 各起什么作用？解 估价函数的任务是估计待搜索节点的重要程度，给它们排定次序。g n 是起始点到达n的实际路径代价，h n 就是n到目标点最短路径的启发函数。2.设有如下结构的移动将牌游戏 其中，b表示黑色将牌，w表是白色将牌，e表示空格。游戏的规定走...