八数码问题A算法的实现及性能分析(12700字)

发表于:2016.11.16来自:www.ttfanwen.com字数:12700 手机看范文

八数码问题A*算法的实现及性能分析

云南大学信息学院

专业:计算机软件与理论

1

目录

一、8数码问题 ............................................................................................................ 3

1.问题描述 ....................................................................................................................................... 3

2. 八数码问题形式化描述 .............................................................................................................. 3

3. 解决方案 ..................................................................................................................................... 4

二、A*算法 ................................................................................................................... 4

1. A*搜索算法一般介绍 .................................................................................................................. 4

2. A*算法的伪代码 .......................................................................................................................... 5

3. 建立合适的启发式 ...................................................................................................................... 6

三、算法实现及性能比较 ........................................................................................... 7

四、算法性能分析 ....................................................................................................... 8

五、结论 ....................................................................................................................... 9

六、参考文献 ............................................................................................................... 9

附录 ............................................................................................................................... 9

2

一、8数码问题

1.问题描述

八数码问题是指这样一种游戏:将分别标有数字1,2,3,…,8 的八块正方形数码牌任意地放在一块3×3 的数码盘上。放牌时要求不能重叠。于是,在3×3 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,不断移动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动,在四个角落上有2个方向可移动,在其他位置上有3个方向可移动,问题描述如图1-1所示

初始状态 过渡状态 最终状态

图1-1 八数码问题执行过程

2. 八数码问题形式化描述

初始状态:

初始状态向量:规定向量中各分量对应的位置,各位置上的数字。把3×3的棋盘按从左到右,从上到下的顺序写成一个一维向量。我们可以设定初始状态:<1,5,2,4,0,3,6,7,8>

后继函数:

按照某种规则移动数字得到的新向量。例如:

<1,5,2,4,0,3,6,7,8>?<1,0,2,4,5,3,6,7,8>

目标测试:

新向量是都是目标状态。即<1,2,3,4,5,6,7,8,0>是目标状态?

路径耗散函数:

每次移动代价为1,每执行一条规则后总代价加1。

八数码问题A算法的实现及性能分析

八数码问题A算法的实现及性能分析

八数码问题A算法的实现及性能分析

3

3. 解决方案

该问题是一个搜索问题。它是一种状态到另一种状态的变换。要解决这个问题,必须先把问题转化为数字描述。由于八数码是一个3*3的矩阵,但在算法中不实用矩阵,而是将这个矩阵转化为一个一维数组,使用这个一维数组来表示八数码,但是移动时要遵守相关规则。

(1) 可用如下形式的规则来表示数字通过空格进行移动:

<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>

(2)共24条移动规则,对应与每个位置的移动规则。

(3)搜索顺序举例:

1) 优先移动行数小的棋子(数字) 2) 同一行中优先移动列数大的棋子

(4)约束规则:不使离开既定位置的数字数增加

八数码的节点扩展应当遵循棋子的移动规则。按规则,每一次可以将一个与空格相邻的棋子移动到空格中,实际上也可以看做空格的相反方向移动。空格的移动方向可以是上下左右,当然不能出边界。棋子的位置,也就是保存状态的数组元素的下标,空格移动后,相应位置发生变化,在不移出边界的条件下,空格向右,下,左,上移动后,新位置是原位置分别加上1,3,-1,-3。在这里,空格可以用任意数字表示。操作本文用u(up) r(right) d(down) l(left) 分别表示空格的向上向右向下向左四个操作。

经分析,8数码问题的搜索策略共有:1.广度优先搜索、2.深度优先搜索、

3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索,等等。其中广度优先搜索法是可采纳的,有界深度优先搜索法是不完备的,最好优先和局部择优搜索法是启发式搜索法。

实验采用启发式A*搜索算法来实现。

二、A*算法

1. A*搜索算法一般介绍

A* 算法实际是一种启发式搜索,所谓启发式搜索,就是利用一个估价函数评估每次的的决策的价值,决定先尝试哪一种方案,这样可以极大的优化普通的广度优先搜索。一般来说,从出发点(A)到目的地(B)的最短距离是固定的,我们可以写一个函数 judge() 估计 A 到 B 的最短距离,如果程序已经尝试着从出发点 A 沿着某条路线移动到了 C 点, 那么我们认为这个方案的 A B 间的估 4

计距离为 A 到 C 实际已经行走了的距离 H 加上用 judge() 估计出的 C 到

B 的距离。

如此,无论我们的程序搜索展开到哪一步,都会算出一个评估值,每一次决策后,将评估值和等待处理的方案一起排序,然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步,一直循环到对象移动到目的地,或所有方案都尝试过却没有找到一条通向目的地的路径则结束。

