八数码问题求解--实验报告讲解-共16页

A星算法求八数码问题实验报告人工智能实验报告实验名称：八数码问题姓名：xx学号：2012210xxxx计算机学院2014年1月14日一．实验目的掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。

二．实验内容给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(2 8 31 6 47 0 52 8 31 6 47 0 5三、A*算法思想：1、思想：A*算法是一种静态路网中求解最短路最有效的直接搜索方法。

估价值与实际值越接近，估价函数取得就越好2、原理：估价函数公式表示为： f(n)=g(n)+h(n),其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。

如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

四、算法流程：Heuristic_Search(启发式搜索)While是从未拓展表中删N为目是，输出路径否，生成n的所有子状态Case:此子状Case:此子状Case:此子状计算该子状记录比已有记录比已有返回五、关键技术：1、使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。

关键代码：bool CreateChild(NOExtend ns[],NOExtend ne){int i,j,k=0;for(i=0;i<3;i++){for(j=0;j<3;j++){if(ne.cur_sudoku.num[i][j]==0){ //寻找九宫格空缺所在的坐标if(i-1>=0){ //将空格向上移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudo ku);//先把未改变的九宫格复制给九宫格数组的某一元素ns[k].cur_sudoku.num[i][j]=ne.cur_sudoku.num[i-1][j];//然后仅改变此二维九宫格的两项值即可ns[k].cur_sudoku.num[i-1][j]=0;ns[k].dx=1;k++;}if(j+1<=2){ //将空格向右移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudo ku);ns[k].cur_sudoku.num[i][j]=ns[k].cur_su doku.num[i][j+1];ns[k].cur_sudoku.num[i][j+1]=0;ns[k].dx=1;k++;}if(i+1<=2){ //将空格向下移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudo ku);ns[k].cur_sudoku.num[i][j]=ns[k].cur_su doku.num[i+1][j];ns[k].cur_sudoku.num[i+1][j]=0;ns[k].dx=1;k++;}if(j-1>=0){ //将空格向左移动CopySudoku(ns[k].cur_sudoku,ne.cur_sudo ku);ns[k].cur_sudoku.num[i][j]=ns[k].cur_su doku.num[i][j-1];ns[k].cur_sudoku.num[i][j-1]=0;ns[k].dx=1;k++;}return 1;}}}return 0;2、用启发式搜索函数寻找求解路径，运用了A*算法的思想，能够更快的求解出最优解。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==八数码实验报告篇一：八数码实验报告利用人工智能技术解决八数码游戏问题1．八数码游戏问题简介九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。

问题是在3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。

问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。

2．八数码游戏问题的状态空间法表示①建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中②建立CLOSED表，且置为空表③判断OPEN表是否为空表，若为空，则问题无解，退出④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。

问题的解就是沿着n到S0的路径得到。

若不是转⑥⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M 中的这些节点作为n的后继节点加入图G中⑦对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点, 设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。

⑧ 按某一任意方式或某种策略重排OPEN表中节点的顺序⑨ 转③3．八数码游戏问题的盲目搜索技术宽度优先搜索：1、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。

2、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

3、宽度优先搜索算法(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。

八数码问题实验报告八数码问题实验报告引言：八数码问题是一种经典的数学难题，在计算机科学领域有着广泛的研究和应用。

本实验旨在通过探索八数码问题的解法，深入理解该问题的本质，并通过实验结果评估不同算法的效率和准确性。

一、问题描述：八数码问题是一个在3×3的棋盘上，由1至8的数字和一个空格组成的拼图问题。

目标是通过移动棋盘上的数字，使得棋盘上的数字排列按照从小到大的顺序排列，最终形成如下的目标状态：1 2 34 5 67 8二、解法探索：1. 深度优先搜索算法：深度优先搜索算法是一种经典的解决拼图问题的方法。

该算法通过不断尝试所有可能的移动方式，直到找到目标状态或者无法再继续移动为止。

实验结果显示，该算法在八数码问题中能够找到解，但由于搜索空间庞大，算法的时间复杂度较高。

2. 广度优先搜索算法：广度优先搜索算法是另一种常用的解决八数码问题的方法。

该算法通过逐层扩展搜索树，从初始状态开始，逐步扩展所有可能的状态，直到找到目标状态。

实验结果显示，该算法能够找到最短路径的解，但同样面临搜索空间庞大的问题。

3. A*算法：A*算法是一种启发式搜索算法，结合了深度优先搜索和广度优先搜索的优点。

该算法通过使用一个估价函数来评估每个搜索状态的优劣，并选择最有希望的状态进行扩展。

实验结果显示，A*算法在八数码问题中表现出色，能够高效地找到最优解。

三、实验结果与分析：通过对深度优先搜索、广度优先搜索和A*算法的实验，得出以下结论：1. 深度优先搜索算法虽然能够找到解，但由于搜索空间庞大，时间复杂度较高，不适用于大规模的八数码问题。

2. 广度优先搜索算法能够找到最短路径的解，但同样面临搜索空间庞大的问题，对于大规模问题效率较低。

3. A*算法在八数码问题中表现出色，通过合理的估价函数能够高效地找到最优解，对于大规模问题具有较好的效果。

四、结论与展望：本实验通过对八数码问题的解法探索，深入理解了该问题的本质，并评估了不同算法的效率和准确性。

八数码实验报告八数码实验报告引言：八数码，也称为滑块拼图，是一种经典的数字游戏。

在这个游戏中，玩家需要通过移动数字方块，将它们按照从小到大的顺序排列。

本次实验旨在通过编写八数码游戏的程序，探索并实践算法设计与实现的过程。

实验过程：1. 游戏规则设计在开始编写程序之前，首先需要明确游戏的规则。

八数码游戏的规则如下：- 有一个3x3的方格，其中有8个方块分别带有数字1到8，还有一个空白方块。

- 玩家可以通过移动数字方块，将它们按照从小到大的顺序排列。

- 移动的方式是将数字方块与空白方块进行交换，只能上下左右移动。

2. 程序设计基于以上规则，我们开始设计程序。

首先，我们需要实现游戏界面的显示与交互。

通过使用图形界面库，我们可以方便地创建一个可视化的游戏界面。

在界面中，每个数字方块都是一个可交互的按钮，玩家可以通过点击按钮来移动数字方块。

接下来，我们需要实现游戏逻辑的处理。

当玩家点击一个数字方块时，程序需要判断该方块是否与空白方块相邻，如果相邻，则进行交换。

同时，程序还需要判断玩家是否已经成功完成了游戏，即数字方块是否已经按照从小到大的顺序排列。

为了实现这些功能，我们可以使用算法来进行判断和计算。

例如，可以通过遍历每个方块，检查其周围是否有空白方块，从而确定是否可以进行移动。

另外，可以使用排序算法来判断数字方块是否已经按照顺序排列。

3. 算法实现在实现算法时，我们可以选择不同的方法。

例如，可以使用深度优先搜索算法来寻找解决方案。

深度优先搜索算法通过递归地尝试每一种移动方式，直到找到一个可行的解决方案。

另外，还可以使用启发式搜索算法，如A*算法，来提高搜索效率。

在本次实验中，我们选择使用A*算法来解决八数码问题。

A*算法通过估计每个状态与目标状态的距离，选择最有可能导致解决方案的移动方式。

通过使用合适的启发函数，A*算法可以在较短的时间内找到一个最优解。

4. 实验结果经过程序的编写和测试，我们成功地实现了八数码游戏。

八数码实验报告八数码实验报告引言：八数码，也被称为滑块拼图，是一种经典的益智游戏。

在这个实验中，我们将探索八数码问题的解决方案，并分析其算法的效率和复杂性。

通过这个实验，我们可以深入了解搜索算法在解决问题中的应用，并且探讨不同算法之间的优劣势。

1. 问题描述：八数码问题是一个在3x3的方格上进行的拼图游戏。

方格中有8个方块，分别标有1到8的数字，还有一个空方块。

游戏的目标是通过移动方块，将它们按照从左上角到右下角的顺序排列。

2. 算法一：深度优先搜索（DFS）深度优先搜索是一种经典的搜索算法，它从初始状态开始，不断地向前搜索，直到找到目标状态或者无法继续搜索为止。

在八数码问题中，深度优先搜索会尝试所有可能的移动方式，直到找到解决方案。

然而，深度优先搜索在解决八数码问题时存在一些问题。

由于搜索的深度可能非常大，算法可能会陷入无限循环，或者需要很长时间才能找到解决方案。

因此，在实际应用中，深度优先搜索并不是最优的选择。

3. 算法二：广度优先搜索（BFS）广度优先搜索是另一种常用的搜索算法，它从初始状态开始，逐层地向前搜索，直到找到目标状态。

在八数码问题中，广度优先搜索会先尝试所有可能的一步移动，然后再尝试两步移动，依此类推，直到找到解决方案。

与深度优先搜索相比，广度优先搜索可以保证找到最短路径的解决方案。

然而，广度优先搜索的时间复杂度较高，尤其是在搜索空间较大时。

因此，在实际应用中，广度优先搜索可能不太适合解决八数码问题。

4. 算法三：A*算法A*算法是一种启发式搜索算法，它在搜索过程中利用了问题的启发信息，以提高搜索效率。

在八数码问题中，A*算法会根据每个状态与目标状态之间的差异，选择最有可能的移动方式。

A*算法通过综合考虑每个状态的实际代价和启发式估计值，来评估搜索路径的优劣。

通过选择最优的路径，A*算法可以在较短的时间内找到解决方案。

然而，A*算法的实现较为复杂，需要合适的启发函数和数据结构。

八数码实验报告实验名称：八数码实验目的：通过使用搜索算法和启发式算法，解决八数码问题，深入理解搜索算法原理和应用。

实验环境：使用Python语言进行编程实现，操作系统为Windows。

实验过程：1. 定义八数码问题的状态和目标状态，分别以列表的形式表示。

* 初始状态：[2, 8, 3, 1, 6, 4, 7, 0, 5]* 目标状态：[1, 2, 3, 8, 0, 4, 7, 6, 5]2. 实现深度优先搜索算法，运行程序得到结果。

通过深度优先搜索算法，得到了八数码问题的解法。

但是，由于深度优先搜索算法过于盲目，搜索时间过长，而且容易陷入无解状态，因此需要改进算法。

3. 改进算法——广度优先搜索。

在深度优先搜索的基础上，改用广度优先搜索算法，实现代码如下：```def bfs(start, target):queue = [(start, [start])]seen = {tuple(start)}while queue:node, path = queue.pop(0)for move, i in direction.items():new_node = [j for j in node]if i not in range(0, 9):continuenew_node[0], new_node[i] = new_node[i], new_node[0] if tuple(new_node) in seen:continueif new_node == target:return path + [new_node]seen.add(tuple(new_node))queue.append((new_node, path + [new_node]))```4. 改进算法——A*算法。

在广度优先搜索的基础上，使用A*算法进行优化。

进行了以下改进：* 引入估价函数，加快搜索速度；* 遍历过程中对结点进行评估，保留最优的结点。

把数码问题就是把一串数字变为下边这个样子:1 2 38 0 47 6 5实现方法1.过程表示源代码：#include<stdio.h>static int style[9]={1,2,3,6,7,4,5,8,0};//输入的数码//2,5,4,3,0,7,1,8,63,2,1,8,0,4,7,6,5 1,0,4,2,7,3,8,5,61,0,3,8,2,4,7,6,5static int arrayStep41[6]={5,4,3,6,7,8};//第四步和第六步共用的数组，所以设为全局量static int arrayStep71[4]={3,6,7,4};static int local;// 空格的地点int i,j;// 所用到的变量int number=0;// 记录挪动步数void print();void step1();void step2();void step3();void step4();void step5();void step6();void step7();void step8();void step9();void exchange(int x,int y);void judge();void judge()// 判断空格地点{number = 0;for(i=0;i<9;i++){if(style[i]==0){local=i;return;}}}void exchange(int x,int y)// 互换两个数{int temp;print();temp=style[x];style[x]=style[y];style[y]=temp;local=y;number++;}void step1(){int arrayStep11[5]={3,0,1,2,5};int arrayStep12[6]={6,7,8,5,2,1};if((style[2]!=0)&&style[2]!=1)return;else{if(local==2){if(style[1]==1)exchange(2,5);elseexchange(2,1);return;}else{if(local==4){exchange(4,1);i=2;while(local!=5){exchange(arrayStep11[i],arrayStep11[i+1]);i++;}return;}for(i=0;i<3;i++){if(arrayStep11[i]==local){while(local!=5){exchange(arrayStep11[i],arrayStep11[i+1]);i++;}return;}}for(i=0;i<4;i++){if(arrayStep12[i]==local){while(local!=1){exchange(arrayStep12[i],arrayStep12[i+1]);i++;}return;}}}}return;}void step2(){int arrayStep21[8]={0,3,6,7,8,5,4,1};for(i=0;i<8;i++){if(arrayStep21[i]==local){while(style[0]!=1){exchange(arrayStep21[i%8],arrayStep21[(i+1)%8]);i++;}break;}}}void step3(){int arrayStep31[8]={2,1,4,3,6,7,8,5};for(i=0;i<8;i++){if(arrayStep31[i]==local){while(style[1]!=2){exchange(arrayStep31[i%8],arrayStep31[(i+1)%8]);i++;}break;}}}void step4(){for(i=0;i<6;i++){if(arrayStep41[i]==local){while((style[4]!=3)){exchange(arrayStep41[i%6],arrayStep41[(i+1)%6]);i=(i+1)%6;}while(local!=3){exchange(arrayStep41[i%6],arrayStep41[(i+5)%6]);i=(i+5)%6;}break;}}}void step5(){int arrayStep51[9]={3,0,1,4,5,2,1,0,3};i=0;do{exchange(arrayStep51[i],arrayStep51[i+1]);i++;}while(local!=3);}void step6(){for(i=0;i<6;i++){if(arrayStep41[i]==local){while(style[5]!=4){exchange(arrayStep41[i%6],arrayStep41[(i+1)%6]);i++;}if(local==8)exchange(8,7);break;}}return;}void step7(){for(i=0;i<4;i++){if(arrayStep71[i]==local){while(style[4]!=5){exchange(arrayStep71[i%4],arrayStep71[(i+1)%4]);i=(i+1)%4;}while(local!=3){exchange(arrayStep71[i%4],arrayStep71[(i+3)%4]);i=(i+3)%4;}break;}}}void step8(){int arrayStep81[13]={3,0,1,2,5,4,7,8,5,2,1,0,3};i=0;do{exchange(arrayStep81[i],arrayStep81[i+1]);i++;}while(local!=3);}void step9(){for(i=0;i<4;i++){if(arrayStep71[i]==local){while(style[7]!=6){exchange(arrayStep71[i%4],arrayStep71[(i+1)%4]);i=(i+1)%4;}while(local!=4){exchange(arrayStep71[i%4],arrayStep71[(i+3)%4]);i=(i+3)%4;}break;}}}void print(){for(j=0;j<9;j++){if(style[j]==0)printf(" \t");elseprintf("%d\t",style[j]);if((j+1)%3==0)printf("\n");}printf("************ %d ***********\n",number);}void loop(){printf(" 请输入数码：\n");for(i=0;i<9;i++)scanf("%d",&style[i]);judge();step1();step2();step3();if(style[2]!=3){step4();step5();}step6();if(style[8]!=5){step7();step8();}step9();print();if(!((style[3]==8)&&(style[6]==7)))printf(" 用书上所给算法来看此数码错误！\n"); }void main(){while(1)loop();}2.深度优先实现/***************说明 ***********************用宽度优先搜寻算法实现八数码问题******************************************/#include<iostream>#include<stdio.h>#include<fstream>#include<stdlib.h>#include "string.h"#include "assert.h"#include "windows.h"using namespace std;int wholeStyle[9] = {2,8,3,1,6,4,7,0,5};int standard1[9] = {1,2,3,8,0,4,7,6,5};int local,i,j;int startKey = 0,endKey = 0,equalKey = 1,tempSpace;struct node *openHead,*open; //open 表struct node *closedHead,*closed; //closed 表struct node *tempNode; //临节气点struct node *answer; // 找到的路径int num = 0;struct node{int style[9];struct node *next;struct node *father;};void updateData()//更新要判断数据{int i;printf(" 请输入八数码原始状态：\n");for(i = 0;i < 9;i++)scanf("%d",&wholeStyle[i]);printf(" 请输入八数码最后状态：\n");for(i = 0;i < 9;i++)scanf("%d",&standard1[i]);}void judge1(struct node *head)// 判断空格地点{for(i = 0;i < 9;i++){if(head->style[i] == 0){local = i;return;}}}int judge2(struct node *head) // 判断能否与标准八数码相等，不相等返回值为0 {for(i = 0;i < 9;i++){if(head->style[i] != standard1[i]){if((i == 3)&&(head->style[3] == standard1[6]));else if((i == 6)&&(head->style[6] == standard1[3]));elsereturn 0;}}return 1;}void judge3() // 判断重生成的八数码能否就是最后状态或许在open、 closed 表中出现{if(judge2(tempNode))endKey = 1;else{while(openHead->next->next->style[0] != 9){for(i = 0;i < 9;i++){if(openHead->next->next->style[i] != tempNode->style[i]){equalKey = 1;break;}elseequalKey = 0;}if(equalKey)// 不相等openHead = openHead->next;elsebreak;}openHead = open->next;if(equalKey)// 不相等{while(closedHead->next->style[0] != 9){for(i = 0;i < 9;i++){if(closedHead->next->style[i] != tempNode->style[i]){equalKey = 1;break;}elseequalKey = 0;}if(!equalKey)// 相等break;elseclosedHead = closedHead->next;}closedHead = closed->next;}if(equalKey)// 不相等{open->next = tempNode;tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;}}}void print(struct node *temp)// 输出八数码表{for(j = 0;j < 9;j++){if(temp->style[j] == 0)printf(" \t");elseprintf("%d\t",temp->style[j]);if((j + 1) % 3 == 0)printf("\n");}}void write2txt(){ofstream out("F:\\out_details.txt",ios::app);if( out.fail() ){cerr<<" 未找到文件 "<<endl;}out<<"第 "<<++num<<" 步 \n";out<<"open table ： \n";while(openHead->next->style[0] != 9){for(i = 0;i < 9;i ++){out<<openHead->next->style[i]<<"\t";if((i+1) % 3 == 0)out<<"\n";}out<<"\n";openHead = openHead->next;}openHead = openHead->next;out<<"*********************\n";out<<"closed table ： \n";while(closedHead->next->style[0] != 9){for(i = 0;i < 9;i ++){out<<closedHead->next->style[i]<<"\t";if((i + 1) % 3 ==0)out<<"\n";}out<<"\n";closedHead = closedHead->next;}closedHead = closedHead->next;out<<"-----------------------------------\n";out.close();}void main(){//updateData();// 输入八数码数据for(i = 0;i < 9;i++)//判断初始状态能否已经为最后状态{if(wholeStyle[i] == standard1[i]);else{if((i == 3)&&(wholeStyle[i] == standard1[6]));else if((i == 6)&&(wholeStyle[i] == standard1[3]));else{startKey = 1;break;}}}if(!startKey){printf(" 不用判断！ \n");return;}printf(" 要判断！ \n");openHead = new node();open = new node();openHead->style[0] = 9;openHead->next = open;for(i = 0;i < 9;i++)open->style[i] = wholeStyle[i];open->next = openHead;open->father = openHead;closedHead = new node();closed = new node();closedHead->style[0] = 9;closedHead->next = closedHead;closed = closedHead;while(open->style[0] != 9)//当open表不为空时向来循环{judge1(openHead->next);if(local % 3 > 0)// 右移{equalKey = 1;tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local - 1];tempNode->style[local - 1] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;if(local > 2)// 下移{equalKey = 1;tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local - 3];tempNode->style[local - 3] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;if(local % 3 < 2)// 左移{equalKey = 1;tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local + 1];tempNode->style[local + 1] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;if(local < 6)// 上移{equalKey = 1;tempNode = new node();//tempNode = malloc(sizeof(struct node));for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local + 3];tempNode->style[local + 3] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;closed->next = openHead->next; // 把 open 的标头增添到closed 表中openHead->next = openHead->next->next;closed = closed->next;closed->next = closedHead;write2txt();}open->next = tempNode;// 把找到的新节点增添到open 表中tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;closed 表中closed->next = openHead->next; //把 open 的标头增添到openHead->next = openHead->next->next;closed = closed->next;closed->next = closedHead;write2txt();answer = new node();tempNode = new node();tempNode = open;while(tempNode->style[0] != 9)// 将结果路径存于answer{answer = tempNode;tempNode = tempNode->father;tempNode->next = answer;}num = 0;while(answer->next->style[0] != 9)//输出answer{printf("***********第%d 步***********\n",num++);print(answer);answer = answer->next;printf("\n");}printf("***********第 %d 步 ***********\n",num++);print(answer);if(answer->style[3] != standard1[3])printf("\n!! 输入的八数码不合法，不可以从初始状态到最后状态 \n\n\n\n");return;}3.宽度优先：/***************说明 ***********************用宽度优先搜寻算法实现八数码问题******************************************/#include<iostream>#include<stdio.h>#include<fstream>#include<stdlib.h>#include "string.h"#include "assert.h"#include "windows.h"using namespace std;int wholeStyle[9] = {2,8,3,1,6,4,7,0,5};int standard1[9] = {1,2,3,8,0,4,7,6,5};int local,i,j;int startKey = 0,endKey = 0,equalKey = 1,tempSpace; struct node *openHead,*open; //open 表struct node *closedHead,*closed; //closed 表struct node *tempNode; //临节气点struct node *answer; // 找到的路径int num = 0;struct node{int style[9];struct node *next;struct node *father;};void updateData()//更新要判断数据{int i;printf(" 请输入八数码原始状态：\n");for(i = 0;i < 9;i++)scanf("%d",&wholeStyle[i]);printf(" 请输入八数码最后状态：\n");for(i = 0;i < 9;i++)scanf("%d",&standard1[i]);}void judge1(struct node *head)// 判断空格地点{for(i = 0;i < 9;i++){if(head->style[i] == 0){local = i;return;}}}int judge2(struct node *head) // 判断能否与标准八数码相等，不相等返回值为0{for(i = 0;i < 9;i++){if(head->style[i] != standard1[i]){if((i == 3)&&(head->style[3] == standard1[6]));else if((i == 6)&&(head->style[6] == standard1[3]));elsereturn 0;}}return 1;}void judge3() // 判断重生成的八数码能否就是最后状态或许在open、 closed 表中出现{if(judge2(tempNode))endKey = 1;else{while(openHead->next->next->style[0] != 9){for(i = 0;i < 9;i++){if(openHead->next->next->style[i] != tempNode->style[i]){equalKey = 1;break;}elseequalKey = 0;}if(equalKey)// 不相等openHead = openHead->next;elsebreak;}openHead = open->next;if(equalKey)// 不相等{while(closedHead->next->style[0] != 9){for(i = 0;i < 9;i++){if(closedHead->next->style[i] != tempNode->style[i]){equalKey = 1;break;}elseequalKey = 0;}if(!equalKey)// 相等break;elseclosedHead = closedHead->next;}closedHead = closed->next;}if(equalKey)// 不相等{open->next = tempNode;tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;}}}void print(struct node *temp)// 输出八数码表{for(j = 0;j < 9;j++){if(temp->style[j] == 0)printf(" \t");elseprintf("%d\t",temp->style[j]);if((j + 1) % 3 == 0)printf("\n");}}void write2txt(){ofstream out("F:\\out_details.txt",ios::app);if( out.fail() ){cerr<<" 未找到文件 "<<endl;}out<<"第 "<<++num<<" 步 \n";out<<"open table ： \n";while(openHead->next->style[0] != 9){for(i = 0;i < 9;i ++){out<<openHead->next->style[i]<<"\t";if((i+1) % 3 == 0)out<<"\n";}out<<"\n";openHead = openHead->next;}openHead = openHead->next;out<<"*********************\n";out<<"closed table ： \n";while(closedHead->next->style[0] != 9){for(i = 0;i < 9;i ++){out<<closedHead->next->style[i]<<"\t";if((i + 1) % 3 ==0)out<<"\n";}out<<"\n";closedHead = closedHead->next;}closedHead = closedHead->next;out<<"-----------------------------------\n";out.close();}void main(){//updateData();// 输入八数码数据for(i = 0;i < 9;i++)//判断初始状态能否已经为最后状态{if(wholeStyle[i] == standard1[i]);else{if((i == 3)&&(wholeStyle[i] == standard1[6]));else if((i == 6)&&(wholeStyle[i] == standard1[3]));else{startKey = 1;break;}}}if(!startKey){printf(" 不用判断！ \n");return;}printf(" 要判断！ \n");openHead = new node();open = new node();openHead->style[0] = 9;openHead->next = open;for(i = 0;i < 9;i++)open->style[i] = wholeStyle[i];open->next = openHead;open->father = openHead;closedHead = new node();closed = new node();closedHead->style[0] = 9;closedHead->next = closedHead;closed = closedHead;while(open->style[0] != 9)//当open表不为空时向来循环{judge1(openHead->next);if(local % 3 > 0)// 右移{equalKey = 1;tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local - 1];tempNode->style[local - 1] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;if(local > 2)// 下移{equalKey = 1;tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local - 3];tempNode->style[local - 3] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;if(local % 3 < 2)// 左移{equalKey = 1;tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local + 1];tempNode->style[local + 1] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;if(local < 6)// 上移{equalKey = 1;tempNode = new node();//tempNode = malloc(sizeof(struct node));for(i = 0;i < 9;i++)tempNode->style[i] = openHead->next->style[i];tempSpace = tempNode->style[local + 3];tempNode->style[local + 3] = tempNode->style[local];tempNode->style[local] = tempSpace;judge3();}if(endKey)break;closed->next = openHead->next;// 把 open 的标头增添到closed 表中openHead->next = openHead->next->next;closed = closed->next;closed->next = closedHead;write2txt();}open 表中open->next = tempNode;// 把找到的新节点增添到tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;closed 表中closed->next = openHead->next; //把 open 的标头增添到openHead->next = openHead->next->next;closed = closed->next;closed->next = closedHead;write2txt();answer = new node();tempNode = new node();tempNode = open;while(tempNode->style[0] != 9)//将结果路径存于answer{answer = tempNode;tempNode = tempNode->father;tempNode->next = answer;}num = 0;while(answer->next->style[0] != 9)//输出answer{printf("***********第%d 步***********\n",num++);print(answer);answer = answer->next;printf("\n");}printf("***********第 %d 步 ***********\n",num++);print(answer);if(answer->style[3] != standard1[3])printf("\n!! 输入的八数码不合法，不可以从初始状态到最后状态\n\n\n\n");return;}4.A 算法/***************说明 ************************* A 算法实现八数码问题********************************************/#include<iostream>#include<fstream>#include<iomanip>using namespace std;void print(struct node *temp);int wholeStyle[9] = {2,8,3,1,6,4,7,0,5};int standard1[9] = {1,2,3,8,0,4,7,6,5};int local,i,j;int tempSpace;struct node *openHead,*open; //open 表struct node *closedHead,*closed; //closed 表struct node *tempNode; //临节气点struct node *answer; // 找到的路径int num = 0;bool endKey;struct node{int depth;int judgement_based;int style[9];struct node *next;struct node *father;};void updateData()//更新要判断数据{int i;cout<<" 请输入八数码原始状态："<<endl;for(i = 0;i < 9;i++)cin>>wholeStyle[i];cout<<" 请输入八数码最后状态："<<endl;for(i = 0;i < 9;i++)cin>>standard1[i];}int judge1(struct node *head)// 判断空格地点{for(i = 0;i < 9;i++){if(head->style[i] == 0)return i;}}int evaluation_function(struct node *head) //计算不在正确地点的点的个数{int not_correct_position = 0;for(i = 0;i < 9;i++)if((head->style[i] != 0)&&(head->style[i] != standard1[i]))not_correct_position++;return not_correct_position;}void print(struct node *temp)// 输出八数码表{for(j = 0;j < 9;j++){if(temp->style[j] == 0)cout<<" \t";elsecout<<temp->style[j]<<"\t";if((j + 1) % 3 == 0)cout<<endl;}}void write2txt()// 将过程记录到文本文档中{ofstream out("F:\\out_details4.txt",ios::app);if( out.fail() ){cerr<<" 未找到文件 "<<endl;}out<<"第 "<<++num<<" 步 \n";out<<"open table ： \n";while(openHead->next->style[0] != 9){for(i = 0;i < 9;i ++){out<<openHead->next->style[i]<<"\t";if((i+1) % 3 == 0)out<<"\n";}out<<" 估值： ";out<<openHead->next->judgement_based<<"\n";openHead = openHead->next;}openHead = openHead->next;out<<"*********************\n";out<<"closed table ： \n";while(closedHead->next->style[0] != 9){for(i = 0;i < 9;i ++){out<<closedHead->next->style[i]<<"\t";if((i + 1) % 3 ==0)out<<"\n";}out<<"深度："<<closedHead->next->depth<<"估值："<<closedHead->next->judgement_based<<"\n";closedHead = closedHead->next;}closedHead = closedHead->next;out<<"-----------------------------------\n";out.close();}void basic_exchange_oper()// 每一次基本的互换都要进行的动作{if(judge1(tempNode) != judge1(closed->father))// 当重生成节点的空格地点与 closed 父亲节点的空格地点不相等{tempNode->father = closed; // 重生成节点的指向它的父亲节点 tempNode->depth =closed->depth + 1;// 深度加 1 tempNode->judgement_based =evaluation_function(tempNode) + tempNode->depth;//计算估值while(openHead->next->style[0] != 9){if(tempNode->judgement_based > openHead->next->judgement_based){openHead = openHead->next;}else{tempNode->next = openHead->next;openHead->next = tempNode;openHead = open->next;return;}}//插入的值比最后一个还大进行下边的操作openHead = open->next;// 先恢复表头不然 Head 指向为最后一个open->next = tempNode;tempNode->next = openHead;open = open->next;return;}}void main(){//updateData();// 输入八数码数据openHead = new node();//初始化 open 表open = new node();openHead->style[0] = 9;openHead->next = open;for(i = 0;i < 9;i++)open->style[i] = wholeStyle[i];open->next = openHead;open->father = openHead;open->depth = 0;open->judgement_based = evaluation_function(open) + open->depth;// 这行能够不写closedHead = new node(); //初始化 closed 表closed = new node();closedHead->style[0] = 9;closedHead->next = closedHead;closed = closedHead;int min_judgement1 = open->judgement_based;while(open->style[0] != 9)//当open表不为空时向来循环{//updateData();// 输入八数码数据write2txt();closed->next = openHead->next;//把 open 表中第一组八数码移到closed 表中openHead->next = openHead->next->next;closed = closed->next;closed->next = closedHead;if(openHead->next->style[0] == 9)// 假如是第一次则 open 暂时指向openHead open = openHead;if(closed->judgement_based == closed->depth)// 判断新移进 closed 表中的八数码的 f 值能否等于它的层数{cout<<"succeed!"<<endl;write2txt();answer = new node();while(closed->style[0] != 9)// 将结果存于answer 表中{answer = closed;closed = closed->father;closed->next = answer;}num = 0;while(answer->style[0] != 9)//控制台显示步骤{cout<<"****** 第 "<<num++<<" 步 ***********\n";print(answer);cout<<endl;answer = answer->next;}return;}else //假如 closed 表末的八数码是最后状态则拓展新的八数码{local = judge1(closed);if(local % 3 > 0)// 右移{tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = closed->style[i];tempSpace = tempNode->style[local - 1];tempNode->style[local - 1] = tempNode->style[local];tempNode->style[local] = tempSpace;basic_exchange_oper();}if(local < 6)// 上移{tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = closed->style[i];tempSpace = tempNode->style[local + 3];tempNode->style[local + 3] = tempNode->style[local];tempNode->style[local] = tempSpace;basic_exchange_oper();}if(local > 2)// 下移{tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = closed->style[i];tempSpace = tempNode->style[local - 3];tempNode->style[local - 3] = tempNode->style[local];tempNode->style[local] = tempSpace;basic_exchange_oper();}if(local % 3 < 2)// 左移{tempNode = new node();for(i = 0;i < 9;i++)tempNode->style[i] = closed->style[i];tempSpace = tempNode->style[local + 1];tempNode->style[local + 1] = tempNode->style[local];tempNode->style[local] = tempSpace;basic_exchange_oper();}}}cout<<"false!"<<endl;}神经网络实验群神经网络实验一、实验目的：理解反向流传网络的构造和原理，掌握反向流传算法对神经元的训练过程，认识反向流传公式。

八个数字问题实验报告. 《八数码问题》实验报告首先，实验的目的:熟悉启发式搜索算法。

二、实验内容:启发式搜索算法用于解决8位数问题。

编制了程序，实现了解决8位数问题的算法。

采用评估功能，其中:是搜索树中节点的深度；在节点数据库中放错位置的件数；这是每个棋子与其在节点数据库中的目标位置之间距离的总和。

三、实验原理:1.问题描述:八位数问题也被称为九宫问题。

在3×3的棋盘上，有八个棋子，每一个棋子都标有一定的1到8的数字，不同棋子上标的数字是不同的。

棋盘上还有一个空格(用数字0表示)，与空格相邻的棋子可以移动到空格中。

要解决的问题是: 给定初始状态和目标状态，找出从初始状态到目标状态移动次数最少的移动步骤。

所谓问题的一种状态是棋盘上棋子的排列。

解决八位数问题实际上是找出一系列从初始状态到目标状态的中间过渡状态。

2.原则描述:启发式搜索(1)原理启发式搜索是评估每个搜索在状态空间中的位置以获得最佳位置，然后从这个位置搜索到目标。

这样，可以省略大量不必要的搜索路径，并且提高了效率。

在启发式搜索中，位置的评估非常重要。

不同的评估会产生不同的效果。

(2)评估函数计算节点的评估函数，可分为两部分:1.成本已经支付(从开始节点到当前节点)；2.要支付的价格(当前节点到目标节点)。

节点n的评估函数被定义为从初始节点通过n到目标节点的路径的最小成本的估计值，即=。

是从初始节点到达当前节点n的实际成本；是从节点n到目标节点的最佳路径的估计开销。

比例越大，它越倾向于先搜索宽度或同等成本。

相反，比例越大，启发式性能越强。

(3)算法描述:(1)将起始节点S放入OPEN表中，计算节点S的值；(2)如果OPEN为空表，则无法退出且没有解决方案；(3)从OPEN表中选择具有最小值的节点。

如果多个节点具有相同的值，当其中一个节点是目标节点时，选择目标节点；否则，任意一个节点被选为节点；(4)从OPEN表中移除节点，并将其放入CLOSED扩展节点表中；(5)如果它是目标节点，它成功退出并获得解决方案；⑥扩展节点以生成其所有后续节点。

八数码人工智能实验报告八数码人工智能实验报告引言：八数码是一种经典的数学问题，也是人工智能领域中常用的实验题目之一。

本次实验旨在通过使用搜索算法解决八数码问题，探讨人工智能在解决复杂问题上的应用。

一、问题描述：八数码问题是一种数字排列游戏，使用一个3x3的方格，其中8个方格上各有一个数字，剩下一个方格为空白。

通过移动数字方格，最终将数字按照从小到大的顺序排列，空白方格位于最后一个位置。

例如，初始状态为：1 2 38 47 6 5目标状态为：1 2 34 5 67 8二、算法选择：本次实验采用了A*搜索算法来解决八数码问题。

A*算法是一种启发式搜索算法，通过估计每个搜索节点到达目标状态的代价来进行搜索。

它综合了广度优先搜索和最佳优先搜索的优点，能够高效地找到最优解。

三、实验过程：1. 状态表示：在实验中，我们使用一个3x3的二维数组来表示八数码的状态。

数组中的每个元素代表一个方格的数字，空白方格用0表示。

2. 启发函数：为了评估每个搜索节点到达目标状态的代价，我们需要定义一个启发函数。

本实验中，我们选择了曼哈顿距离作为启发函数。

曼哈顿距离是指每个数字方格与其目标位置之间的水平和垂直距离之和。

3. A*算法：A*算法的核心思想是维护一个优先队列，根据每个搜索节点的估价函数值进行排序。

具体步骤如下：- 将初始状态加入优先队列，并设置初始估价函数值为0。

- 从优先队列中取出估价函数值最小的节点，进行扩展。

- 对于每个扩展节点，计算其估价函数值，并将其加入优先队列。

- 重复上述步骤，直到找到目标状态或者队列为空。

四、实验结果：经过实验，我们发现A*算法能够高效地解决八数码问题。

对于初始状态为随机排列的八数码，A*算法能够在较短的时间内找到最优解。

实验结果表明，A*算法在解决八数码问题上具有较好的性能。

五、实验总结：本次实验通过使用A*搜索算法解决八数码问题，展示了人工智能在解决复杂问题上的应用。

A*算法通过合理的启发函数和优先队列的维护，能够高效地找到最优解。

题目: a算法求解八数码问题实验报告目录1. 实验目的2. 实验设计3. 实验过程4. 实验结果5. 实验分析6. 实验总结1. 实验目的本实验旨在通过实验验证a算法在求解八数码问题时的效果，并对其进行分析和总结。

2. 实验设计a算法是一种启发式搜索算法，主要用于在图形搜索和有向图中找到最短路径。

在本实验中，我们将使用a算法来解决八数码问题，即在3x3的九宫格中，给定一个初始状态和一个目标状态，通过移动数字的方式将初始状态转变为目标状态。

具体的实验设计如下：1) 实验工具：我们将使用编程语言来实现a算法，并结合九宫格的数据结构来解决八数码问题。

2) 实验流程：我们将设计一个初始状态和一个目标状态，然后通过a 算法来求解初始状态到目标状态的最短路径。

在求解的过程中，我们将记录下每一步的状态变化和移动路径。

3. 实验过程我们在编程语言中实现了a算法，并用于求解八数码问题。

具体的实验过程如下：1) 初始状态和目标状态的设计：我们设计了一个初始状态和一个目标状态，分别为：初始状态：1 2 34 5 67 8 0目标状态：1 2 38 0 42) a算法求解：我们通过a算法来求解初始状态到目标状态的最短路径，并记录下每一步的状态变化和移动路径。

3) 实验结果在实验中，我们成功求解出了初始状态到目标状态的最短路径，并记录下了每一步的状态变化和移动路径。

具体的实验结果如下：初始状态：1 2 34 5 67 8 0目标状态：1 2 38 0 47 6 5求解路径：1. 上移1 2 37 8 62. 左移1 2 3 4 0 5 7 8 63. 下移1 2 3 4 8 5 7 0 64. 右移1 2 3 4 8 5 0 7 65. 上移1 2 3 0 8 5 4 7 61 2 38 0 54 7 67. 下移1 2 38 7 54 0 68. 右移1 2 38 7 54 6 0共计8步，成功从初始状态到目标状态的最短路径。

《八数码问题》实验报告一、实验目的：熟练掌握启发式搜索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 的比重越大，表示启发性能就越强。

人工智能实验报告八数码
人工智能实验报告：八数码
引言
人工智能（AI）是当今世界上最热门的领域之一，它已经在许多领域取得了巨大的成功，包括医疗保健、金融、交通和娱乐等。

在这篇实验报告中，我们将探讨人工智能在解决八数码问题上的应用。

八数码问题是一个经典的智力游戏，它要求玩家将一个3x3的方格中的数字1-8和一个空白格按照一定的规则进行移动，最终达到特定的排列顺序。

这个问题看似简单，但实际上是一个复杂的组合优化问题，需要大量的搜索和计算才能找到最优解。

实验目的
本实验旨在使用人工智能技术解决八数码问题，通过比较不同算法的表现，评估它们在解决这一问题上的效率和准确性。

实验方法
我们使用了两种经典的人工智能算法来解决八数码问题，分别是深度优先搜索（DFS）和A*搜索算法。

我们编写了相应的程序，并在相同的硬件环境下进行了实验。

实验结果
通过实验我们发现，深度优先搜索算法在解决八数码问题上存在着局部最优解的问题，容易陷入死循环。

而A*搜索算法则能够更快地找到最优解，并且在解决问题时所需的搜索次数更少。

结论
本实验结果表明，A*搜索算法在解决八数码问题上表现更优秀，具有更高的效率和准确性。

这为我们在实际应用中选择合适的人工智能算法提供了重要的参考。

未来展望
随着人工智能技术的不断发展，我们相信在解决类似的组合优化问题上会出现更多更高效的算法。

我们将继续深入研究，探索更多的人工智能算法，并将其应用于更广泛的领域，为人类社会带来更多的便利和创新。

八数码问题实验报告八数码问题实验报告引言：八数码问题，也被称为九宫格问题，是一种经典的数学谜题。

在一个3x3的方格中，摆放有1至8的数字，其中一个位置为空。

目标是通过交换数字的位置，将数字按照从小到大的顺序排列，最终使得空格位于最后一个位置。

本实验旨在通过编程实现八数码问题的求解，并探讨不同算法在解决该问题上的效果和优劣。

实验步骤：1. 算法选择在本次实验中，我们选择了广度优先搜索算法和A*算法作为求解八数码问题的两种不同方法。

广度优先搜索算法是一种盲目搜索算法，它通过逐层扩展搜索树，直到找到目标状态。

而A*算法则是一种启发式搜索算法，它结合了广度优先搜索和启发式函数，通过评估每个状态的代价来指导搜索过程，以找到最优解。

2. 算法实现我们使用Python语言实现了以上两种算法。

首先，我们定义了一个表示状态的类，并实现了状态的初始化、移动、判断是否达到目标状态等基本操作。

然后，我们分别编写了广度优先搜索算法和A*算法的求解函数。

在广度优先搜索算法中，我们使用队列数据结构来保存待扩展的状态，以实现逐层扩展的效果；在A*算法中，我们使用优先队列来保存待扩展的状态，并根据启发式函数的值进行优先级排序。

3. 实验结果我们使用了多个测试样例来验证两种算法的求解效果。

实验结果表明，广度优先搜索算法能够找到解，但是在面对状态空间较大的情况下，搜索时间会呈指数级增长。

而A*算法则能够更快地找到最优解，其效率相对较高。

然而，A*算法需要选择合适的启发式函数，并且对于某些特殊情况，可能会陷入局部最优解而无法找到最优解。

4. 结果分析通过对比两种算法的求解结果，我们可以发现广度优先搜索算法和A*算法在时间效率和解的质量上存在一定的差异。

广度优先搜索算法适用于状态空间较小的情况，但是在状态空间较大时效率较低；而A*算法则能够在较短的时间内找到最优解，但需要对问题进行合理的建模和启发式函数的选择。

因此，在实际应用中，我们需要根据问题的规模和特点来选择合适的算法。

八数码问题实验报告引言八数码问题是一个著名的数学问题，也是一个经典的搜索算法应用场景。

该问题是在一个3x3的棋盘上，分布着1至8这8个数字，其中一个格子是空白的。

目标是通过交换棋盘上的数字，使得棋盘上的数字按照从小到大的顺序排列，空白格子位于最后。

本实验报告将介绍八数码问题的背景、具体实验步骤以及实验结果分析。

实验步骤1.定义状态空间和目标状态：将八数码问题抽象成一个状态空间图。

每个状态表示一个棋盘布局，目标状态是数字按照从小到大的顺序排列，空白格子位于最后。

2.实现状态的表示：使用一个3x3的二维数组来表示棋盘状态，空白格子用0表示。

3.实现状态转移函数：定义合法的移动操作，例如将一个数字移动到空白格子的位置。

根据当前状态和移动操作，得到下一个状态。

4.实现启发式函数：设计一个启发式函数来评估当前状态和目标状态之间的距离。

常用的启发式函数有曼哈顿距离和错位数。

5.实现搜索算法：选择合适的搜索算法，例如A算法或IDA算法。

根据当前状态和目标状态，通过搜索算法找到最优解。

6.实验结果分析：运行实验程序，记录搜索所需的时间和搜索路径长度。

分析不同启发式函数和搜索算法对实验结果的影响。

实验结果分析本次实验中，我们选择了A*算法作为搜索算法，曼哈顿距离作为启发式函数。

经过多次实验，我们发现实验结果受到初始状态的影响较大。

对于某些初始状态，搜索算法可以在较短的时间内找到最优解，而对于其他初始状态，搜索时间较长。

这是因为八数码问题的状态空间非常庞大，搜索算法需要遍历大量的状态才能找到最优解。

另外，我们还发现启发式函数的选择对搜索效率有一定的影响。

曼哈顿距离作为一种常用的启发式函数，可以提供较好的搜索效果。

而对于某些特定的初始状态，如果选择了错误的启发式函数，可能会导致搜索算法无法找到最优解。

在实验过程中，我们还发现A算法在某些情况下会陷入局部最优解，而无法找到全局最优解。

这是因为A算法的搜索过程是基于启发式函数的估计值，存在一定的不确定性。

实验报告一、实验问题八数码问题求解二、实验软件VC6.0 编程语言或其它编程语言三、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。

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

2 83 1 2 31 4 8 47 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 数码问题的隐式图的生成问题。

人工智能基础实验报告题目：八数码问题一、内容 (2)二、目的 (2)三、实验设计思想和流程 (2)四、主要数据结构及符号说明 (3)五、程序初值及运行结果 (5)附录（源代码及注释） (6)一、内容八数码问题由8个编号1~8并放在3*3方格棋盘上的可走动的棋子组成。

棋盘上有一个格是空的，以便可以让空格周围的棋子走进空格，这也可以理解为移动空格。

给出起始状态和目标状态。

用A*算法求解出移动的路径。

二、目的1、学会用状态空间法来进行知识表示2、理解A*算法三、实验设计思想和流程1.八数码问题的状态表示八数码问题的一个状态就是八个数字在棋盘上的一种放法。

每个棋子用它上面所标的数字表示，并用0表示空格，这样就可以将棋盘上棋子的一个状态存储在一个二维数组中。

2、结点扩展规则搜索就是按照一定规则扩展已知结点，直到找到目标结点或所有结点都不能扩展为止。

八数码问题的结点扩展应当遵守棋子的移动规则。

按照棋子移动的规则，每一次可以将一个与空格相邻棋子移动到空格中，实际上可以看作是空格作相反移动。

空格移动的方向可以是右、下、左、上，当然不能移出边界。

3、A*算法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)。

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

