文档视界 最新最全的文档下载
当前位置:文档视界 › 人工智能导论:状态空间搜索实验—八数码问题求解

人工智能导论:状态空间搜索实验—八数码问题求解

人工智能导论:状态空间搜索实验—八数码问题求解
人工智能导论:状态空间搜索实验—八数码问题求解

昆明理工大学信息工程与自动化学院学生实验报告

( 2014—— 2015 学年 第 一 学期 )

课程名称:人工智能导论 开课实验室: 年 月 日

一、实验内容和要求

八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

例如:

(a) 初始状态 (b) 目标状态图1 八数码问题示意图

请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A * 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN 表和CLOSED 表,给出解路径,对实验结果进行分析总结,得出结论。

实验报告内容格式要求:XXXXXXXXXXXX (中文:宋体,小四;英文:Times New Roman )。

二、实验目的

1. 熟悉人工智能系统中的问题求解过程;

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用;

3. 熟悉对八数码问题的建模、求解及编程语言的应用。

三、实验算法

启发函数设定

由八数码问题的部分状态图可以看出,从初始节点开始,在通向目标节点的路径上,各节点的数码格局同目标节点相比较,其数码不同的位置个数在逐渐减少,最后为零,因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息,利用这个信息来扩展节点的选择,减少搜索范围,提高搜索速度。

2、数据结构与算法设计

数码结构体

typedef struct node //八数码结构体

{

int form[N][N]; //数码组

int evalue; //评估值,差距

int udirec; //所屏蔽方向,防止往回推到上一状态,1上2下3左4右

struct node *parent; //父节点

}Graph;

Graph *Qu[MAX];//队列

Graph *St[MAX];//堆栈

搜索过程:(搜索采用广度搜索方式,利用待处理队列辅助,逐层搜索(跳过劣质节点))

a、把初始数码组压入队列;

b、从队列中取出一个数码组节点;

c、扩展子节点,即从上下左右四个方向移动空格,生成相应子节点:

d、对子节点数码组作评估,是否为优越节点,即其评估值是否小于等于其父节点加一,是则将其压入队,否则抛弃。

e、判断压入队的子节点数码组(优越点)的评估值,为零则表示搜索完成,退出搜索;

f、跳到步骤2;

四、程序框图

五、实验结果及分析

采用深度优先搜索方式并简化搜索

六、结论

Open表close表

1 2 0

2 3 4 0 1

2 4 5 6 0 1

3 目标完成

七、源程序及注释

#include } //设计了搜索深度范围,防止队列内存越界

#include 6、运行结果

#include

#define N 3 //数码组大小

#define Max_Step 50 //最大搜索深度

#define MAX 50

typedef struct node//八数码结构体