A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为: f'(n) = g'(n) + h'(n)

这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值,h'(n)是n到目标的最断路经的启发值。由于这个f'(n)其实是无法预先知道的,所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n),但g(n)>=g'(n)才可(大多数情况下都是满足的,可以不用考虑),h(n)代替h'(n),但h(n)<=h'(n)才可。可以证明应用这样的估价函数是可以找到最短路径的,也就是可采纳的。

2. A*算法的伪代码

创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。

算起点的估价值;

将起点放入OPEN表;

while(OPEN!=NULL)

{

从OPEN表中取估价值f最小的节点n;

if(n节点==目标节点){

break;

}

for(当前节点n 的每个子节点X)

{

算X的估价值;

if(X in OPEN)

{

if( X的估价值小于OPEN表的X估价值 ){

把n设置为X的父亲;

更新OPEN表中的估价值; //取最小路径的估价值

}

}

if(X inCLOSE) {

5

if( X的估价值小于CLOSE表的X估价值 ){

把n设置为X的父亲;

将该节点从close表中除去

把X节点放入OPEN //取最小路径的估价值

}

}

if(X not inboth){

把n设置为X的父亲;

求X的估价值;

并将X插入OPEN表中; //升序排列open

}

}//end for

将n节点插入CLOSE表中;

按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小,从最小路径的节点向下进行。

}//end while(OPEN!=NULL)

保存路径,即从终点开始,每个节点沿着父节点移动直至起点,这就是你的路径;

3. 建立合适的启发式

A*算法有个计算公式 f(x) = g(x)+h(x)

其中g(x)为从起始状态到当前状态所消耗的步数,h(x)为一个启发值,估算从当前状态到目标状态所需的步数,一般h(x)小于等于实际需要步数为好,这样不会将最优解忽略,因为h(x)和解空间有一些关系,如果h(x)设置的比实际需要的步数多,那么解空间就有可能将最优解忽略。举个例子吧,宽度优先搜索就是h(x)=0带来的效果,深度优先搜索就是g(x)=0带来的效果,不过h(x)距离h*(x)[实际需要的步数]的程度不能过大,否则h(x)就没有过强的区分能力,算法效率并不会很高。对一个好的h(x)的评价是:h(x)在h*(n)[实际需要的步数]的下界之下,并且尽量接近h*(n)[实际需要的步数].

那么8数码问题g(x) 为经过上下左右移动空格附近的数字来得到新状态所需步数,h(x)为当前状态与目标状态的距离,就是所有不在目标位置的数字总和,必然小于h*(x)

6

三、算法实现及性能比较

这里通过c++语言来实现各种排序算法(源码见附录),程序运行环境为windows 7,所用编译器为vs2010。

实验分别以不同的初始棋盘和相同的目标棋盘为例进行测试。 初始数码棋盘1:2 0 3 1 4 6 7 5 8

初始数码棋盘2:2 4 3 0 6 8 1 7 5

初始数码棋盘3:2 3 7 6 4 8 1 0 5

初始数码棋盘4:3 2 4 5 0 7 8 1 6

初始数码棋盘5:4 0 3 2 6 8 1 7 5

初始数码棋盘6:1 4 3 5 7 0 2 6 8

初始数码棋盘7:4 6 3 2 8 5 1 0 7

目标数码棋盘:1 2 3 4 5 6 7 8 0

实验部分结果如图3-1:

八数码问题A算法的实现及性能分析

图3-1.测试结果

7

四、算法性能分析

在测试中我们根据不同的初始数码状态相同的目标数码状态,产生不同的移动步骤,并给出了其步数和运行时间(单位ms)。表1为不同的初始数码状态相同的目标数码状态测试后得到的运行时间数据。表2为不同的初始数码状态相同的目标数码状态能否的到正确的步骤与否的数据。

八数码问题A算法的实现及性能分析

八数码问题A算法的实现及性能分析

八数码问题A算法的实现及性能分析

八数码问题A算法的实现及性能分析

表2 能否得到正确步骤

为了直观起见,根据实验数据画出不同的初始数码状态相同的目标数码状态下时间随步数的变化趋势图如图3-2所示:

3000

2500

2000

Time(ms)

1500

1000

500

Steps

图3-2时间随步数的变化趋势图

8

根据实验数据表2,我们可得到该算法得到正确步骤路径的概率为:71.42%。 五、结论

最后我们得出结论:

时间性能上,

算法所需时间随步数的增加而逐渐呈增加趋势,但并不是线性增长。部分时间不随移动步数变化。

该算法能得到正确的解概率约为71.42%

六、参考文献

1.《Artificial intelligence :;a modern approach 人工智能 : 一种现代方法》 作者:Russell, Stuart J. 出版社:清华大学出版社

