图搜索与问题求解

问题：指事件或事物的已知或当前状态与目标状态之间的有差异。

问题求解：指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一直。

问题求解所需的知识（求解框架）：叙述性知识、描述客观事物的特点及关系。

过程性知识、通常是解决问题的操作步骤和过程的知识，也称为操作性知识。

控制性知识、求解问题的方法和技巧的知识，确定解决问题的策略。

知识表示:研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。

常用的知识表示形式:状态空间图，与或图，谓词逻辑，产生式，框架，语义网络盲目搜索：无向导的搜索，也称穷举搜素。

在搜索过程中，没有任何背景知识作指导，不考虑任何与解有关的信息，随机地或按预先规定的顺序（如广度优先和深度优先）机械地生成树的节点，并判断是否为解，直到找到解或证明问题无解为止。

特点：搜索效率太低，所以在实际中往往是不可行的。

启发函数：通过函数计算来评价每种选择的价值大小，用以指导搜索过程。

启发式搜索：利用问题本身的“启发性信息”不断地改变或调整搜索的方向，使搜索朝着问题本身最希望的方向进行，加速问题的求解并找到最优解。

特点：重排OPEN表，选择最有希望的节点加以扩展。

启发式搜索—全局择优算法：也叫做最好优先搜索，在启发性知识导航下的广度优先搜索，在OPEN表中保留所有已生成而为考察的节点，对其中的每个节点x计算启发函数h（x）,从全部节点中选出最优节点进行扩展，而不管这个结点出现的搜索树的什么地方。

步1、把初始几点S。

放入OPEN表中，计算h(S。

)；步2、若OPEN表为空，则搜索失败，退出。

步3、否则，移出OPEN表中第一节点N放入CLOSED表中，并冠以序号n;步4、若目标结点S。

=N，则搜索成功，利用CLOSED表中的返回指针找出S。

到N的路径即为所求解，退出。

步5、若N不可扩展，则转步2；步6、否则，扩展N，计算N的每个子节点x的启发函数h(x)，并将N所有子节点x配以指向N的返回指针后放入OPEN表中，依据启发函数值h(x)对节点的计算，对OPEN表中所有节点按其启发函数值的大小以升序排列，转步2.局部择优：是启发性知识导航下的深度优先搜索，在OPEN表中保留所有已生成为为考察的节点，对其中新生成的每个子节点x计算启发函数h(x),从全部子节点中选出最优节点进行扩展，其选择下一个要考察的结点的范围是刚刚生成的全部子节点。

图搜索问题求解实验⼆图搜索问题求解⼀、实验⽬的加深学⽣对图搜索技术的理解，使学⽣掌握图搜索基本编程⽅法，并能利⽤图搜索技术解决⼀些应⽤问题。

1. 掌握Turbo prolog软件编程⽅法；2. 熟悉状态图搜索的基本算法；3．掌握图搜索问题求解中的问题表⽰、节点表⽰、close表和open表的构造。

⼆、实验环境计算机，Turbo PROLOG教学软件三、预习要求1.预习教材第四章有关状态图问题求解的内容，熟悉状态图求解的过程和⽅法；2.了解Turbo PROLOG程序设计的基本知识。

四、实验内容以求交通图中两地之间的路径和最短路径问题为例，分别⽤状态图搜索和代价树搜索，进⾏问题求解。

问题描述如下：G 为⼀有向图, 其每条边都有⼀个⾮负的权数。

对于图中任意两点间的路径, 定义⼀个路径长度, 其值为该路径所包含的各条边的权数之和。

两点间的路径⼀般不⽌⼀条。

对于给定的任意出发点s和到达点t，⾸先找到所有的从s⾄t的路径，然后从中找出长度最短的路径。

左图是某⼀城市的交通⽹络。

边的⽅向表⽰允许的通⾏⽅向。

边旁的权数表⽰该边的长度。

要求找出点 v1 ⾄ v5 的所有路径，并找出最短路径。

五、实验⽅法和步骤1. 启动prolog编辑环境；2. ⽤图搜索搜索思想编辑路径求解问题的源程序；2. 运⾏程序，分析结果；3. ⽤代价树搜索思想编辑最短路径求解问题的源程序；4．运⾏程序，分析结果。

六、⽰例程序以教材例4.1迷宫图的路径搜索为例，给出迷宫问题的求解程序。