{

int form[N][N];//数码组

int evalue;//评估值

int udirect;//所屏蔽方向,防止往回推到上已状态,1上2下3左4右struct node *parent;//父节点

/////////打印数码组

void Print(Graph *The_graph)

{

int i,j;

if(The_graph==NULL)

printf("图为空\n");

else

{

printf("---------------------\n");

for(i=0;i

{

printf("|\t");

for(j=0;j

{

printf("%d\t",The_graph->form[i][j]);//遍历打印

}

printf("\t|\n");

}

printf("|\t\t\t差距:%d\t|\n",The_graph->evalue);//差距显示

printf("---------------------\n");

}

}

/////////评价函数

int Evaluate(Graph *The_graph,Graph *End_graph)

{

int valute=0;//差距数

int i,j;

for(i=0;i

{

for(j=0;j

{

if(The_graph->form[i][j]!=End_graph->form[i][j]) {

valute++;

}

}

}

The_graph->evalue=valute;

return valute;

}

/////////移动数码组

Graph *Move(Graph *The_graph,int Direct,int CreatNew_graph) {

Graph *New_graph;//

int HasGetBlank=0;//是否获取空格位置

int AbleMove=1;//是否可移动

int i,j,t_i,t_j,x,y;

for(i=0;i

{

for(j=0;j

{

if(The_graph->form[i][j]==0)

{

HasGetBlank=1;

break;

}

}

if(HasGetBlank==1)

break;

}

//printf("空格位置:%d,%d\n",i,j);

t_i=i;

t_j=j;

//移动空格

switch(Direct)

{

case 1://上

t_i--;

if(t_i<0)

AbleMove=0;

break;

case 2://下

t_i++;

if(t_i>=N)

AbleMove=0;

break;

case 3://左

t_j--;

if(t_j<0)

AbleMove=0;

break;

case 4://右

t_j++;

if(t_j>=N)

AbleMove=0;

break;

}

if(AbleMove==0)//不能移动则返回原节点

{

return The_graph;

}

if(CreatNew_graph==1)

{

New_graph=(Graph *)malloc(sizeof(Graph));//生成节点for(x=0;x

{

for(y=0;y

{

New_graph->form[x][y]=The_graph->form[x][y];//复制数码组

}

}

}

else

{

New_graph=The_graph;

}

//移动后

New_graph->form[i][j]=New_graph->form[t_i][t_j];

New_graph->form[t_i][t_j]=0;

//printf("移动产生的新图:\n");

//Print(New_graph);

return New_graph;

}

/////////搜索函数

Graph *Search(Graph *Begin,Graph *End)

{

Graph *g1,*g2,*g;

int Step=0;//深度

int Direct=0;//方向

int i;

int front,rear;

front=rear=-1;//队列初始化

g=NULL;

rear++;//入队

Qu[rear]=Begin;

while(rear!=front)//队列不空

{

front++;//出队

g1=Qu[front];

//printf("开始第%d个图:\n",front);

//Print(g1);

for(i=1;i<=4;i++)//分别从四个方向推导出新子节点

{

Direct=i;

if(Direct==g1->udirect)//跳过屏蔽方向

continue;

g2=Move(g1, Direct, 1);//移动数码组

if(g2!=g1)//数码组是否可以移动

{

//可以移动

Evaluate(g2, End);//评价新的节点

//printf("开始产生的第%d个图:\n",i);

//Print(g2);

if(g2->evalue<=g1->evalue+1)

{

//是优越节点

g2->parent=g1;

//移动空格

switch(Direct)//设置屏蔽方向,防止往回推 {

case 1://上

g2->udirect=2;

break;

case 2://下

g2->udirect=1;

break;

case 3://左

g2->udirect=4;

break;

case 4://右

g2->udirect=3;

break;

}

rear++;

Qu[rear]=g2;//存储节点到待处理队列

if(g2->evalue==0)//为0则搜索完成

{

g=g2;

//i=5;

break;

}

}

else

{

free(g2);//抛弃劣质节点

g2=NULL;

}

}

}

if(g!=NULL)//为0则搜索完成

{

if(g->evalue==0)

{

break;

}

}

Step++;//统计深度

if(Step>Max_Step)

{

break;

}

}

return g;

}

/////////初始化一个八数码结构体

Graph *CR_BeginGraph(Graph *The_graph)

{

srand((unsigned)time(0));

int M=10;//随机移动步数

int Direct;

int i,x,y;

Graph *New_graph;

New_graph=(Graph *)malloc(sizeof(Graph));

for(x=0;x

{

for(y=0;y

{

New_graph->form[x][y]=The_graph->form[x][y]; }

}

for(i=0;i

{

Direct=rand()%4+1;//产生1-4随机数

//printf("Direct:%d\n",Direct);

New_graph=Move(New_graph, Direct, 0);

//Print(New_graph);

}

New_graph->evalue=0;

New_graph->udirect=0;

New_graph->parent=NULL;

return New_graph;

}

int main (int argc, const char * argv[])

{

// insert code here...

/*

Graph Begin_graph={

{{2,8,3},{1,6,4},{0,7,5}},0,0,NULL

};

Graph Begin_graph={

{{2,8,3},{1,0,4},{7,6,5}},0,0,NULL

};

Graph Begin_graph={

{{2,0,1},{4,6,5},{3,7,8}},0,0,NULL

};

*/

//目标数码组

Graph End_graph={

{{1,2,3},{8,0,4},{7,6,5}},0,0,NULL

};

//初始数码组

Graph *Begin_graph;

Begin_graph=CR_BeginGraph(&End_graph);//随机产生初始数码组 Evaluate(Begin_graph, &End_graph);//对初始的数码组评价

printf("初始数码组:\n");

Print(Begin_graph);

printf("目标数码组:\n");

Print(&End_graph);

Graph *G,*P;

int top=-1;

//图搜索

G=Search(Begin_graph, &End_graph);

//打印

if(G)

{

//把路径倒序

P=G;

//压栈

while(P!=NULL)

{

top++;

St[top]=P;

P=P->parent;

}

printf("<<<<<<<<<<<<<<<搜索结果>>>>>>>>>>>>>>>>\n"); //弹栈打印

while(top>-1)

{

P=St[top];

top--;

Print(P);

}

printf("<<<<<<<<<<<<<<<<<完成>>>>>>>>>>>>>>>>>>\n"); }

else

{

printf("搜索不到结果,深度为%d\n",Max_Step);

//设计搜索深度范围主要是防止队列内存越界

}

return 0;

}

八数码问题求解--实验报告讲解

实验报告 一、实验问题 八数码问题求解 二、实验软件 VC6.0 编程语言或其它编程语言 三、实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 四、实验数据及步骤 (一、)实验内容 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始状态(b) 目标状态 图1 八数码问题示意图 (二、)基本数据结构分析和实现 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{

int digit[ROW][COL]; int dist; // distance between one state and the destination一 个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成: (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down, index);//向下扩展的节点 int dist_down = MAXDISTANCE; (3)将当前状态的空格左移 Node node_left; Assign(node_left, index);//向左扩展的节点 int dist_left = MAXDISTANCE; (4)将当前状态的空格右移 Node node_right; Assign(node_right, index);//向右扩展的节点 int dist_right = MAXDISTANCE; 通过定义结点状态和发生器函数,就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。 3.图的搜索策略 经过分析,8数码问题中可采用的搜速策略共有:1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索,一共五种。其中,广度优先搜索法是可采纳的,有界深度优先搜索法是不完备的,最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。 (三、)广度(宽度)优先搜索原理 1. 状态空间盲目搜索——宽度优先搜索 其基本思想是,从初始节点开始,向下逐层对节点进形依次扩展,并考察它是否为目标节点,再对下层节点进行扩展(或搜索)之前,必须完成对当层的所有节点的扩展。再搜索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面,后进入的节点排在后面。其搜索过程如图(1)所示。

用A算法解决八数码问题演示教学

用A算法解决八数码 问题

用A*算法解决八数码问题 一、 题目:八数码问题也称为九宫问题。在3×3的棋盘,有八个棋子,每个 棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态:状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态:任何状态都可以被指定为初始状态。 操作符:用来产生4个行动(上下左右移动)。 目标测试:用来检测状态是否能匹配上图的目标布局。 路径费用函数:每一步的费用为1,因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态,要求找到一种搜索策略,用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。对 于几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价 值,即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--; 这样估价函数f 在g 值一定的情况下,会或多或少的受估价值h 的制 约,节点距目标点近,h 值小,f 值相对就小,能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。

A star算法在静态路网中的应用 2.算法伪代码 创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算起点的估价值,将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 )

八数码问题人工智能实验报告

基于人工智能的状态空间搜索策略研究 ——八数码问题求解 (一)实验软件 TC2.0 或VC6.0编程语言或其它编程语言 (二)实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 (三)需要的预备知识 1. 熟悉TC 2.0或VC6.0 编程语言或者其它编程语言; 2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法; 3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用; 4. 熟悉计算机常用人机接口设计。 (四)实验数据及步骤 1. 实验内容 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 图1 八数码问题示意图 请任选一种盲目搜索算法(深度优先搜索或宽度优先搜索)或任选一种启发式搜索方法(A 算法或A* 算法)编程求解八数码问题(初始状态任选),并对实验结果进行分析,得出合理的结论。 2. 实验步骤 (1)分析算法基本原理和基本流程; 程序采用宽度优先搜索算法,基本流程如下:

(2)确定对问题描述的基本数据结构,如Open表和Closed表等;

(3)编写算符运算、目标比较等函数; (4)编写输入、输出接口; (5)全部模块联调; (6)撰写实验报告。 (五)实验报告要求 所撰写的实验报告必须包含以下内容: 1. 算法基本原理和流程框图; 2. 基本数据结构分析和实现; 3. 编写程序的各个子模块,按模块编写文档,含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等; 4. 程序运行结果,含使用的搜索算法及搜索路径等; 5. 实验结果分析; 6. 结论; 7. 提供全部源程序及软件的可执行程序。 附:实验报告格式 一、实验问题 二、实验目的 三、实验原理 四、程序框图 五、实验结果及分析 六、结论

A星算法求八数码问题试验报告

人工智能实验报告实验名称:八数码问题 姓名:xx 学号:2012210xx xx计算机学院

2014年1月14日 一.实验目的. 的思想,启发式搜索,来求解在代价最小的情况下将九宫格从一掌握A* 个状态转为另状态的路径。 二.实验内容且要求在有限步的操作内,使其转化为目标状态,给定九宫 格的初始状态,并打印出求解路径。例如(即移动的步数最少)所得到的解是代 价最小解 3 8 2 4 6 1 5 0 7 3 2 8 4 6 1 5 0 7 A*三、算法思想:1、思想:估价值与实际A*算法是一种静态路网中求 解最短路最有效的直接搜索方法。值越接近,估价函数取得就越好、原理:2 f(n)=g(n)+h(n), 估价函数公式表示为:是在状态空g(n) 是从初始点经由节点n到目标点的估价函数,其中 f(n) 到目标节点最佳路径的估计nh(n) 是从间中从初始节点到n节点的实际代价,h(n)的选取:代价。保证找到最短路径(最优解的)条件,关键在于估价函数到目标节点的距离实际值,这种情况下,搜索的点数多,搜索估价值h(n)<= n等于h(n)范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计如

果估那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。最短距离, ,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。价值>实际值 四、算法流程:

1、使用了CreateChild()函数,求得了任意未拓展九宫格的扩展结点,便于拓展子空间,搜索所有情况。 关键代码: bool CreateChild(NOExtend ns[],NOExtend ne){

八数码问题C语言A星算法详细实验报告含代码

一、实验内容和要求 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如: [ (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN 表和CLOSED表,给出解路径,对实验结果进行分析总结,得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; % 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中,一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为: f'(n) = g'(n) + h'(n) 这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价),h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的,所以实际上使用的是下面的估价函数: f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价,h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已

知的。用f(n)作为f'(n)的近似,也就是用g(n)代替g'(n),h(n)代替h'(n)。这样必须满足两个条件:(1)g(n)>=g'(n)(大多数情况下都是满足的,可以不用考虑),且f必须保持单调递增。(2)h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同,但是在扩展出一个结点后,要计算它的估价函数,并根据估价函数对待扩展的结点排序,从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下: & 1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。 2)取出队列头(队列头指针所指)的结点,如果该结点是目标结点,则输出路径,程序结束。否则对结点进行扩展。 3)检查扩展出的新结点是否与队列中的结点重复,若与不能再扩展的结点重复(位于队列头指针之前),则将它抛弃;若新结点与待扩展的结点重复(位于队列头指针之后),则比较两个结点的估价函数中g的大小,保留较小g值的结点。跳至第五步。 4)如果扩展出的新结点与队列中的结点不重复,则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置,使它们按从小到大的顺序排列,最后更新队列尾指针。 5)如果队列头的结点还可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步。 四、程序框图

C语言实现8数码问题

1、实验目的 (1)熟悉人工智能系统中的问题求解过程; (2)熟悉状态空间中的盲目搜索策略; (3)掌握盲目搜索算法,重点是宽度优先搜索和深度优先搜索算法。 2、实验要求 用VC语言编程,采用宽度优先搜索和深度优先搜索方法,求解8数码问题3、实验内容 (1)采用宽度优先算法,运行程序,要求输入初始状态 假设给定如下初始状态S0 2 8 3 1 6 4 7 0 5 和目标状态Sg 2 1 6 4 0 8 7 5 3 验证程序的输出结果,写出心得体会。 (2)对代码进行修改(选作),实现深度优先搜索求解该问题

提示:每次选扩展节点时,从数组的最后一个生成的节点开始找,找一个没有被扩展的节点。这样也需要对节点添加一个是否被扩展过的标志。 4 源代码及实验结果截图 #include #include #include //八数码状态对应的节点结构体 struct Node{ int s[3][3];//保存八数码状态,0代表空格 int f,g;//启发函数中的f和g值 struct Node * next; struct Node *previous;//保存其父节点 }; int open_N=0; //记录Open列表中节点数目 //八数码初始状态 int inital_s[3][3]={ 2,8,3,1,6,4,7,0,5 }; //八数码目标状态 int final_s[3][3]={ 2,1,6,4,0,8,7,5,3 };

//------------------------------------------------------------------------ //添加节点函数入口,方法:通过插入排序向指定表添加 //------------------------------------------------------------------------ void Add_Node( struct Node *head, struct Node *p) { struct Node *q; if(head->next)//考虑链表为空 { q = head->next; if(p->f < head->next->f){//考虑插入的节点值比链表的第一个节点值小 p->next = head->next; head->next = p; } else { while(q->next)//考虑插入节点x,形如a<= x <=b { if((q->f < p->f ||q->f == p->f) && (q->next->f > p->f || q->next->f == p->f)){ p->next = q->next; q->next = p; break; } q = q->next; } if(q->next == NULL) //考虑插入的节点值比链表最后一个元素的值更大 q->next = p; }

人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习

第五章状态空间搜索策略 搜索是人工智能的一个基本问题,是推理不可分割的一部分。搜索是求解问题的一种方法,是根据问题的实际情况,按照一定的策略或规则,从知识库中寻找可利用的知识,从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义:一层含义是要找到从初始事实到问题最终答案的一条推理路线;另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。搜索可分为盲目搜索和启发式搜索两种。 1.1 盲目搜索策略 1.状态空间图的搜索策略 为了利用搜索的方法求解问题,首先必须将被求解的问题用某种形式表示出来。一般情况下,不同的知识表示对应着不同的求解方法。状态空间表示法是一种用 “状态”和“算符”表示问题的方法。状态空间可由一个三元组表示(S 0,F,S g )。 利用搜索方法求解问题的基本思想是:首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态,选择一适当的算符作用于当前状态,生成一组后继状态(或称后继节点),然后检查这组后继状态中有没有目标状态。如果有,则说明搜索成功,从初始状态到目标状态的一系列算符即是问题的解;若没有,则按照某种控制策略从已生成的状态中再选一个状态作为当前状态,重复上述过程,直到目标状态出现或不再有可供操作的状态及算符时为止。 算法5.1 状态空间图的一般搜索算法 ①建立一个只含有初始节点S 0的搜索图G,把S 放入OPEN表中。 ②建立CLOSED表,且置为空表。 ③判断OPEN表是否为空表,若为空,则问题无解,退出。 ④选择OPEN表中的第一个节点,把它从OPEN表移出,并放入CLOSED表中,将此节点记为节点n。

⑤考察节点n是否为目标节点,若是,则问题有解,并成功退出。问题的解即可从图G中沿着指针从n到S 的这条路径得到。 ⑥扩展节点n生成一组不是n的祖先的后继节点,并将它们记作集合M,将M中的这些节点作为n的后继节点加入图G中。 ⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点,设置一个指向父节点(即节点n)的指针,并把这些节点加入OPEN表中;对于已在G中出现过的M中的那些节点,确定是否需要修改指向父节点(n节点)的指针;对于那些先前已在G中出现并且已在COLSED表中的M中的节点,确定是否需要修改通向它们后继节点的指针。 ⑧按某一任意方式或按某种策略重排OPEN表中节点的顺序。 ⑨转第③步。 2.宽度优先搜索策略 宽度优先搜索是一种盲目搜索策略。其基本思想是,从初始节点开始,逐层对节点进行依次扩展,并考察它是否为目标节点,在对下层节点进行扩展(或搜索)之前,必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面,后进入的节点排在后面(即将扩展得到的后继节点放于OPEN表的末端)。 宽度优先搜索的盲目性较大,搜索效率低,这是它的缺点。但宽度优先搜索策略是完备的,即只要问题有解,用宽度优先搜索总可以找到它的解。 3.深度优先搜索 深度优先搜索也是一种盲目搜索策略,其基本思想是:首先扩展最新产生的(即 开始,在其后继节点中选择一个节点,对其进行最深的)节点,即从初始节点S 考察,若它不是目标节点,则对该节点进行扩展,并再从它的后继节点中选择一个节点进行考察。依此类推,一直搜索下去,当到达某个既非目标节点又无法继续扩展的节点时,才选择其兄弟节点进行考察。

八数码问题C语言A星算法详细实验报告含代码

八数码问题C语言A星算法详细实验报告含代 码 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】

一、实验内容和要求 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如: (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法(广度优先搜索或深度优先搜索)或任选一种启发式搜索方法(全局择优搜索,加权状态图搜索,A 算法或 A* 算法)编程求解八数码问题(初始状态任选)。选择一个初始状态,画出搜索树,填写相应的OPEN表和CLOSED表,给出解路径,对实验结果进行分析总结,得出结论。 二、实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法 A*算法是一种常用的启发式搜索算法。 在A*算法中,一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为: f'(n) = g'(n) + h'(n)

这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价),h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的,所以实际上使用的是下面的估价函数: f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价,h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。用f(n)作为f'(n)的近似,也就是用g(n)代替 g'(n),h(n)代替h'(n)。这样必须满足两个条件:(1)g(n)>=g'(n)(大多数情况下都是满足的,可以不用考虑),且f必须保持单调递增。(2)h必须小于等于实际的从当前节点到达目标节点的最小耗费 h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同,但是在扩展出一个结点后,要计算它的估价函数,并根据估价函数对待扩展的结点排序,从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下: 1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。

启发式搜索算法解决八数码问题(C语言)

1、程序源代码 #include #include struct node{ int a[3][3];//用二维数组存放8数码 int hx;//函数h(x)的值,表示与目标状态的差距 struct node *parent;//指向父结点的指针 struct node *next;//指向链表中下一个结点的指针 }; //------------------hx函数-------------------// int hx(int s[3][3]) {//函数说明:计算s与目标状态的差距值 int i,j; int hx=0; int sg[3][3]={1,2,3,8,0,4,7,6,5}; for(i=0;i<3;i++) for(j=0;j<3;j++) if(s[i][j]!=sg[i][j]) hx++; return hx; } //-------------hx函数end----------------------// //-------------extend扩展函数----------------// struct node *extend(node *ex) { //函数说明:扩展ex指向的结点,并将扩展所得结点组成一条//单链表,head指向该链表首结点,并且作为返回值 int i,j,m,n; //循环变量 int t; //临时替换变量 int flag=0; int x[3][3];//临时存放二维数组 struct node *p,*q,*head; head=(node *)malloc(sizeof(node));//head p=head; q=head; head->next=NULL;//初始化 for(i=0;i<3;i++)//找到二维数组中0的位置 { for(j=0;j<3;j++)

第三章 知识的状态空间表示法

第三章知识的状态空间表示法 1 课前思考: 人类的思维过程,可以看作是一个搜索的过程。 某个方案所用的步骤是否最少?也就是说它是最优的吗?如果不是,如何才能找到最优的方案?在计算机上又如何实现这样的搜索?这些问题实际上就是本章我们要介绍的搜索问题。 2 学习目标: 掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法,对典型问题,掌握启发式函数的定义方法。 3 学习指南: 了解算法的每一个过程和细节问题,掌握一些重要的定理和结论,在有条件的情况下,程序实现每一个算法,求解一些典型的问题。 4 难重点: 回溯搜索算法、算法及其性质、改进的A*算法。 5 知识点: 本章所要的讨论的问题如下: 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗? 什么情况下可以找到最佳解? 求解的效率如何。 3.1 状态空间表示知识 一、状态空间表示知识要点 1.状态 状态(State)用于描述叙述性知识的一组变量或数组,也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成: Q={q1,q2,……,qn} 当给每一个分量以确定的值时,就得到一个具体的状态,每一个状态都是一个结点(节点)。

实际上任何一种类型的数据结构都可以用来描述状态,只要它有利于问题求解,就可以选用。 2.操作(规则或算符) 操作(Operator)是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时,它将引起该状态中某一些分量发生变化,从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数,它描述了状态之间的关系。通常可表示为: F={ f1 , f2,……… fm} 3.状态空间 状态空间(State Space)是由问题的全部及一切可用算符(操作)所构成的集合称为问题的状态空间。用三元组表示为: ({Qs},{F},{Qg}) Qs:初始状态,Qg:目标状态,F:操作(或规则)。 4.状态空间(转换)图 状态空间也可以用一个赋值的有向图来表示,该有向图称为状态空间图,在状态空间图中包含了操作和状态之间的转换关系,节点表示问题的状态,有向边表示操作。 二、状态图搜索 1.搜索方式 用计算机来实现状态图的搜索,有两种最基本的方式:树式搜索和线式搜索。 2.搜索策略 大体可分为盲目搜索和启发式(heuristic)搜索两大类。 搜索空间示意图 例3.1 钱币翻转问题 设有三枚硬币,其初始状态为(反,正,反),允许每次翻转一个硬币(只翻一个硬币,必须翻一个硬币)。必须连翻三次。问是否可以达到目标状态(正,正,正)或(反,反,反)。问题求解过程如下: 用数组表示的话,显然每一硬币需占一维空间,则用三维数组状态变量表示这个知识: Q=(q1 , q2 , q3) 取q=0 表示钱币的正面q=1 表示钱币的反面 构成的问题状态空间显然为: Q0=(0,0,0),Q1=(0,0,1),Q2=(0,1,0),Q3=(0,1,1)

A星算法求八数码问题实验报告

人工智能实验报告 实验名称:八数码问题 姓名:xx 学号:2012210xx xx计算机学院 2014年1月14日

一.实验目的 掌握A*的思想,启发式搜索,来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。 二.实验内容 给定九宫格的初始状态,要求在有限步的操作内,使其转化为目标状态,且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 7 0 5 三、A*算法思想: 1、思想: A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近,估价函数取得就越好 2、原理: 估价函数公式表示为: f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由节点n到目标点的估价函数,g(n) 是在状态空间中从初始节点到n节点的实际代价,h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解的)条件,关键在于估价函数h(n)的选取:估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离,那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。

四、算法流程: 是 是,输出路径 否,生成n 的所有子状态 Heuristic_Search(启发式搜索) While (未拓展表不为空?) 从未拓展表中删除第一个状态n N 为目标状态? Case:此子状态 不在拓展表和 未拓展表中 Case:此子状态在未拓展表中 Case:此子状态在拓展表 计算该子状态的估价函数值; 记录比已有的路径更短 的路径 记录比已有的路径更短的路径 返回

用盲目搜索技术解决八数码问题

. 用盲目搜索技术解决八数码问题 题目 在3×3的棋盘,有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上 标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 算法流程 使用宽度优先搜索 从初始节点开始,向下逐层对节点进形依次扩展,并考察它是否为目标节点,再对下层节点进行扩展(或搜索)之前,必须完成对当层的所有节点的扩展。再搜 索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面, 后进入的节点排在后面。 宽度优先算法如下: 把初始结点S0放入OPEN表中 若OPEN表为空,则搜索失败,问题无解 取OPEN表中最前面的结点N放在CLOSE表中,并冠以顺序编号n 若目标结点,则搜索成功,问题有解N?Sg若N无子结点,则转2 扩展结点N,将其所有子结点配上指向N的放回指针,依次放入OPEN表的尾部,转2 源程序 #include 文档Word . #include #include

using namespace std; const int ROW = 3;//行数 const int COL = 3;//列数 const int MAXDISTANCE = 10000;//最多可以有的表的数目const int MAXNUM = 10000; typedef struct _Node{ int digit[ROW][COL]; int dist;//distance between one state and the destination 一个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置} Node; Node src, dest;// 父节表目的表 vector node_v; // store the nodes存储节点 文档Word . bool isEmptyOfOPEN() //open表是否为空

八数码问题实验报告讲解

《八数码问题》实验报告 一、实验目的: 熟练掌握启发式搜索A *算法。 二、实验内容: 使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A *算法,采用估价函数 ()()()()w n f n d n p n ??=+??? , 其中:()d n 是搜索树中结点n 的深度;()w n 为结点n 的数据库中错放的棋子个数;()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 三、实验原理: 1. 问题描述: 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。 要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述: 启发式搜索 (1)原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 (2)估价函数

计算一个节点的估价函数,可以分成两个部分: 1、 已经付出的代价(起始节点到当前节点); 2、 将要付出的代价(当前节点到目标节点)。 节点n 的估价函数)(n f 定义为从初始节点、经过n 、到达目标节点的路径的最小代价 的估计值,即)(* n f = )(* n g + )(* n h 。 )(*n g 是从初始节点到达当前节点n 的实际代价; )(*n h 是从节点n 到目标节点的最佳路径的估计代价。 )(*n g 所占的比重越大,越趋向于宽度优先或等代价搜索;反之,)(*n h 的比重越大, 表示启发性能就越强。 (3)算法描述: ① 把起始节点S 放到OPEN 表中,并计算节点S 的)(S f ; ② 如果OPEN 是空表,则失败退出,无解; ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同,当其中有一个 为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点i ; ④ 把节点i 从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中; ⑤ 如果i 是个目标节点,则成功退出,求得一个解; ⑥ 扩展节点i ,生成其全部后继节点。对于i 的每一个后继节点j : 计算)(j f ;如果j 既不在OPEN 表中,又不在CLOCED 表中,则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针,以便一旦找到目标节点时记住一个解答路径;如果j 已在OPEN 表或CLOSED 表中,则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小,则 (I)以此新值取代旧值。 (II)从j 指向i ,而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中,则把它移回OPEN 表中。 ⑦ 转向②,即GOTO ②。 (3)算法流程图:

启发式搜索 八数码问题

启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。 要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ,A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? , 其中:()d n 是搜索树中结点n 的深度;()w n 为结点n 的数据库中错放的棋子个数;()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度,深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中,并计算节点S 的)(S f ; ② 如果OPEN 是空表,则失败退出,无解; ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同,当其中有一个 为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点i ; ④ 把节点i 从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中; ⑤ 如果i 是个目标节点,则成功退出,求得一个解; ⑥ 扩展节点i ,生成其全部后继节点。对于i 的每一个后继节点j : 计算)(j f ;如果j 既不在OPEN 表中,又不在CLOCED 表中,则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针,以便一旦找到目标节点时记住一个解答路径;如果j 已在OPEN 表或CLOSED 表中,则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小,则 (I)以此新值取代旧值。 (II)从j 指向i ,而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中,则把它移回OPEN 表中。 ⑦ 转向②,即GOTO ②。

八数码问题报告

八数码问题分析 班级:计算机1041 学号:01 姓名:李守先 2013年9月26日

摘要 八数码问题(Eight-puzzle Problem )是人工智能中一个很典型的智力问题。 本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java 算法与实现的思想, 分析了A*算法的可采纳性等及系统的特点。 关键词 九宫重排, 状态空间, 启发式搜索, A*算法 1 引言 九宫重排问题(即八数码问题)是人工智能当中有名的难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。状态转换的规则:空格周围的数移向空格,我们可以看作是空格移动,它最多可以有4个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。 图1 许多学者对该问题进行了有益的探索[1,2,4,6]。给定初始状态,9个数在3×3中的放法共有9!=362880种,其状态空间是相当大的。因此, 有必要考虑与问题相关的启发性信息来指导搜索,以提高搜索的效率。当然,还有个很重要的问题:每个初始状态都存在解路径吗?文献给出了九宫重排问题是否有解的判别方法:九宫重排问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解;否则问题无解。状态的逆序数是定义把三行数展开排成一行,并且丢弃数字 0 不计入其中,ηi 是第 i 个数之前比该数小的数字的个数,则 η=Σηi 是该状态的逆序数,图2说明了逆序数计算的过程 。 本文介绍用JAVA 编写九宫重排问题游戏。游戏规则是,可随机产生或由用户设置初始状态,由初始状态出发,不断地在空格上下左右的数码移至空格,若能排出目标状态,则成功。为了避免对无解节点进行无用搜索,首先对初始节点进行逆序数分析,对有解的节点进行搜索,从而节省了资源,也提高了效率。本文内容安排: 第2部分介绍几个相关的概念和A*算法以及可采纳性 ;

采用A算法解决八数码问题

人工智能实验一报告题目:采用A*算法解决八数码问题 姓名: XXX 学号: 10S003028 专业:计算机科学与技术 提交日期: 2011-05-04

目录 1问题描述........................................................................................................................... - 2 - 1.1待解决问题的解释............................................................................................... - 2 - 1.2问题的搜索形式描述............................................................................................ - 2 - 1.3解决方案介绍(原理)........................................................................................ - 3 - 2算法介绍........................................................................................................................... - 4 - 2.1A*搜索算法一般介绍............................................................................................ - 4 - 2.2 算法伪代码........................................................................................................... - 4 - 3算法实现........................................................................................................................... - 5 - 3.1 实验环境与问题规模........................................................................................... - 5 - 3.2 数据结构............................................................................................................... - 5 - 3.3 实验结果............................................................................................................... - 6 - 3.4系统中间及最终输出结果.................................................................................... - 6 - 4参考文献........................................................................................................................... - 7 - 5附录—源代码及其注释................................................................................................... - 7 -

八数码实验报告

利用人工智能技术解决八数码游戏问题 1.八数码游戏问题简介 九宫排字问题(又称八数码问题)是人工智能当中有名的难题之一。问题是在 3×3方格盘上,放有八个数码,剩下第九个为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始位置转化为目标位置。 2.八数码游戏问题的状态空间法表示 ①建立一个只含有初始节点s0的搜索图g,把s0放入open表中 ②建立closed表,且置为空表 ③判断open表是否为空表,若为空,则问题无解,退出 ④选择open表中的第一个节点,把它从open表移出,并放入closed表中,将此节点记为节点n ⑤考察节点n是否为目标节点,若是,则问题有解,成功退出。问题的解就是沿着n到s0的路径得到。若不是转⑥ ⑥扩展节点n生成一组不是n的祖先的后继节点,并将它们记为集合m,将m中的这些节点作为n的后继节点加入图g中 ⑦对未在g中出现过的(open和closed表中未出现过的)集合m中的节点, 设置一个指向父节点n的指针,并把这些节点放入open表中;对于已在g中出现过的m中的节点,确定是否需要修改指向父节点的指针;对于已在g中出现过并已在closed表中的m中的节点,确定是否需要修改通向他们后继节点的指针。 ⑧按某一任意方式或某种策略重排open表中节点的顺序 ⑨转③ 3.八数码游戏问题的盲目搜索技术 宽度优先搜索: 1、定义 如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索(breadth-first search)。 2、特点 这种搜索是逐层进行的;在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。 3、宽度优先搜索算法 (1) 把起始节点放到open表中(如果该起始节点为一目标节点,则求得一个解答)。 (2) 如果open是个空表,则没有解,失败退出;否则继续。 (3) 把第一个节点(节点n)从open表移出,并把它放入closed的扩展节点表中。 (4) 扩展节点n。如果没有后继节点,则转向上述第(2)步。 (5) 把n的所有后继节点放到open表末端,并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第(2)步。 流程图: 性质: 当问题有解时,一定能找到解。 当问题为单位消耗值,且问题有解时,一定能找到最优解。 算法与问题无关,具有通用性。 时间效率和空间效率都比较低。 深度优先搜索:

相关文档