2.百度百科网站

附录

#include<iostream>

#include<time.h>

#include<windows.h>

#include<vector>

#include<cmath>

using namespace std;

struct node{

};

vector<node> store; //存放路径节点

9 int a[3][3]; //存放矩阵 int father; //父节点的位置 int gone; //是否遍历过,1为是,0为否 int fn; //评价函数的值 int x,y; //空格的坐标 int deep; //节点深度

int mx[4]={-1,0,1,0};

int my[4]={0,-1,0,1}; //上下左右移动数组

int top; //当前节点在store中的位置

bool check(int num) //判断store[num]节点与目标节点是否相同,目标节点储存在store[0]中

{

for(int i=0;i<3;i++){

for(int j=0;j<3;j++){

if(store[num].a[i][j]!=store[0].a[i][j])

return false;

}

}

return true;

}

bool search(int num) //判断store[num]节点是否已经扩展过 ,没有扩展返回true {

int pre=store[num].father; //pre指向store[num]的父节点位置

bool test=true;

while(!pre){ //循环直到pre为0,既初始节点

for(int i=0;i<3;i++){

for (int j=0;j<3;j++){

if(store[pre].a[i][j]!=store[num].a[i][j]){

test=false;

break;

}

}

if(test==false) break;

}

if(test==true) return false;

pre=store[pre].father; //pre继续指向store[pre]父节点位置

}

return true;

}

void print(int num) //打印路径,store[num]为目标节点

{

vector<int> temp; //存放路径

int pre=store[num].father;

temp.push_back(num);

while(pre!=0){ //从目标节点回溯到初始节点

temp.push_back(pre);

pre=store[pre].father;

10

}

} cout<<endl; cout<<"*********数码移动步骤*********"<<endl; int mm=1; //步数 for(int m=temp.size()-1;m>=0;m--){ } cout<<"所需步数为: "<<store[num].deep<<endl; return; cout<<"---第"<<mm<<"步---:"<<endl; for(int i=0;i<3;i++){ } mm++; cout<<endl; for(int j=0;j<3;j++){ } cout<<endl; cout<<store[temp[m]].a[i][j]<<" ";

int get_fn(int num) //返回store[num]的评价函数值 {

}

11 int fn_temp=0; //评价函数值 bool test=true; for(int i=0;i<3;i++){ //当找到一个值后,计算这个值位置与目标位置的距离差,test置 for(int j=0;j<3;j++){ test=true; for(int k=0;k<3;k++){ for(int l=0;l<3;l++){ 为false后继续寻找下一个值 if((store[num].x!=i||store[num].y!=j)&&store[num].a[i][j]==store[0].a[k][l]){ // } fn_temp=fn_temp+store[num].deep; //加上节点深度 return fn_temp; } } } if(test==false) break; } if(test==false) break; fn_temp=fn_temp+abs(i-k)+abs(j-l); test=false; 寻值时排除空格位

void kongxy(int num) //获得空格坐标 {

}

int main()

{

for(int i=0;i<3;i++){ } return; for(int j=0;j<3;j++){ } if(store[num].a[i][j]==0){ } store[num].x=i; store[num].y=j; cout<<"-----------A*算法解决8数码问题------------"<<endl; while(true){ store.clear(); //清空store vector<int> open; //建立open表 int i,j,m,n,f; int min; //store[min]储存fn值最小的节点 int temp; bool test; top=1; //当前节点在store的位置,初始节点在store[1] int target[9]; int begin[9]; //储存初始状态和目标状态,用于判断奇偶 int t1=0,t2=0; //初始状态和目标状态的奇偶序数 node node_temp; store.push_back(node_temp); store.push_back(node_temp); //用于创建store[0]和store[1],以便下面使用 cout<<"请输入初始数码棋盘状态,0代表空格:"<<endl; //输入初始状态,储存在store[1]test=false; while(test==false){ f=0; for(i=0;i<3;i++){ for(j=0;j<3;j++){ cin>>temp; store[1].a[i][j]=temp; begin[f++]=temp; 12

}

}

test=true;

for(i=0;i<8;i++){ //检查是否有重复输入,若有则重新输入 for(j=i+1;j<9;j++){

if(begin[i]==begin[j]){

test=false;

break;

}

}

if(test==false) break;

}

if(test==false) cout<<"输入重复,请重新输入:"<<endl;

}

kongxy(1); //找出空格的坐标

cout<<"请输入目标数码棋盘状态,0代表空格: "<<endl; //输入目标状态,储存在store[0]中

test=false;

