图搜索与问题求解

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

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）普通计算机智能低下，不能满足社会需求。

2)研究人工智能也是当前信息化社会的迫切需求。

3）智能化是自动化发展的必然趋势。

4）研究人工智能,对人类自身智能的奥秘也提供有益帮助。

远期目标是要制造智能机器。

具体讲就是使计算机具有看、听、说、写等感知和交互能力，具有联想、学习、推理、理解、学习等高级思维能力，还要有分析问题解决问题和发明创造的能力。

近期目标：是实现机器智能。

即先部分地或某种程度地实现机器智能，从而使现有的计算机更灵活好用和更聪明有用。

人工智能的研究内容1)搜索与求解2）学习与发现3)知识与推理4)发明与创造5)感知与交流6）记忆与联想7）系统与建造8）应用与工程研究途径与方法：1)心理模拟,符号推演法就是以人脑的心理模型为依据，将问题或知识表示成某种逻辑网络，采用符号推演的方法,实现搜索、推理、学习等功能，从宏观上来模拟人脑的思维,实现人工智能.2)生理模拟,神经计算就是用人工神经元组成的人工神经网络来作为信息和知识的载体，用称为神经计算的方法实现学习、记忆、联想、识别和推理等功能，从而来模拟人脑的智能行为,使计算机表现出某种智能。

3）行为模拟,控制进化是一种基于感知－行为模型的研究途径和方法,它是在模拟人在控制过程中的智能活动和行为特性，如自适应，自寻优、自学习、自组织等，来研究和实现人工智能。

4)群体模拟，仿生计算模拟生物群落的群体智能行为，从而实现人工智能.5)博采广鉴，自然计算就是模仿或借鉴自然界的某种机理而设计计算模型，这类计算模型通常是一类具有自适应、自组织、自学习、自寻优能力的算法.6)原理分析，数学建模就是通过对智能本质和原理的分析,直接采用某种数学方法来建立智能行为模型.人工智能的基本技术1）表示a符号智能的表示是知识表示b计算智能的表示一般是对象表示2)运算a符号智能的运算是基于知识表示的推理或符号操作b计算智能的运算是基于对象表示的操作或计算3)搜索a符号智能在问题空间内搜索进行问题求解b计算智能在解空间搜索进行求解第三章1广度优先搜索的特点广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大，广度优先策略是完备的广度优先搜索策略与问题无关，具有通用性.缺点搜索效率低。

图搜索与问题求解实验报告一实验题目图搜索与问题求解二实验目的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）把每次过河的一次安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。

广州大学学生实验报告开课学院及实验室：计算机科学与工程实验室 2020年10月14日(***报告只能为文字和图片,老师评语将添加到此处,学生请勿作答***)一、实验内容1. 分别用广度优先搜索策略、深度优先搜索策略和启发式搜索算法（至少两种）求解八数码问题；分析估价函数对启发式搜索算法的影响；探究讨论各个搜索算法的特点。

二、实验设备1. 实验设备：计算机；2. 平台：Windows操作系统，Visual C++ 6.0 / Python Anaconda三、实验步骤1. 随机生成一个八数码问题分布，设计一个可解的目标状态（要求棋盘9个位置都不同）2. 分别用广度优先搜索策略、深度优先搜索策略和至少两种启发式搜索算法求解八数码问题3. 分析估价函数对启发式搜索算法的影响4. 探究讨论各个搜索算法的特点四、分析说明（包括核心代码及解释）广度优先搜索：首先创建一个结构体node，来记录节点移动方向和扩展的节点。

struct node{int ab[3][3];//节点int direction;//方向};struct node sh[102], end;int count = 1;然后创建一个init函数来初始化棋盘起始状态和目标状态，使用for语句填写棋盘数字用loction函数确定0节点的位置，通过for语句和if语句判断sh[num].ab[i / 3][i % 3] == 0，即可得到0节点的位置Sign函数用来获取棋盘状态，将当前棋盘数字顺序生成一个数，即可得知棋盘状态。

Mobile函数用来移动0节点，先用loction函数获取0节点的位置，再通过if语句来判断0节点位置和所能移动方向，然后进行移动。

Display函数使用for语句来打印当前棋盘。

Search函数使用display函数来打印从初始状态移动到目标状态的中间状态棋盘，在while（1）语句下利用mobile函数移动0节点，直到目标状态找到或者超过寻找次数。