DOMAINSstate=symbolDATABASE-mydatabaseopen(state,integer)closed(integer,state,integer)res(state)open1(state,integer)min(state,integer)mark(state)fail_PREDICATESsolveroad(state,state)search(state,state)resultsearchingstep4(integer,state)step56(integer,state)equal(state,state)repeatresulting(integer)rule(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 don't find aroad!"). 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(No,State):-step56(No,State),!,fail.step56(No,StateX):-rule(StateX,StateY),not(open(StateY,_)),not(closed(_,StateY,_)),assertz(open(StateY,No)),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,s4).road(s4,s1).road(s1,s4).road(s1,s2).road(s2,s1).road(s2,s3).road(s3,s2).road(s4,s7).road(s7,s4).road(s4,s5).road(s5,s4).road(s5,s6).road(s6,s5).road(s5,s8).road(s8,s5).road(s8,s9).road(s9,s8).road(s2,s5).road(s5,s2).road(s9,sg).七、实验报告要求1. 实验报告应简单明了，语⾔通顺，结果正确，程序规范。

图搜索与问题求解实验报告一实验题目图搜索与问题求解二实验目的1熟悉和掌握启发式搜索/A*搜索的定义、估价函数和算法过程；2 理解和掌握搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3 比较并分析图搜索策略的实质，通过实验理解启发式搜索/A*搜索的意义。

三实验要求1以九宫问题/八数码问题为例，以某种启发式搜索/A*搜索策略编程演示其搜索过程；2 定义启发式函数,能正确求解出从初始状态到目标状态的移动路线；3 对不可达状态能进行正确识别；4对所采用的启发式函数做出性能分析。

四数据结构typedef struct Qnode{ //队列的节点类型定义long a; //将8数码转化为长整型后入队列int dnum; //与目标状态数码不同的位置的个数Qnode *next;}*QueuePtr;typedef struct{QueuePtr front; //队头指针QueuePtr rear; //队尾指针}LinkQueue; //链式队列五实验算法1 说明有解和无解如何判定；int NiXu(int a[][3]) //求出所给状态的逆序数{i nt i,j,k=0,sum=0;i nt b[8];f or(i=0;i<3;i++)for(j=0;j<3;j++)if(a[i][j]) //空格用0代替，逆序不计空格b[k++]=a[i][j];for(i=1;i<8;i++)for(j=0;j<i;j++)if(b[i]<b[j])sum++;return sum;}if(NiXu(start)%2 != NiXu(end)%2)printf("无法到达！\n");e lse{printf("广度优先搜索如下：\n\n");search();}2 说明启发式函数如何设定；int h(long x){i nt sum=0;i nt b[3][3];u_trans(x,b);f or (int i=0;i<3;i++)for (int j=0;j<3;j++)if (end[i][j]!=b[i][j])sum++;r eturn sum;}3说明实验中采用的搜索算法。

人工智能作业题解答第三章图搜索与问题求解1、何为状态图和与或图？图搜索与问题求解有什么关系？解：按连接同一节点的各边间的逻辑关系划分，图可以分为状态图和与或图两大类。

其中状态图是描述问题的有向图。

在状态图中寻找目标或路径的基本方法就是搜索。

2、综述图搜索的方式和策略。

解：图搜索的方式有：树式搜索，线式搜索。

其策略是：盲目搜索，对树式和不回溯的线式是穷举方式，对回溯的线式是随机碰撞式。

启发式搜索，利用“启发性信息”引导的搜索。

3、什么是问题的解？什么是最优解？解：能够解决问题的方法或具体做法成为这个问题的解。

其中最好的解决方法成为最优解。

4、什么是与或树？什么是可解节点？什么是解树？解：与或树:一棵树中的弧线表示所连树枝为“与”关系,不带弧线的树枝为或关系。

这棵树中既有与关系又有或关系，因此被称为与或树。

可解节点:解树实际上是由可解节点形成的一棵子树,这棵子树的根为初始节点，叶为终止节点，且这棵子树一定是与树。

解树:满足下列条件的节点为可解节点。

①终止节点是可解节点；②一个与节点可解，当且仅当其子节点全都可解；③一个或节点可解，只要其子节点至少有一个可解。

5、设有三只琴键开关一字排开，初始状态为“关、开、关”，问连接三次后是否会出现“开、开、开”或“关、关、关”的状态？要求每次必须按下一个开关，而且只能按一个开关。

请画出状态空间图。

注：琴键开关有这样的特点，若第一次按下时它为“开”，则第二次按下时它就变成了“关”。

解：设0为关，1为开6、有一农夫带一只狼、一只羊和一筐菜欲从河的左岸乘船到右岸，但受下列条件限制：1）船太小，农夫每次只能带一样东西过河。

2）如果没农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过桥方案，使得农夫、狼、羊、菜都不受损失地过河。

画出相应状态空间图。

提示：（1）用四元组（农夫、狼、羊、菜）表示状态，其中每个元素都可为0或1，用0表示在左岸，用1表示在右岸。

（2）把每次过河的一次安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。