八数码实验报告(2)

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> …… 此处隐藏：2899字，全部文档内容请下载后查看。喜欢就下载吧 ……