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

A*算法求解八数码问题●open 表、closed 表数据结构的选择：1)把s放入open表，记f=h，令closed为空表。

2)重复下列过程，直到找到目标节点为止。

若open表为空表，则宣告失败。

3)选取open表中未设置过的具有最小f值的节点为最佳节点bestnode，并把它放入closed表。

4)若bestnode为一目标节点，则成功求得一解。

5)若bestnode不是目标节点，则扩展之，产生后继节点succssor。

6)对每个succssor进行下列过称：a)对每个succssor返回bestnode的指针。

b)计算g（suc）=g（bes）+k（bes，suc）。

c)如果succssore open，称此节点为old，并填到bestnode的后继节点表中。

d)比较新旧路劲代价。

如果g（suc）<g(old)，则重新确定old的父辈节点为bestnode，记下较小代价g（old），并修真f（old）值。

e)若至old节点的代价较低或一样，则停止扩展节点。

f)若succssore不再closed表中，则看其是否在closed表中。

g)若succssore在closed表中，则转向（c）。

h)若succssore既不在open表中，又不在closed表中，则把它放入open表中，并添入bestnode后裔表中，然后转向（7）。

i)计算f值j)Go loop●节点的数据结构：static int target[9]={1,2,3,8,0,4,7,6,5}; 全局静态变量，表示目标状态class eight_num{private:int num[9]; 定义八数码的初始状态int not_in_position_num; 定义不在正确位置八数码的个数int deapth; 定义了搜索的深度int eva_function; 评价函数的值，每次选取最小的进行扩展public:eight_num* parent; 指向节点的父节点eight_num* leaf_next; 指向open表的下一个节点eight_num* leaf_pre; 指向open 表的前一个节点初始状态的构造函数eight_num(int init_num[9]);eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9){}eight_num(void){ }计算启发函数g(n)的值void eight_num::cul_para(void){}显示当前节点的状态void eight_num::show(){}复制当前节点状态到一个另数组中void eight_num::get_numbers_to(int other_num[9]){}设置当前节点状态(欲设置的状态记录的other数组中)void eight_num::set_num(int other_num[9]){}eight_num& eight_num::operator=(eight_num& another_8num){} eight_num& eight_num::operator=(int other_num[9]){}int eight_num::operator==(eight_num& another_8num){}int eight_num::operator==(int other_num[9]){}空格向上移int move_up(int num[9]){}空格向下移int move_down(int num[9]){}空格向左移int move_left(int num[9]){}空格向右移int move_right(int num[9]){}判断可否解出int icansolve(int num[9],int target[9]){}判断有无重复int existed(int num[9],eight_num *where){}寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start){}}A*算法求解框图：●分析估价函数对搜索算法的影响：估价函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。

a星算法求解八数码问题python一、介绍八数码问题是一种经典的智力游戏，也是人工智能领域中的经典问题之一。

在这个问题中，有一个3×3的棋盘，上面摆着1至8这8个数字和一个空格，初始状态和目标状态都已知。

要求通过移动数字，将初始状态变换成目标状态。

其中空格可以和相邻的数字交换位置。

为了解决这个问题，我们可以使用A*算法。

本文将详细介绍如何用Python实现A*算法来求解八数码问题。

二、A*算法简介A*算法是一种启发式搜索算法，常用于寻找最短路径或最优解等问题。

它基于Dijkstra算法，并加入了启发式函数来加速搜索过程。

在A*算法中，每个节点都有两个估价值：g值和h值。

g值表示从起点到该节点的实际代价，h值表示从该节点到目标节点的估计代价。

启发式函数f(n) = g(n) + h(n) 表示从起点到目标节点的估计总代价。

A*算法采用优先队列来保存待扩展的节点，并按照f(n)值从小到大排序。

每次取出队头元素进行扩展，并将扩展出来的新节点按照f(n)值插入队列中。

当扩展出目标节点时，算法结束。

三、八数码问题的状态表示在八数码问题中，每个状态都可以表示为一个3×3的矩阵。

我们可以用一个一维数组来表示这个矩阵，其中0表示空格。