二、实验内容1、八数码问题描述所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8，其中一个单元格是空的。

将任意摆放的数码盘（城初始状态）逐步摆成某个指定的数码盘的排列（目标状态），如图1所示：图1 八数码问题的某个初始状态和目标状态对于以上问题，我们可以把数码的移动等效城空格的移动。

如图1的初始排列，数码7右移等于空格左移。

那么对于每一个排列，可能的一次数码移动最多只有4中，即空格左移、空格右移、空格上移、空格下移。

最少有两种（当空格位于方阵的4个角时）。

所以，问题就转换成如何从初始状态开始，使空格经过最小的移动次数最后排列成目标状态。

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*算法。

八数码问题,实验报告八数码实验报告利用人工智能技术解决八数码游戏问题1．八数码游戏问题简介九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。

问题是在3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。

问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。

2．八数码游戏问题的状态空间法表示①建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中②建立CLOSED表，且置为空表③判断OPEN表是否为空表，若为空，则问题无解，退出④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。

问题的解就是沿着n到S0的路径得到。

若不是转⑥⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中⑦对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点, 设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。

⑧按某一任意方式或某种策略重排OPEN表中节点的顺序⑨转③3．八数码游戏问题的盲目搜索技术宽度优先搜索：1、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-first search)。

2、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