while(test==false){

f=0;

for(i=0;i<3;i++){

for(j=0;j<3;j++){

cin>>temp;

store[0].a[i][j]=temp;

target[f++]=temp;

}

}

test=true;

for(i=0;i<8;i++){ //检查是否有重复输入,若有则重新输入 for(j=i+1;j<9;j++){

if(target[i]==target[j]){

test=false;

break;

}

}

if(test==false) break;

}

if(test==false){

cout<<"输入重复,请重新输入:"<<endl;

continue; //若重复,重新输入

}

13

} for(i=0;i<9;i++){ //检查目标状态与初始状态是否匹配 } if(test==false) cout<<"输入与初始状态不匹配,请重新输入:"<<endl; test=false; for(j=0;j<9;j++){ } if(test==false) break; if(begin[i]==target[j]){ } test=true; break; for(i=1;i<9;i++){ //判断奇偶序数是否相同,若不相同则无法找到路径 } for(i=1;i<9;i++){ } if(!(t1%2==t2%2)){ } cout<<"无法找到路径."<<endl; cout<<endl; //system("pause"); //return 0; continue; for(j=1;i-j>=0;j++){ } if(target[i]>target[i-j]){ } if(target[i-j]!=0) t2++; for(j=1;i-j>=0;j++){ } if(begin[i]>begin[i-j]){ } if(begin[i-j]!=0) t1++; LARGE_INTEGER Freg; LARGE_INTEGER Count1,Count2; QueryPerformanceFrequency(&Freg); QueryPerformanceCounter(&Count1);//获取时间Count1 double d; 14

点 store[1].father=0; //初始化参数 store[1].gone=0; store[1].deep=0; //初始节点的父节点为0 store[1].fn=get_fn(1); if(check(1)){ //判断初始状态与目标状态是否相同 } open.push_back(1); //把初始状态在store中的位置数压入open表中 while(!open.empty()){ //当open表不为空时,开始寻找路径 if(check(top)) break; min=top; int i_min=0; for(i=0;i<open.size();i++){ //遍历open表中元素,找出store中fn值最小的节 } store[min].gone=1; open.erase(open.begin()+i_min); //把最小节点标记遍历过,并从open表中删除 m=store[min].x; n=store[min].y; //空格坐标 for(f=0;f<4;f++){ //上下左右移动空格 i=m+mx[f]; j=n+my[f]; if(i>=0&&i<=2&&j>=0&&j<=2){ //当变换后的空格坐标在矩阵中时,开始 top++; store.push_back(store[min]); //把store[min]压入store中成为新增store[top].father=min; //新增节点的父节点为min 15 print(1); //system("pause"); //return 0; cout<<endl; continue; if(store[open[i]].fn<=store[min].fn&&store[open[i]].gone==0){ } min=open[i]; i_min=i; 移动 节点,位置为store[top]

+1

store[top].gone=0; //新增节点未被访问 store[top].deep=store[min].deep+1; //新增节点的深度为父节点深度 } } } temp=store[top].a[m][n]; //交换空格与相邻数字 store[top].a[m][n]=store[top].a[i][j]; store[top].a[i][j]=temp; store[top].x=i; //移动后的空格坐标 store[top].y=j; store[top].fn=get_fn(top); //移动后的fn值 open.push_back(top); //把top压入open表中 if(check(top)){ //检查是否到达目标 } if(search(top)==false){ //检查新增节点是否被访问过,若访问过, } top--; store.pop_back(); open.pop_back(); print(top); //system("pause"); //return 0; break; 则删除此节点 } QueryPerformanceCounter(&Count2);//获取时间Count2 d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;//计cout<<"算法时间为为"<<d<<" ms."<<endl; cout<<endl; 算时间差,d的单位为ms. return 0; system("pause");

} 16



更多类似范文
┣ 人工智能大作业八数码问题 3700字
┣ 采用A算法解决八数码问题 10400字
┣ 人工智能A算法八数码报告 8300字
┣ 实验一 八数码 5100字
┣ 更多八数码问题实验报告
┗ 搜索类似范文

更多相关推荐:
prolog实验报告600字

华北电力大学实验报告实验名称PROLOG语言编程练习及图搜索问题求解课程名称人工智能及应用专业班级学生姓名学号成绩指导教师实验日期20xx年5月实验报告如打印纸张用A4左装订页边距上下25cm左29cm右21c...

人工智能实验报告(华北电力大学科技学院)600字

华北电力大学科技学院实验报告实验名称课程名称人工智能及应用专业班级软件12k1学生姓名马云峰号1219xx020xx6成绩指导教师刘丽实验日期20xx514学华北电力大学科技学院实验报告第页共页华北电力大学科技...

人工智能8位数码难题的问题求解

1234567891011121314

专栏推荐
大家在关注