例如，初始状态可以表示为[2, 8, 3, 1, 6, 4, 7, 0, 5]，目标状态可以表示为[1, 2, 3, 8, 0, 4, 7, 6, 5]。

四、A*算法求解八数码问题的步骤1.将初始状态加入优先队列中，并设置g值和h值为0。

2.从队头取出一个节点进行扩展。

如果该节点是目标节点，则搜索结束；否则，将扩展出来的新节点加入优先队列中。

3.对于每个新节点，计算g值和h值，并更新f(n)值。

如果该节点已经在优先队列中，则更新其估价值；否则，将其加入优先队列中。

4.重复第2步至第3步直到搜索结束。

五、Python实现以下是用Python实现A*算法求解八数码问题的代码：```import heapqimport copy# 目标状态goal_state = [1,2,3,8,0,4,7,6,5]# 启发式函数：曼哈顿距离def h(state):distance = 0for i in range(9):if state[i] == 0:continuerow = i // 3col = i % 3goal_row = (state[i]-1) // 3goal_col = (state[i]-1) % 3distance += abs(row - goal_row) + abs(col - goal_col)return distance# A*算法def A_star(start_state):# 初始化优先队列和已访问集合queue = []visited = set()# 将初始状态加入优先队列中，并设置g值和h值为0heapq.heappush(queue, (h(start_state), start_state, 0))while queue:# 取出队头元素进行扩展f, state, g = heapq.heappop(queue)# 如果该节点是目标节点，则搜索结束；否则，将扩展出来的新节点加入优先队列中。

人工智能实验报告学院：信息科学与工程学院班级：自动化0901班学号： 0909090316姓名：孙锦岗指导老师：刘丽珏日期：2011年12月20日一、实验名称、目的及内容实验名称：八数码难题的搜索求解演示实验目的：加深对图搜索策略概念的理解，掌握搜索算法。

实验内容要求：以八数码难题为例演示广度优先或深度优先搜索、A算法（本实验使用的是广度优先搜索）的搜索过程，争取做到直观、清晰地演示算法。

八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态如图所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。

试编一程序实现这一搜索过程。

二、实验原理及基本技术路线图实验原理：八数码问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。

我们可以把一个随机排列的数组从左到右从上到下用一个数组表示，例如｛８，７，１，５，２，６，３，４，０｝其中０代表空格。

它在奇序列位置上。

在这个数组中我们首先计算它能够重排列出来的结果，公式就是：∑（Ｆ（Ｘ））＝Ｙ，其中Ｆ（Ｘ），就是一个数他前面比这个数小的数的个数，Ｙ为奇数和偶数个有一种解法。

那么上面的数组我们就可以解出它的结果。

数据结构：本实验使用的数据结构是队列，应用队列先进先出的特点来实现对节点的保存和扩展。

首先建立一个队列，将初始结点入队，并设置队列头和尾指，然后取出队列（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列，然后判断扩展出的新结点与队列中的结点是否重复，如果重复则，否则记录其父结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。

否则如果队列头的结点可以扩展，直接返回第二步。

否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。

用A算法实现的八数码问题C++源码用A*算法实现的八数码问题C++源码#include <iomanip>#include <stdlib.h>#include <iostream.h>#include <time.h>#include <stdio.h>#include <conio.h>//using namespace std;//定义默认目标状态static int target[9]={1,2,3,8,0,4,7,6,5};//八数码类class EightNum{private:int num[9];int diffnum;//与目标状态位置不同的数的个数. int deapth;//派生的深度.int evalfun;//状态的估价值public:EightNum *parent;//生成当前状态的父状态. EightNum *state_pre;//当前状态前生成状态. EightNum *state_next;//当前状态后生成状态.//成员函数声明EightNum(void);EightNum(int initnum[9]);int get_evalfun();void eval_func();void getnum(int num1[9]);void setnum(int num1[9]);void show(void);void show_spec(int i);int null_position(void);EightNum& operator =(EightNum& NewEightN);EightNum& operator =(int num2[9]);int operator ==(EightNum& NewEightN);int operator ==(int num2[9]);};//八数码类定义//八数码类成员函数定义EightNum::EightNum(void){//初始化数组num[]for(int i=0;i<9;i++)num[i]=i;}EightNum::EightNum(int initnum[9]){//用输入的数组初始化num[]for(int i=0;i<9;i++)num[i]=initnum[i];}int EightNum::get_evalfun(){//返回估价值return evalfun;}void EightNum::eval_func(){//估价函数int i,temp;temp=0;for(i=0;i<9;i++){if(num[i]!=target[i])temp++;}diffnum=temp;if(this->parent==NULL) deapth=0;else deapth=this->parent->deapth+1;evalfun=deapth+temp;}void EightNum::getnum(int num1[9]){//取出八数码数值for(int i=0;i<9;i++)num1[i]=num[i];}void EightNum::setnum(int num1[9]){//写入八数码数值for(int i=0;i<9;i++)num[i]=num1[i];}void EightNum::show(){//八数码输出函数for(int i=0;i<9;i++){cout<<num[i]<<" ";if((i+1)%3==0)cout<<"\n";}}void EightNum::show_spec(int i){//结果步骤输出函数cout<<num[i];cout<<"<--";}int EightNum::null_position(){//查找空格位置int i,j;for(i=0;i<9;i++){if(num[i]==0)j=i;}return j;}EightNum& EightNum::operator =(EightNum& NewEightN){//"="重载,针对八数码类的引用for(int i=0;i<9;i++)num[i]=NewEightN.num[i];diffnum=NewEightN.diffnum;deapth=NewEightN.deapth+1;evalfun=diffnum+deapth;return *this;}EightNum& EightNum::operator =(int num2[9]){//"="重载,用于数组赋值for(int i=0;i<9;i++)num[i]=num2[i];return *this;}int EightNum::operator ==(EightNum& NewEightN){//"=="重载,用于八数码类中状态的比较int compere=1;for(int i=0;i<9;i++)if(num[i]!=NewEightN.num[i]){compere=0;break;}if(compere==0) return 0;else return 1;}int EightNum::operator ==(int num2[9]){//"=="重载,用于数组的比较int compere=1;for(int i=0;i<9;i++)if(num[i]!=num2[i]){compere=0;break;}if(compere==0) return 0;else return 1;}//八数码类函数定义结束int solve(int num[9],int target[9]){//判断是否有解的函数,利用逆序数的奇偶性来判断int i,j;int num_con=0,tar_con=0;for(i=0;i<9;i++)for(j=0;j<i;j++){if(num[j]<num[i] && num[j]!=0)num_con++;if(target[j]<target[i] && target[j]!=0)tar_con++;}num_con=num_con%2;tar_con=tar_con%2;if((num_con==0 && tar_con==0)||(num_con==1 && tar_con==1))return 1;elsereturn 0;}//空格移动函数int moveup(int num[9]){//空格上移for(int i=0;i<9;i++)if(num[i]==0) break;if(i<3) return 0;else {num[i]=num[i-3];num[i-3]=0;return 1;}}int movedown(int num[9]){//空格下移for(int i=0;i<9;i++)if(num[i]==0) break;if(i>5) return 0;else {num[i]=num[i+3];num[i+3]=0;return 1;}}int moveleft(int num[9]){//空格左移for(int i=0;i<9;i++)if(num[i]==0) break;if(i==0||i==3||i==6) return 0;else {num[i]=num[i-1];num[i-1]=0;return 1;}}int moveright(int num[9]){//空格右移for(int i=0;i<9;i++)if(num[i]==0) break;if(i==2||i==5||i==8) return 0;else {num[i]=num[i+1];num[i+1]=0;return 1;}}int exist(int num[9],EightNum *a){//判断是否重复搜索函数EightNum *t;for(t=a;t!=NULL;t=t->parent)if(*t==num) return 1;//调用"=="进行数组比较else return 0;}EightNum* find(EightNum *s){//寻找估价函数值最小的节点EightNum *m,*n;int min=s->get_evalfun();m=n=s;for(m=s;m!=NULL;m=m->state_next){if(min>m->get_evalfun()){n=m;min=m->get_evalfun();}return n;}}int main(void)//主函数{int i,j;int flag;int num[9];int error;do{//输入判断error=0;cout<<"请输入八数码问题的初始状态(用0代表空格,中间用空格隔开):"<<endl;for(i=0;i<9;i++){flag=0;cin>>num[i];for(j=0;j<i;j++)if(num[j]==num[i])flag=1;if(num[i]<0||num[i]>8||flag==1){error++;}}if(error!=0)cout<<"输入数据错误!请重新输入!"<<endl;}while(error!=0);cout<<"是否改变默认的目标状态?(y/n)";char input;cin>>input;int error1;if(input=='y'||input=='Y'){do{error1=0;cout<<"请输入新的目标状态(用0代表空格):"<<endl;for(i=0;i<9;i++){flag=0;cin>>target[i];for(j=0;j<i;j++)if(target[j]==target[i])flag=1;if(target[i]<0||target[i]>9||flag==1){error1++;}}if(error1!=0)cout<<"输入数据错误!请重新输入!"<<endl;}while(error1!=0);}//实例化初始状态和目标状态,并输出.EightNum start(num),T arget(target);start.parent=start.state_next=start.state_pre=NULL; start.eval_func();cout<<"初始状态为:"<<endl;start.show();cout<<"目标状态为:"<<endl;Target.show();//判断是否有解int m=solve(num,target);if(m==0){cout<<"此状态无解!"<<endl;return 0;}//进入A*算法搜索double time;clock_t startt,finisht;int ok=0;//结束标识位int space=0;//所耗费空间startt=clock();//开始时间EightNum *BestNode=&start,*Node=&start,*New8Num,*r; while(BestNode!=NULL&&ok!=1){BestNode=find(Node);if(*BestNode==Target){//调用"=="操作符ok=1;break;}r=BestNode->state_pre;//生成向上移的节点BestNode->getnum(num);if(moveup(num) && !exist(num,BestNode)){New8Num=new EightNum;New8Num->setnum(num);New8Num->parent=BestNode;New8Num->eval_func();New8Num->state_pre=r;if(r==NULL)Node=New8Num;elser->state_next=New8Num;r=New8Num;space++;}//生成向下移的节点BestNode->getnum(num);if(movedown(num) && !exist(num,BestNode)){ New8Num=new EightNum;New8Num->setnum(num);New8Num->parent=BestNode;New8Num->eval_func();New8Num->state_pre=r;if(r==NULL)Node=New8Num;elser->state_next=New8Num;r=New8Num;space++;}//生成向左移的节点BestNode->getnum(num);if(moveleft(num) && !exist(num,BestNode)){ New8Num=new EightNum;New8Num->setnum(num);New8Num->parent=BestNode;New8Num->eval_func();New8Num->state_pre=r;if(r==NULL)Node=New8Num;elser->state_next=New8Num;r=New8Num;space++;}//生成向右移的节点BestNode->getnum(num);if(moveright(num) && !exist(num,BestNode)){New8Num=new EightNum;New8Num->setnum(num);New8Num->parent=BestNode;New8Num->eval_func();New8Num->state_pre=r;if(r==NULL)Node=New8Num;elser->state_next=New8Num;r=New8Num;space++;}r->state_next=BestNode->state_next;if(BestNode->state_next!=NULL)BestNode->state_next->state_pre=r;BestNode->state_next=BestNode->state_pre=NULL; }finisht=clock();//输出搜索结果if(ok==1){time=(double)(finisht-startt)*1000/CLOCKS_PER_SEC; EightNum *p,*q=NULL;int step=0;for(p=BestNode->parent;p!=NULL;p->parent){if(step==0){i=8;p->show_spec(i);i=p->null_position();}else{p->show_spec(i);i=p->null_position();}if (step==8||step==18||step==28||step==38||step==48) cout<<"\n";step++;}cout<<"\nA*算法处理结果：所耗时间:";cout<<time;cout<<"ms, ";cout<<"所耗空间:";cout<<space;cout<<"块, ";cout<<"最短路径步数:";cout<<step;cout<<"步 !\n";}elsecout<<"\nA*算法无法找到最短路径!\n";}。

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

例如：图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星算法的8数码问题求解⽅案设计（1）⼀、问题描述8数码问题⼜称9宫问题，与游戏“华容道”类似。

意在给定的33棋格的8个格⼦内分别放⼀个符号，符号之间互不相同，余下的⼀格为空格。

并且通常把8个符号在棋格上的排列顺序称作8数码的状态。

开始时，规则给定⼀个初始状态和⼀个⽬标状态，并要求被试者对棋格内的符号经过若⼲次移动由初始状态达到⽬标状态，这个过程中只有空格附近的符号可以朝空格的⽅向移动，且每次只能移动⼀个符号。

为⽅便编程和表⽰，本⽂中8个格⼦内的符号分别取1—8的8个数字表⽰，空格⽤0表⽰。

并给定8数码的初始状态和⽬标状态分别如图1、2所⽰。

图1 初始状态图2 ⽬标状态则要求以图1为初始状态，通过交换0和0的上、下、左、右四个⽅位的数字（每次只能和其中⼀个交换），达到图2所⽰⽬标状态。

⼆、实验⽬的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利⽤A*算法求解N数码难题，理解求解流程和搜索顺序。

三、实验任务1）实现类似于如图所⽰N数码难题演⽰程序。

2）⽤你所熟悉的程序语⾔实现，可以B/S实现，也可以C/S实现四、算法设计根据任务要求，本⽂采⽤A*搜索算法。

但要在计算机上通过编程解决该问题，还应当解决该问题在计算机上表⽰的⽅式，并设计合适的启发函数，以提⾼搜索效率。

①状态的表⽰在A*算法中，需要⽤到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。

因此在表⽰当前状态的变量中，必须要有能指向下⼀个扩展节点的指针，以完成对open表中元素的索引。

从这⼀点上看，open表中的元素相互间即构成了⼀个线性表，因此初步选定使⽤结构体表⽰问题的状态。

如图3所⽰，表⽰问题的结构体包括表⽰当前节点状态的DATA和指向open 表中下⼀个待扩展节点的指针NEXT。

图3 结构体现在进⼀步考虑DATA中包括的内容：如图1、2所⽰，8数码问题的提出是以⼀个33数表表⽰的，因此本⽂中采⽤⼀个33的⼆维数组s[3][3]表⽰当前状态的具体信息。

/* A*算法伪代码算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）输入：初始状态，目标状态输出：从初始状态到目标状态的一系列过程算法描述：Begin：读入初始状态和目标状态，并计算初始状态评价函数值f；根据初始状态和目标状态，判断问题是否可解；If(问题可解)把初始状态加入open表中；While（未找到解&&状态表非空）①在open表中找到评价值最小的节点，作为当前结点；②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③；③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；④对于新扩展的状态结点，判断其是否重复，若不重复把其加入到open表中；⑤把当前结点从open表中移除；End whileEnd if输出结果；End程序中我们假设空格无论往那个方向移动一步的代价都是1，取f(n) = g(n) + h(n)为估价函数其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价，由错位数算出。

在VC6.0下运行成功*/#include "iostream"#include <time.h>#include <stdio.h>#include <dos.h>#include <conio.h>using namespace std;static int target[9]; //全局静态变量，表明目标状态//class definitionclasseight_num{private:intnum[9]; //定义八数码的初始态intnot_in_position_num; //定义不在正确位置的八数码的个数intdeapth; //定义了搜索的深度（当前节点离起始节点的距离）inteva_function; //评价函数f的值，每次选取最小的进行下一步的扩展public:eight_num* parent; //指向节点的父节点eight_num* leaf_next; //指向open表的下一个节点eight_num* leaf_pre; //指向open 表的前一个节点eight_num(intinit_num[9]); //初始状态的构造函数eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9){num[0]=num1;num[1]=num2;num[2]=num3;num[3]=num4;num[4]=num5;num[5]=num6;num[6]=num7;num[7]=num8;num[8]=num9;}eight_num(void){for (int i=0;i<9;i++)num[i]=i;}void cul_para(void); //计算启发函数g(n)的值void get_numbers_to(intother_num[9]); //复制当前节点状态到一个另数组中intget_nipn(void){returnnot_in_position_num;}intget_deapth(void){returndeapth;}intget_evafun(void){returneva_function;}voidset_num(intother_num[9]);void show(void); //显示当前节点的状态eight_num& operator=(eight_num&);eight_num& operator=(intother_num[9]);int operator==(eight_num&);int operator==(intother_num[9]);};//计算启发函数g(n)的值voideight_num::cul_para(void){int i;inttemp_nipn=0;for (i=0;i<9;i++)if (num[i]!=target[i])temp_nipn++;not_in_position_num=temp_nipn;if (this->parent==NULL)deapth=0;elsedeapth=this->parent->deapth+1;eva_function=not_in_position_num+deapth; }//构造函数1eight_num::eight_num(intinit_num[9]){for (int i=0;i<9;i++)num[i]=init_num[i];}//显示当前节点的状态voideight_num::show(){cout<<num[0];cout<<" ";cout<<num[1];cout<<" ";cout<<num[2];cout<<"\n";cout<<num[3];cout<<" ";cout<<num[4];cout<<" ";cout<<num[5];cout<<"\n";cout<<num[6];cout<<" ";cout<<num[7];cout<<" ";cout<<num[8];cout<<"\n";}//复制当前节点状态到一个另数组中voideight_num::get_numbers_to(intother_num[9]){for (int i=0;i<9;i++)other_num[i]=num[i];}//设置当前节点状态(欲设置的状态记录的other数组中) voideight_num::set_num(intother_num[9]){for (int i=0;i<9;i++)num[i]=other_num[i];}eight_num&eight_num::operator=(eight_num& another_8num) {for (int i=0;i<9;i++)num[i]=another_8num.num[i];not_in_position_num=another_8num.not_in_position_num;deapth=another_8num.deapth+1;eva_function=not_in_position_num+deapth;return *this;}eight_num&eight_num::operator=(intother_num[9]){for (int i=0;i<9;i++)num[i]=other_num[i];return *this;}inteight_num::operator==(eight_num& another_8num){int match=1;for (int i=0;i<9;i++)if(num[i]!=another_8num.num[i]){match=0;break;}if (match==0)return 0;elsereturn 1;}inteight_num::operator==(intother_num[9]){int match=1;for (int i=0;i<9;i++)if(num[i]!=other_num[i]){match=0;break;}if (match==0)return 0;elsereturn 1;}//class definition over 类定义结束//空格向上移intmove_up(intnum[9]){for (int i=0;i<9;i++)if (num[i]==0)break;if (i<3)return 0;else{num[i]=num[i-3];num[i-3]=0; //两个数互换return 1;}}//空格向下移intmove_down(intnum[9]){for (int i=0;i<9;i++)if (num[i]==0)break;if (i>5)return 0;{num[i]=num[i+3];num[i+3]=0;return 1;}}//空格向左移intmove_left(intnum[9]){for (int i=0;i<9;i++)if (num[i]==0)break;if (i==0||i==3||i==6)return 0;else{num[i]=num[i-1];num[i-1]=0;return 1;}}//空格向右移intmove_right(intnum[9]){for (int i=0;i<9;i++)if (num[i]==0)break;if (i==2||i==5||i==8)return 0;else{num[i]=num[i+1];num[i+1]=0;return 1;}}//判断可否解出inticansolve(intnum[9],int target[9]) {inti,j;intcount_num,count_target;for (i=0;i<9;i++)for (j=0;j<i;j++)if(num[j]<num[i]&&num[j]!=0)count_num++; //求逆序数if(target[j]<target[i]&&target[j]!=0)count_target++;}if((count_num+count_target)%2 == 0)return 1;elsereturn 0;}//判断有无重复int existed(intnum[9],eight_num *where){eight_num *p;for(p=where;p!=NULL;p=p->parent)if(*p==num)return 1; //有重复return 0;}//寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start){eight_num *p,*OK;p=OK=start;int min=start->get_evafun();for(p=start;p!=NULL;p=p->leaf_next)if(min>p->get_evafun()){OK=p;min=p->get_evafun();}return OK;}//主函数开始int main(void){double time;clock_tStart,Finish; //clock_t和int一个类型，只不过要声明start、Finish //为时钟变量，易于理解intmemery_used=0,step=0;intnum[9];int flag=0; //是否输入错误标志，1表示输入错误int bingo=0;//是否查找成功标志，1表示成功inti,j;cout<<"请输入八数码的目标状态(用0表示空格):\n";for (i=0;i<9;i++){flag=0;cin>>target[i];for(j=0;j<i;j++)if(target[i]==target[j]) //判断输入的数是否有重复flag=1;if (target[i]<0||target[i]>8||flag==1){i--;cout<<"输入错误，请关闭并重新输入!\n";}}cout<<"请输入八数码的初始状态(用0表示空格):\n";for (i=0;i<9;i++){flag=0;cin>>num[i];for(j=0;j<i;j++)if(num[i]==num[j]) //判断输入的数是否有重复flag=1;if (num[i]<0||num[i]>8||flag==1){i--;cout<<"输入错误，请关闭并重新输入!\n";}}eight_num S(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();memery_used++;cout<<"现在初始状态为:\n";S.show();cout<<"目标状态为:\n";Target.show();if(!icansolve(num,target)){cout<<"No one can solve it!\n";exit(0);//cin>>i;//return 1;}Start=clock( );eight_num *OK_leaf=&S,*leaf_start=&S,*new_8num,*p; while(OK_leaf!=NULL&&bingo!=1){OK_leaf=find_OK_leaf(leaf_start);if(*OK_leaf==Target){bingo=1; //判断是否达到目标状态break;}p=OK_leaf->leaf_pre;OK_leaf->get_numbers_to(num);if(move_up(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf->get_numbers_to(num);if(move_down(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf->get_numbers_to(num);if(move_left(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf->get_numbers_to(num);if(move_right(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}p->leaf_next=OK_leaf->leaf_next;if(OK_leaf->leaf_next!=NULL)OK_leaf->leaf_next->leaf_pre=p;OK_leaf->leaf_next=OK_leaf->leaf_pre=NULL;}Finish=clock( );if(bingo==1){time = (double)(Finish-Start)*1000/CLOCKS_PER_SEC; //计算时间到mseight_num *p;cout<<"搜索过程为：\n";for (p=OK_leaf->parent;p!=NULL;p=p->parent){cout<<"****************************\n";cout<<" ^\n";p->show();// cout<<"****************************\n";step++;}cout<<"\n搜索所用时间: ";cout<<time;cout<<"ms\n";cout<<"搜索所走的总步数: ";cout<<step;cout<<"\n";}elsecout<<"Fail to find!";return 0;}。

A*算法&SA算法A*算法&SA算法 (1)A*算法 (1)【算法简介】 (1)【算法流程】 (1)【问题描述】 (1)【核心代码】 (2)【实验结果】 (2)【实验思考】 (6)SA算法 (7)【算法简介】 (7)【算法流程】 (7)【问题描述】 (7)【核心代码】 (7)【实验结果】 (8)【实验思考】 (9)附录 (10)【A*算法解决八数码问题代码】 (10)【SA算法解决旅行商问题代码】 (23)A*算法【算法简介】A*搜索算法是对A搜索算法的改进，从而不仅能得到目标解，而且还一定能找到最优解。

当然是问题有节的前提下。

定义最优估价函数f*(n)=g*(n)+h*(n)。

其中n为状态空间图中的一个状态，g*(n)为起点到n状态的最短路径代价值，h*(n)为n状态到目的状态的最短路径的代价值。

这样f*(n)就是从起点出发通过n状态而到达目的状态的最佳路径的总代价。

A*搜索中用个个个g(n)和h(n)作为g*(n)和h*(n)的估计，使其尽量接近，从而提高效率。

【算法流程】•初始化open、closed链表•判断此问题是否有解：无解，则打印信息退出；有解，则继续•Repeatopen表为空→查找失败open表不空，从open表中拿出f min（记为Bestnode）放入closed表若Bestnode是目标结点→成功求解break若Bestnode不是目标结点，产生它的后继→succeed链表对每个后继，Repeat建立此结点到Bestnode的parent指针结点在open表中，将open表中结点加入Bestnode后继结点链，若此结点g值小于open表中结点g值，open表中结点改变parent指针，并删除此点结点在closed表中，将closed表中结点加入Bestnode后继结点链，若此结点g值小于closed表中结点g值，closed表中结点改变parent指针，closed表中结点重新加入open表中，并删除此点open表和closed表中均无此点，将此点加入Bestnode后继结点链，并按一定规则的加入到open表中【问题描述】在一个3*3的方棋盘上放着1,2,3,4,5,6,7,8八个数码，每个数码各占一格，且有一个空格。

人工智能实验一报告题目：采用A*算法解决八数码问题成员：李文、郭弯弯学号：、专业：计算机科学与技术完成日期： 2016/04/09一、实验要求、目的及分工1.1实验要求使用A*算法实现八数码问题，并用图形界面展示。

1.2实验目的a. 熟悉人工智能系统中的问题求解过程；b. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；c. 熟悉对八数码问题的建模、求解及编程语言的应用。

1.3实验分工我们小组共两个人，共同查找背景资料，李文同学主要负责源代码，郭弯弯同学主要负责实验报告以及演示文稿的完成。

二、实验问题2.1问题描述所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8 的八块正方形数码牌任意地放在一块3×3 的数码盘上。

放牌时要求不能重叠。

于是，在3×3 的数码盘上出现了一个空格。

现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。

空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如下图所示：(a) 初始状态 (b) 目标状态图1 八数码问题示意图2.2问题解释首先，八数码问题包括一个初始状态(START) 和目标状态(TRAGET)，所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态：（START>STATE1>STATE2>...>TARGET ）这个状态是否存在就是我们要解决的第一个问题；第二个问题是我们要求出走的路径是什么。

2.3八数码问题形式化描述初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。

把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，即每执行一条规则后总代价加1。

A星⼋数码求解资料讲解A星⼋数码求解实验⼆ A*算法实验I软⼯1303 201326811825 朱镇洋⼀、实验⽬的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利⽤A*算法求解N 数码难题，理解求解流程和搜索顺序。

⼆、实验原理：A*算法是⼀种启发式图搜索算法，其特点在于对估价函数的定义上。

对于⼀般的启发式图搜索，总是选择估价函数f 值最⼩的节点作为扩展节点。

因此，f 是根据需要找到⼀条最⼩代价路径的观点来估算节点的，所以，可考虑每个节点n 的估价函数值为两个分量：从起始节点到节点n 的实际代价以及从节点n 到达⽬标节点的估价代价。

三、实验内容： 1 问题描述。

⼋数码问题:在⼀个3×3的⽅阵中放⼊⼋个数码1、2、3、4、5、6、7、8，其中⼀个单元格是空的。

将任意摆放的数码盘（初始状态）逐步摆成某个指定的数码盘的排列（⽬标状态）：2 设计两种不同的估价函数。

w(n) ；w 表⽰不在⽬标位置的节点数h(n)=d(n)+ ；d(n)表⽰深度p(n) ；p 表⽰所有点到其⽬标节点的步数总和1 2 4 3 5 6782 134 567 8起始状态⽬标状态算法流程图：开始将s 与⽬标序列对⽐结束符合Open 表是否为空Yes读取栈顶元素，并删除堆顶元素No对当前结构扩展，根据空格的位置调整序列并存⼊最⼤堆3 在求解8数码问题的A*算法程序中，设置相同的初始状态和⽬标状态，针对不同的估价函数，求得问题的解令初始状态都为：023415687 ⽬标状态为：123405678通过程序运⾏结果我们可以发现，上述两种估价函数中明显第⼆种在算法效率上更具优势，第⼀种估价函数要通过18步才能到达⽬标状态，通过中间变量记录扩展节点和⽣成节点有1062个：⽽第⼆种估价函数只要16步即可到达⽬标状态，也意味着扩展节点和⽣成节点只有654个，⽐第⼀种少了很多：原因分析：通过实验结果也说明了估计函数对启发式搜索算法的重要影响，因为第⼆种估价函数p(n)是节点与⽬标节点相⽐所需移动次数的总和，与第⼀种估价函数w(n)（只考虑错误位数）相⽐，p(n)不仅考虑了错位信息，还考虑了错位的距离，⽐w(n)更完美，所以它的执⾏效率更⾼。