3、宽度优先搜索算法(1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。

(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。

(3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED 的扩展节点表中。

人工智能实验报告-八数码（五篇模版）第一篇：人工智能实验报告-八数码《人工智能》实验一题目实验一启发式搜索算法1.实验内容：使用启发式搜索算法求解8数码问题。

⑴ 编制程序实现求解8数码问题A*算法，采用估价函数⎧⎪w(n)，f(n)=d(n)+⎨pn⎪⎩()其中：d(n)是搜索树中结点n的深度；w(n)为结点n的数据库中错放的棋子个数；p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。

⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界的h(n)的定义，并测试使用该估价函数是否使算法失去可采纳性。

2.实验目的熟练掌握启发式搜索A算法及其可采纳性。

3.数据结构与算法设计该搜索为一个搜索树。

为了简化问题，搜索树节点设计如下：typedef struct Node//棋盘 {//节点结构体int data[9];double f,g;struct Node * parent;//父节点}Node,*Lnode;int data[9];数码数组：记录棋局数码摆放状态。

struct Chess * Parent;父节点：指向父亲节点。

下一步可以通过启发搜索算法构造搜索树。

1、局部搜索树样例：*2、搜索过程搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。

搜索过程如下：（1）、把原棋盘压入队列；（2）、从棋盘取出一个节点；（3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；（5）、跳到步骤（2）；3、算法的评价完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。

现存在的一些优缺点。

1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N 数码问题的求解过程。