八数码问题C语言A星算法详细实验报告含代码
一、实验内容和要求
八数码问题：在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)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。
3.A*算法的步骤
A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。
A*算法的步骤如下：
1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。
2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。
3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。
4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。
5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。
四、程序框图
五、实验结果及分析
输入初始状态：2 8 3 目标状态：1 2 3
1 6 4 8 0 4
7 0 5 7 6 5
运行结果屏幕打印
OPEN表与CLOSE表：
OPEN CLOSE
1 2 3 4 0
2 3 4 5 6 0 1
2 3 4 6 7 0 1 5
2 3 4 6 8 9 0 1 5 7
2 3 4 8 9 10 0 1 5 7 6
2 3 4 8 11 12 13 0 1 5 7 6 9
2 3 4 8 12 13 14 15 0 1 5 7 6 9 11
3 4 8 12 13 14 15 16 17 0 1 5 7 6 9 11 2
4 8 12 13 14 1
5 1
6 1
7 1
8 1
9 0 1 5 7 6 9 11 2 3
4 8 12 13 14 1
5 1
6 1
7 19 20 0 1 5 7 6 9 11 2 3 18
8 12 13 14 15 16 17 19 21 22 0 1 5 7 6 9 11 2 3 18 4
12 13 14 15 16 17 19 21 22 23 0 1 5 7 6 9 11 2 3 18 4 8
12 13 14 15 16 17 19 21 22 24 25 0 1 5 7 6 9 11 2 3 18 4 8 23
12 13 14 15 16 17 19 21 22 24 26 0 1 5 7 6 9 11 2 3 18 4 8 23 24 发现26为目标节点
六、结论
对于八数码问题，BFS算法最慢，A*算法较快。八数码问题的一个状态实际上是0~9的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列。如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。因此，
可以在运行程序前检查初始状态和目标状态的排序的奇偶行是否相同，相同则问题可解，应当能搜索到路径。否则无解。
七、源程序及注释
#include
#include
#include
using namespace std;
const int ROW = 3;
const int COL = 3;
const int MAXDISTANCE = 10000;
const int MAXNUM = 10000;
int abs(int a)
{
if (a>0) return a;
else return -a;
}
typedef struct _Node{
int digit[ROW][COL];
int dist; // 距离
int dep; // 深度
int index; // 索引值
} Node;
Node src, dest;
vector
bool isEmptyOfOPEN() { //判断Open表是否空
for (int i = 0; i < node_v.size(); i++) {
if (node_v[i].dist != MAXNUM)
return false;
}
return true;
}
bool isEqual(int index, int digit[][COL]) { //判断节点是否与索引值指向的节点相同
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] != digit[i][j])
return false;
}
return true;
}
ostream& operator<<(ostream& os, Node& node) {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++)
os << node.digit[i][j] << ' ';
os << endl;
}
return os;
}
void PrintSteps(int index, vector
index = node_v[index].index;
while (index != 0) {
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
}
for (int i = rstep_v.size() - 1; i >= 0; i--)
cout << "Step " << rstep_v.size() - i
<< endl << rstep_v[i] << endl;
}
void Swap(int& a, int& b) { //交换
int t;
t = a;
a = b;
b = t;
}
void Assign(Node& node, int index) { //获取节点
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
node.digit[i][j] = node_v[index].digit[i][j];
int GetMinNode() { //获取启发值最小的节点
int dist = MAXNUM;
int loc; // the location of minimize node
for (int i = 0; i < node_v.size(); i++) {
if (node_v[i].dist == MAXNUM)
continue;
else if ((node_v[i].dist + node_v[i].dep) < dist) { loc = i;
dist = node_v[i].dist + node_v[i].dep;
}
}
return loc;
}
bool isExpandable(Node& node) { //判断是否可扩展
for (int i = 0; i < node_v.size(); i++) {
if (isEqual(i, node.digit))
return false;
}
return true;
}
int Distance(Node& node, int digit[][COL]) { //计算距离int distance = 0;
bool flag = false;
for(int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
for (int k = 0; k < ROW; k++) {
for (int l = 0; l < COL; l++) {
if (node.digit[i][j] == digit[k][l]) {
distance += abs(i - k) + abs(j - l);
flag = true;
break;
}
else
flag = false;
}
if (flag)
break;
}
return distance;
int MinDistance(int a, int b) { //二者取小
return (a < b ? a : b);
}
void ProcessNode(int index) { //展开节点
int x, y;
bool flag;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] == 0) {
x =i; y = j;
flag = true;
break;
}
else flag = false;
}
if(flag)
break;
}
Node node_up; //上移操作
Assign(node_up, index);
int dist_up = MAXDISTANCE;
if (x > 0) {
Swap(node_up.digit[x][y], node_up.digit[x - 1][y]);
if (isExpandable(node_up)) {
dist_up = Distance(node_up, dest.digit);
node_up.index = index;
node_up.dist = dist_up;
node_up.dep = node_v[index].dep + 1;
node_v.push_back(node_up);
}
}
Node node_down; //下移操作
Assign(node_down, index);
int dist_down = MAXDISTANCE;
if (x < 2) {
Swap(node_down.digit[x][y], node_down.digit[x + 1][y]); if (isExpandable(node_down)) {
dist_down = Distance(node_down, dest.digit);
node_down.index = index;
node_down.dist = dist_down;
node_down.dep = node_v[index].dep + 1;
node_v.push_back(node_down);
}
}
Node node_left;//左移操作
Assign(node_left, index);
int dist_left = MAXDISTANCE;
if (y > 0) {
Swap(node_left.digit[x][y], node_left.digit[x][y - 1]); if (isExpandable(node_left)) {
dist_left = Distance(node_left, dest.digit);
node_left.index = index;
node_left.dist = dist_left;
node_left.dep = node_v[index].dep + 1;
node_v.push_back(node_left);
}
}
Node node_right; //右移操作
Assign(node_right, index);
int dist_right = MAXDISTANCE;
if (y < 2) {
Swap(node_right.digit[x][y], node_right.digit[x][y + 1]); if (isExpandable(node_right)) {
dist_right = Distance(node_right, dest.digit);
node_right.index = index;
node_right.dist = dist_right;
node_right.dep = node_v[index].dep + 1;
node_v.push_back(node_right);
}
}
node_v[index].dist = MAXNUM;
}
int main() {
int number;
cout << "输入初始状态:" << endl;
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++) {
cin >> number;
src.digit[i][j] = number;
}
src.index = 0;
src.dep = 1;
cout << "输入目标状态" << endl;
for (int m = 0; m < ROW; m++)
for (int n = 0; n < COL; n++) {
cin >> number;
dest.digit[m][n] = number;
}
node_v.push_back(src);
while (1) {
if (isEmptyOfOPEN()) {
cout << "找不到解!" << endl;
return -1;
}
else {
int loc; // the location of the minimize node loc = GetMinNode();
if(isEqual(loc, dest.digit)) {
vector
cout << "初始状态：" << endl;
cout << src << endl;
PrintSteps(loc, rstep_v);
cout << "成功!" << endl;
break;
}
else
ProcessNode(loc);
}
}
return 0;
}
大一上期C语言实验报告1熟悉实验环境
成都工业学院·计算机工程学院 《程序设计基础》实验报告 1.实验目的 （1）熟悉C语言运行环境，了解和使用Visual6.0++集成开发环境（2）熟悉Visual6.0++环境的功能键和常用的功能菜单命令 （3）掌握C语言程序的书写格式和C语言程序的结构 （4）掌握C语言上机步骤，以及编辑、编译和运行一个C语言程序的方法 （5）熟悉Visual6.0++环境下的程序调试方法 2.实验内容 （1）按照实验步骤编辑、编译、运行第一个”Hello World”程序（2）利用实验指导中的第二个程序熟悉调试工具,在已知x，y值的情况下，计算出x和y的和、差、积、商，并显示出来（3）编写一个程序，输入a、b、c三个值，输出它们的和与平均值c 3.源程序 （1）#include
（3）#include
用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表的估价值 ) {把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值} } if(X not inboth) {把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //还没有排序}
C语言实验报告参考答案 原
C语言实验报告参考答案 实验一熟悉C语言程序开发环境及数据描述 四、程序清单 1．编写程序实现在屏幕上显示以下结果： The dress is long The shoes are big The trousers are black 答案： #include
int a,b,c,x,y; a=150; b=20; c=45; x=a/b; y=a/c; printf("a/b的商=%d\n",x); printf("a/c的商=%d\n",y); x=a%b; y=a%c; printf("a/b的余数=%d\n",x); printf("a/c的余数=%d\n",y); } （2） #include
d=170; x=(a+b)/(b-c)*(c-d); printf("(a+b)/(b-c)*(c-d)=%f\n",x); } 3. 设变量a的值为0，b的值为-10，编写程序：当a>b时，将b赋给c；当a<=b 时，将0赋给c。(提示：用条件运算符) 答案： #include
用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表的估价值 )
C语言实验报告参考答案
长沙理工大学2010C语言实验报告参考答案 实验一熟悉C语言程序开发环境及数据描述 四、程序清单 1．编写程序实现在屏幕上显示以下结果： The dress is long The shoes are big The trousers are black 答案： #include<> main() { printf("The dress is long\n"); printf("The shoes are big\n"); printf("The trousers are black\n"); } 2．改错题（将正确程序写在指定位置） 正确的程序为： #include <> main() { printf("商品名称价格\n"); printf("TCL电视机￥7600\n"); printf("美的空调￥2000\n"); printf("SunRose键盘￥\n"); } 2．编写程序： a=150,b=20,c=45,编写求a/b、a/c(商)和a%b、a%c(余数)的程序。 答案： #include<> main() { int a,b,c,x,y; a=150; b=20; c=45;
x=a/b; y=a/c; printf("a/b的商=%d\n",x); printf("a/c的商=%d\n",y); x=a%b; y=a%c; printf("a/b的余数=%d\n",x); printf("a/c的余数=%d\n",y); } 4. 设变量a的值为0，b的值为-10，编写程序：当a>b时，将b赋给c；当a<=b时，将a赋给c。(提示：用条件运算符) 答案： #include<> main() { int a,b,c; a=0; b=-10; c= (a>b) ? b:a; printf("c = %d\n",c); } 五、调试和测试结果 1.编译、连接无错，运行后屏幕上显示以下结果： The dress is long The shoes are big The trousers are black 3、编译、连接无错，运行后屏幕上显示以下结果： a/b的商=7 a/c的商=3 a/b的余数=10 a/c的余数=15 4. 编译、连接无错，运行后屏幕上显示以下结果： c =-10 实验二顺序结构程序设计 四、程序清单 1．键盘输入与屏幕输出练习 问题1 D 。 问题2 改printf("%c,%c,%d\n",a,b,c);这条语句
八数码问题求解--实验报告讲解
实验报告 一、实验问题 八数码问题求解 二、实验软件 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）所示。
2010C语言实验报告参考答案
2010C语言实验报告参考答案
长沙理工大学2010C语言实验报告参考答案 实验一熟悉C语言程序开发环境及数据描述四、程序清单 1．编写程序实现在屏幕上显示以下结果： The dress is long The shoes are big The trousers are black 答案： #include
printf("商品名称价格\n"); printf("TCL电视机￥7600\n"); printf("美的空调￥2000\n"); printf("SunRose键盘￥50.5\n"); } 2．编写程序： a=150,b=20,c=45,编写求a/b、a/c(商)和a%b、a%c(余数)的程序。 答案： #include
x=a%b; y=a%c; printf("a/b的余数=%d\n",x); printf("a/c的余数=%d\n",y); } 4. 设变量a的值为0，b的值为-10，编写程序：当a>b时，将b赋给c；当a<=b时，将a赋给c。(提示：用条件运算符) 答案： #include
启发式搜索算法解决八数码问题(C语言)
1、程序源代码 #include
哈工大(威海)c语言实验报告册答案
实验1简单判定性问题求解 一、实验学时 完成本实验需4学时。 二、实验目的 1、阅读程序题 （1）掌握C语言数据类型，熟悉如何定义一个整型、字符型的变量，以及对它们赋值的方法； （2）掌握不同的类型数据之间赋值的规律； （3）掌握数据在内存中的存储方式； （4）学会输入、输出函数的基本格式和使用方法； （5）学会使用有关算术运算符、逻辑运算符、关系运算符，以及包含这些运算符的表达式。 2、编程题 （1）如何运用if-else判定性结构进行程序设计； （2）如何运用switch判定性结构进行程序设计。 3、调试题 （1）熟悉C程序的编辑、编译、连接和运行的过程。 三、实验指导 为了达到最佳的实验效果，以下提供几条适于编程的指导意见，可供参考。 1、阅读程序题应先运用自己在课堂所学的知识，推导出结果，在上机时输入计算机，印证自己推导的结果，注意观察数据在内存中的存储方式、含不同种运算符表达式的输出结果。 2、编程题必须首先画出流程图，并反复思考判断程序设计的正确性，完成程序的设计。要注意简单判定性问题的结构选择。 3、调试题应明确程序的调试、测试是一项非常烦琐的工作，也是非常重要的工作。对于初学者来说应该建立良好的习惯，在调试程序的时候，应该尽可能考虑到程序运行时各种可能情况。
四、实验内容 1、阅读程序题 （1）main( ) { /*定义字符型变量*/ char c1,c2; /*向字符变量赋以整数*/ c1=97; c2=98; printf("%c %c\n",c1,c2); /*以字符形式输出*/ printf("%d %d\n",c1,c2); /*以整数形式输出*/ } 思考：可否改成int c1，c2；输出结果是？相同 （2）main() { int a=7,b=5; printf("%d\n",b=b/a); } 思考：若将printf语句中%d变为%f，可否输出分式的值？可以（3）main() { int a=9; a+=a-=a+a; /*包含复合的赋值运算符的赋值表达式*/ printf("%d\n",a); } 思考：赋值表达式a＋＝a－＝a＋a的求解步骤？ 第一步：a=a-(a+a)=-9 第二步a=a+a=18 （4）main() { int k=-1; printf("%d,%u\n",k,k);
实验三A星算法求解8数码问题实验讲解
实验三：A*算法求解8数码问题实验 一、实验目的 熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。 二、实验内容 1、八数码问题描述 所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8，其中一个单元格是空的。将任意摆放的数码盘（城初始状态）逐步摆成某个指定的数码盘的排列（目标状态）， 如图1所示 图1 八数码问题的某个初始状态和目标状态 对于以上问题，我们可以把数码的移动等效城空格的移动。如图1的
初始排列，数码7右移等于空格左移。那么对于每一个排列，可能的一次数码移动最多只有4中，即空格左移、空格右移、空格上移、空格下移。最少有两种（当空格位于方阵的4个角时）。所以，问题1 就转换成如何从初始状态开始，使空格经过最小的移动次数最后排列成目标状态。 2、八数码问题的求解算法 2.1 盲目搜索 宽度优先搜索算法、深度优先搜索算法 2.2 启发式搜索 启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。 先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。
C语言实验报告参考源代码
实验5三种基本结构的综合应用 4．一个素数（设为p）依次从最高位去掉一位，二位，三位，……，若得到的各数仍都是素数(注：除1和它本身外，不能被其它整数整除的正整数称为素数，1不是素数，2是素数），且数p的各位数字均不为零，则称该数p为逆向超级素数。例如，617，17，7都是素数，因此617是逆向超级素数，尽管503，03，3都是素数，但它不是逆向超级素数，因为它包含有零。试求[100,999]之内的所有逆向超级素数的个数。 #include "stdio.h" main() {int i,j,k,m,p,q,n=0; for(i=100;i<=999;i++) {for(j=2;j A*算法求解八数码问题 1、八数码问题描述 所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、 6、7、8，其中一个单元格是空的。将任意摆放的数码盘（城初始状态）逐步摆成某个 指定的数码盘的排列（目标状态），如图1所示 图1 八数码问题的某个初始状态和目标状态 对于以上问题，我们可以把数码的移动等效城空格的移动。如图1的初始排列，数码7右移等于空格左移。那么对于每一个排列，可能的一次数码移动最多只有4中，即空格左移、空格右移、空格上移、空格下移。最少有两种（当空格位于方阵的4个角时）。所以，问题就转换成如何从初始状态开始，使空格经过最小的移动次数最后排列成目标状态。 2、八数码问题的求解算法 2.1 盲目搜索 宽度优先搜索算法、深度优先搜索算法 2.2 启发式搜索 启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。 先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g 的最短路径的耗散值。 评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x， h(x)<=h*(x) (3) 成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。 针对八数码问题启发函数设计如下： f(n)=d(n)+p(n) (4) 其中A*算法中的g(n)根据具体情况设计为d(n)，意为n节点的深度，而h(n)设计为 人工智能实验一报告题目：采用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 - 《C语言程序设计》 实 验 手 册 《C语言程序设计》实验课程简介 课程名称：C语言程序设计实验 课程性质：专业必修课 课程属性：专业必修课 学时学分：学时32 学分1 开课实验室：软件实验室 面向专业：网络工程、软件工程、计算机科学与技术 一、课程的任务和基本要求 C语言程序设计实验是面向计算机相关专业学生开设的《C语言程序设计》实验课，是配合《C语言程序设计》课程而开设的实验性教育环节。本课程的主要任务是让学生充分掌握C 语言程序设计的基本概念、各种数据类型的使用技巧、模块化程序设计的方法等。C语言程序设计实验对课程中所涉及的知识进行验证，同时也是学生很好地学习课程的辅助手段。通过C语言上机实验的教学活动，使学生真正全面掌握C语言的基础知识，培养和提高学生的程序开发能力。 二、实验项目 【实验一】最简单的C程序---顺序程序设计 【实验二】逻辑运算和判断选取控制 【实验三】循环结构程序设计（一） 【实验四】循环结构程序设计（二） 【实验五】函数 【实验六】数组（一） 【实验七】数组（二） 【实验八】指针 【实验九】结构体、共用体和文件 【实验十】C程序综合性实验 三、有关说明 1、与其它课程和教学环节的联系： 先修课程：计算机文化 后续课程：面向对象程序设计、Java程序设计、数据结构、软件工程 2、教材和主要参考书目： （1）教材： 《C程序设计习题解答与上机指导》，谭浩强吴伟民著，北京：清华大学出版社，2003年。（2）主要参考书目： 《C语言程序设计》谭浩强主编，清华大学出版社，2003年。 三、实验内容 实验一最简单的C程序---顺序程序设计 （验证性实验 2学时） （一）、实验目的 1．熟悉win-tc程序运行环境 2．掌握运行一个C程序的步骤，理解并学会C程序的编辑、编译、链接方法 3．掌握C语言中使用最多的一种语句——赋值语句 4．掌握数据的输入输出方法，能正确使用各种格式控制符 （二）、实验内容 1．写出下列程序的运行结果 （1）#include #include 二、编程题(参考答案) 1、 #include “stdio.h” void main() { int Math=82,eng=78,comp=91,average; average=(Math+eng+comp)/3; printf(“Math=%d,eng=%d,comp=%d,average=%d\n”,Math,eng,comp,average); } 2、 #include “stdio.h” void main() { int n=152,d1,d2,d3; d1=n%10; d2=(n/10)%10; d3=n/100; printf(“整数%d的个位数字是%d，十位数字是%d，百位数字是%d\n”,n,d1,d2,d3); } 3、 #include “stdio.h” void main() { int n1,n2; printf(“Enter n1,n2：”); scanf(“%d,%d”,&n1,&n2); printf(“%d+%d=%d\n”,n1,n2,n1+n2); printf(“%d/%d=%d\n”,n1,n2,n1/n2); printf(“%d%%%d=%d\n”,n1,n2,n1%n2); } 三、改错题 原错误行（共三行）： /********************************** found ********************************/ #include “stdoi,h” /********************************** found ********************************/ printf(“%d=%d*%d\n”,x); /********************************** found ********************************/ printf(“%d*%d=%d\n”,y); 改正后： #include “stdio.h” printf(“%d=%d*%d\n”,y,x,x); printf(“%d*%d=%d\n”,x,x,y); 《八数码问题》实验报告 一、实验目的： 熟练掌握启发式搜索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）算法流程图： 学生实验报告册 （理工类） 课程名称：C语言程序设计实验专业班级： 15自动化 2班 学生学号： 1517011063 学生姓名：王启涛所属院部：智能科学与控制工程学院指导教师：王预2015——20 16学年第 2 学期 金陵科技学院教务处制 实验报告书写要求 实验报告上交电子稿，标题采用四号黑体，正文采用小四号宋体，单倍行距。 实验报告书写说明 实验报告中实验目的和要求、实验仪器和设备、实验内容与过程、实验结果与分析这四项内容为必需项。教师可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。 （2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。 （5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用五级记分制或百分制，按《金陵科技学院课堂教学实施细则》中作业批阅成绩评定要求执行。 实验项目名称：初级程序设计实验学时： 6 实验地点：工科楼 实验日期： 2016.3.29 实验成绩： 批改教师：王预批改时间： 实验1 初级程序设计 一、实验目的和要求 （1）熟悉Visual C++集成环境，进行编辑、保存、编译、连接及运行，并能进行简单程序调试； （2）掌握C语言中各种运算符的使用； （3）掌握C语言中各种数据类型的区别与应用； （4）熟练掌握C语言中变量的定义、赋值和使用，表达式语句、输入/输出语句的使用； （5）掌握C语言中输入/输出函数的使用； （6）掌握C语言中控制语句的使用，含if-else、for、while、do-while语句的使用。 二、实验仪器和设备 奔腾以上计算机，装有windows XP以上版本操作系统和Visual C++ 6.0软件。 三、实验内容与过程 1、程序调试 （1）#include A星算法求解八数码问题
采用A算法解决八数码问题
C语言实验报告参考答案
八数码C语言A算法详细代码
C语言实验报告答案
八数码问题实验报告讲解
C语言实验报告册_2016.3a
- C语言实验报告(答案)
- 2010C语言实验报告参考答案
- (实验报告)C语言程序设计实验报告
- C语言实验报告参考答案(原)
- (最新版)C语言实验报告(答案)
- c语言实验报告册答案
- C语言实验报告22
- C语言实验报告参考答案原
- C语言实验报告1.pptx
- C语言实验报告第3章答案
- 大学大一C语言程序设计实验室上机题全部代码答案(实验报告)
- C语言实验报告参考答案
- C语言实验报告参考答案原
- 湖北理工学院c语言实验报告六答案(完整版)
- C语言实验报告参考答案
- 郑州大学c语言实验报告册答案(全部)
- 大学一年级下学期C语言程序设计实验报告答案完整版
- C语言实验报告参考源代码
- C语言实验报告(答案)
- C语言实验报告参考答案完整版