for(j=0;j<n;j++){ } if(node->board.pos[i][j]==0){ } zr[0]=i+1; zr[1]=j+1; break;
int wrong(lnode *node) { }
int pick(lnode *node) { int w=0,i,j,ii,jj; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(node->board.pos[i][
j]!=goal[i][j]&&node->board.pos[i][j]!=0){ for(ii=0;ii<n;ii++) for(jj=0;jj<n;jj++)
if(node->board.pos[i][j]==goal[ii][jj]){ w=w+abs(ii-i)+abs(jj-j); break; int w=0,i,j; for(i=0;i<n;i++){ } return w; for(j=0;j<n;j++){ } if(node->board.pos[i][j]!=goal[i][j]&&node->board.pos[i][j]!=0)
w++;篇三：八数码实验报告53 华 中 师 范 大 学 计 算 机 学 院 实 验 报 告 书 实验题目 ：
八数码问题求解 课程名称 ： 人工智能 主讲教师 ： 金聪 班 级 ： 试验时间 ： 1.问题描述： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格
相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状
态的移动棋子步数最少的移动步骤。 2.初始状态 1 0 3 7 2 4 6 8 5 3.目标状态 1 2 3, 8 0 4, 7 6 5 4.搜索策略 启发式搜索技术
（1） 原理：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估， 得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
（2） 估价函数
计算一个节点的估价函数，可以分成两个部分： 1、 已经付出的代价（起始节点到当前节点）； 2、 将要付出的代价（当前节点到目标节点）。 节点n的估价函数f(n)定义为从初始节点、经过n、到达目标节点的路径的最小代价的
估计值，即f(n) = g(n)+ h(n)。 *** g*(n)是从初始节点到达当前节点n的实际代价； 体现出搜索过程中采用的启发式信h*(n)是从节点n到目标节点的最佳路径的估计代价，
息（背景知识），称之为启发函数。 g*(n)所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h*(n)的比重越大，表示启发性能就越强。 本实验中我们使用函数p(n)，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然p(n)比?(n)
更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离。 5.算法 begin：
读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； if(问题可解)
把初始状态假如open表中； while（未找到解&&状态表非空） ①在open表中找到评价值最小的节点，作为当前结点； ②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③； ③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结
点的评价值f并记录其父节点； ④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中； ⑤把
当前结点从open表中移除； end while end if 输出结果； end
6.源代码
#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define overflow 1 #define n 3
int goal[n][n]={1,2,3,8,0,4,7,6,5}; int zero[2],nodeqty=0;
int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列 typedef int piece;
struct chessboard{//棋盘信息 piece pos[n][n];//记录每个数码a的位置r行c列 int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该节点的方式 }; struct lnode{ chessboard board; lnode *parent,*next; bool flag; };
typedef lnode* list;
int* findzero(lnode* &node) {
int i,j,zr[2]; int *z=zr;
for(i=0;i<n;i++){ for(j=0;j<n;j++){
if(node->board.pos[i][j]==0){ zr[0]=i+1; zr[1]=j+1; break; }
} }
return z;
} int pick(lnode *node) {
int w=0,i,j,ii,jj; for(i=0;i<n;i++){ for(j=0;j<n;j++){
if(node->board.pos[i][j]!=goal[i][j]&&node->board.pos[i][j]!=0){
for(ii=0;ii<n;ii++) for(jj=0;jj<n;jj++)
if(node->board.pos[i][j]==goal[ii][jj]){ w=w+abs(ii-i)+abs(jj-j); break; } } } }
return w; }
lnode* extend(lnode *node,int depth,int zero[2],int moveflag,int choose) { lnode* newnode=new lnode; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ newnode->board.pos[i][j]=node->board.pos[i][j]; } }
switch(moveflag) {
case 1: //向左移，不能出界：zero[1]>=2
newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]-1][zero
[1]-2];
newnode->board.pos[zero[0]-1][zero[1]-2]=0; break;
case 2: //向右移，不能出界：zero[1]<=2
newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]-1][zero
[1]];
newnode->board.pos[zero[0]-1][zero[1]]=0; break; case 3: //向上移，不能出界：zero[0]>=2
newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]-2][zero
[1]-1];
newnode->board.pos[zero[0]-2][zero[1]-1]=0; break;
case 4: //向下移，不能出界：zero[0]<=2
newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]][zero[1]-1];
newnode->board.pos[zero[0]][zero[1]-1]=0; break; }
newnode->board.d=depth+1; switch(choose){
case 1:newnode->board.f=newnode->board.d+pick(newnode);break; } newnode->board.move=moveflag; newnode->parent=node; nodeqty++;
return newnode; }
void initlist(lnode* &open,lnode* &close) {
open=(list)malloc(sizeof(lnode)); close=(list)malloc(sizeof(lnode)); if(!open&&!close) exit(overflow); open->next=null; close->next=null; }
int listinsert(list &l,lnode* newnode) {
list p=l;
while(p->next){ p=p->next; }
newnode->next=p->next; p->next=newnode; return true; }
lnode* getminf(list &l) {篇四：人工智能大作业八数码问题 基于a星算法的八数码问题求解 学号： 姓名： 摘要：在人工智能领域中, 八数码问题一直都是一个游戏难题。介绍了八数码问题, 然后在启发式搜 索算法上对a * 算法定义进行了解释, 并在其旨在提高搜索效率的方面作了比较详尽的介绍,
详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法： a* 算法。再依据这种
算法用可视化编程语言vc+ + 6. 0 来实现八数码问题的求解过程, 取得了预期的搜索解, 提
高了搜索效率。
关键词：八数码问题; 启发式搜索; a* 算法 本组成员： 本人分工：主要负责进行问题分析，提出解决方案，进行系统设计，算法上具体负责主
函数的编写。 1 引言
八数码问题是人工智能的一个经典的问题。文中通过设计一个基于a* 算法的状态空间搜索程
序, 对于给定的初始状态, 采用h ( n ) = p ( n ) 表示以每一个将牌与目标位置之间距离的总和
作为启发函数的度量, 并用可视化编程语言vc+ + 来实现该问题。 2 算法原理与系统设计 1）a*算法思想 a*算法是对a算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。a*
算法对a算法中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)>0； 第二，h(n)是最小代价h*(n)的下界，即对任意节点n 均有h(n)≤h*(n)。即满足上述两条限制的a算
法称为a*算法。 2）估价函数 用来估算节点希望程度的量度，叫估价函数f(x)，f(x)=g(x)+h(x)。g(x)为从初始节点到当前节点 已经付出的代价，h(x)为从当前节点到目标节点的最优路径的估计代价。本算法中令g(x)为当前节点