当前位置：文档之家 › 八数码问题C语言A星算法详细实验报告含代码

八数码问题C语言A星算法详细实验报告含代码

  • 格式：doc
  • 大小：224.50 KB
  • 文档页数：10

一、实验内容与要求八数码问题:在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 31 6 4 8 0 47 0 5 7 6 5运行结果屏幕打印OPEN表与CLOSE表:OPEN CLOSE1 2 3 4 02 3 4 5 6 0 12 3 4 6 7 0 1 52 3 4 6 8 9 0 1 5 72 3 4 8 9 10 0 1 5 7 62 3 4 8 11 12 13 0 1 5 7 6 92 3 4 8 12 13 14 15 0 1 5 7 6 9 113 4 8 12 13 14 15 16 17 0 1 5 7 6 9 11 24 8 12 13 14 15 16 17 18 19 0 1 5 7 6 9 11 2 34 8 12 13 14 15 16 17 19 20 0 1 5 7 6 9 11 2 3 188 12 13 14 15 16 17 19 21 22 0 1 5 7 6 9 11 2 3 18 412 13 14 15 16 17 19 21 22 23 0 1 5 7 6 9 11 2 3 18 4 812 13 14 15 16 17 19 21 22 24 25 0 1 5 7 6 9 11 2 3 18 4 8 2312 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为目标节点搜索树:0…7 2 8 3 1 0 4 7 6 5六、结论对于八数码问题,BFS算法最慢,A*算法较快。

八数码问题的一个状态实际上就是0~9的一个排列,对于任意给定的初始状态与目标,不一定有解,也就就是说从初始状态不一定能到达目标状态。

因为排列有奇排列与偶排列两类,从奇排列不能转化成偶排列。

如果一个数字0~8的随机排列871526340,用F(X)表示数字X前面比它小的数的个数,全部数字的F(X)之与为Y=∑(F(X)),如果Y为奇数则称原数字的排列就是奇排列,如果Y为偶数则称原数字的排列就是偶排列。

因此,可以在运行程序前检查初始状态与目标状态的排序的奇偶行就是否相同,相同则问题可解,应当能搜索到路径。

否则无解。

七、源程序及注释#include <iostream>#include <ctime>#include <vector>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<Node> node_v; // 储存节点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<Node>& rstep_v) { //输出步骤rstep_v、push_back(node_v[index]);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 S 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 nodefor (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;}elseflag = 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) {S[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) {S[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) {S[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) {S[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<Node> rstep_v;cout << "初始状态:" << endl;cout << src << endl;PrintSteps(loc, rstep_v);cout << "成功!" << endl;break;}elseProcessNode(loc);}}return 0;}。

合集下载

A星算法求解八数码技术报告

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星算法解决八数码问题

用A星算法解决八数码问题

A*算法解决八数码问题1 问题描述什么是八数码问题八数码游戏包括一个3×3的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。

与空位相邻的棋子可以滑动到空位中。

游戏的目的是要达到一个特定的目标状态。

标注的形式化如下：问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：任何状态都可以被指定为初始状态。

操作符：用来产生4个行动（上下左右移动）。

目标测试：用来检测状态是否能匹配上图的目标布局。

路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。

解决方案介绍算法思想(估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。

估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n 节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

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

搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。

启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有 h ( t ) = 0，对于结点m和n （n 是m的子结点）有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。

数码问题C语言A星算法详细实验报告含代码

数码问题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)。

八数码C语言A算法详细代码

八数码C语言A算法详细代码

#include<iostream>#include<time.h>#include<windows.h>#include<vector>#include<cmath>using namespace std;struct node{int a[3][3]; //存放矩阵int father; //父节点的位置int gone; //是否遍历过,1为是,0为否int fn; //评价函数的值int x,y; //空格的坐标int deep; //节点深度};vector<node> store; //存放路径节点int mx[4]={-1,0,1,0};int my[4]={0,-1,0,1}; //上下左右移动数组int top; //当前节点在store中的位置bool check(int num) //判断store[num]节点与目标节点是否相同,目标节点储存在store[0]中{for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(store[num].a[i][j]!=store[0].a[i][j])return false;}}return true;}bool search(int num) //判断store[num]节点是否已经扩展过 ,没有扩展返回true{int pre=store[num].father; //pre指向store[num]的父节点位置bool test=true;while(!pre){ //循环直到pre为0,既初始节点for(int i=0;i<3;i++){for (int j=0;j<3;j++){if(store[pre].a[i][j]!=store[num].a[i][j]){test=false;break;}}if(test==false) break;}if(test==true) return false;pre=store[pre].father; //pre继续指向store[pre]父节点位置}return true;}void print(int num) //打印路径,store[num]为目标节点{vector<int> temp; //存放路径int pre=store[num].father;temp.push_back(num);while(pre!=0){ //从目标节点回溯到初始节点temp.push_back(pre);pre=store[pre].father;}cout<<endl;cout<<"*********数码移动步骤*********"<<endl;int mm=1; //步数for(int m=temp.size()-1;m>=0;m--){cout<<"---第"<<mm<<"步---："<<endl;for(int i=0;i<3;i++){for(int j=0;j<3;j++){cout<<store[temp[m]].a[i][j]<<" ";}cout<<endl;}mm++;cout<<endl;}cout<<"所需步数为: "<<store[num].deep<<endl;return;}int get_fn(int num) //返回store[num]的评价函数值{int fn_temp=0; //评价函数值bool test=true;for(int i=0;i<3;i++){ //当找到一个值后,计算这个值位置与目标位置的距离差,test置为false后继续寻找下一个值for(int j=0;j<3;j++){test=true;for(int k=0;k<3;k++){for(int l=0;l<3;l++){if((store[num].x!=i||store[num].y!=j)&&store[num].a[i][j]==store[0].a[k][l]){ //寻值时排除空格位fn_temp=fn_temp+abs(i-k)+abs(j-l);test=false;}if(test==false) break;}if(test==false) break;}}}fn_temp=fn_temp+store[num].deep; //加上节点深度return fn_temp;}void kongxy(int num) //获得空格坐标{for(int i=0;i<3;i++){for(int j=0;j<3;j++){if(store[num].a[i][j]==0){store[num].x=i;store[num].y=j;}}}return;}int main(){cout<<"-----------A*算法解决8数码问题------------"<<endl;while(true){store.clear(); //清空storevector<int> open; //建立open表int i,j,m,n,f;int min; //store[min]储存fn值最小的节点int temp;bool test;top=1; //当前节点在store的位置,初始节点在store[1]int target[9];int begin[9]; //储存初始状态和目标状态,用于判断奇偶int t1=0,t2=0; //初始状态和目标状态的奇偶序数node node_temp;store.push_back(node_temp);store.push_back(node_temp); //用于创建store[0]和store[1],以便下面使用cout<<"请输入初始数码棋盘状态,0代表空格："<<endl; //输入初始状态,储存在store[1]中test=false;while(test==false){f=0;for(i=0;i<3;i++){for(j=0;j<3;j++){cin>>temp;store[1].a[i][j]=temp;begin[f++]=temp;}}test=true;for(i=0;i<8;i++){ //检查是否有重复输入,若有则重新输入for(j=i+1;j<9;j++){if(begin[i]==begin[j]){test=false;break;}}if(test==false) break;}if(test==false) cout<<"输入重复,请重新输入:"<<endl;}kongxy(1); //找出空格的坐标cout<<"请输入目标数码棋盘状态,0代表空格： "<<endl; //输入目标状态,储存在store[0]中test=false;while(test==false){f=0;for(i=0;i<3;i++){for(j=0;j<3;j++){cin>>temp;store[0].a[i][j]=temp;target[f++]=temp;}}test=true;for(i=0;i<8;i++){ //检查是否有重复输入,若有则重新输入for(j=i+1;j<9;j++){if(target[i]==target[j]){test=false;break;}}if(test==false) break;}if(test==false){cout<<"输入重复,请重新输入:"<<endl;continue; //若重复,重新输入}for(i=0;i<9;i++){ //检查目标状态与初始状态是否匹配test=false;for(j=0;j<9;j++){if(begin[i]==target[j]){test=true;break;}}if(test==false) break;}if(test==false) cout<<"输入与初始状态不匹配,请重新输入:"<<endl;}for(i=1;i<9;i++){ //判断奇偶序数是否相同,若不相同则无法找到路径for(j=1;i-j>=0;j++){if(begin[i]>begin[i-j]){if(begin[i-j]!=0) t1++;}}}for(i=1;i<9;i++){for(j=1;i-j>=0;j++){if(target[i]>target[i-j]){if(target[i-j]!=0) t2++;}}}if(!(t1%2==t2%2)){cout<<"无法找到路径."<<endl;cout<<endl;//system("pause");//return 0;continue;}LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);//获取时间Count1double d;store[1].father=0; //初始化参数store[1].gone=0;store[1].deep=0; //初始节点的父节点为0store[1].fn=get_fn(1);if(check(1)){ //判断初始状态与目标状态是否相同print(1);//system("pause");//return 0;cout<<endl;continue;}open.push_back(1); //把初始状态在store中的位置数压入open表中while(!open.empty()){ //当open表不为空时,开始寻找路径if(check(top)) break;min=top;int i_min=0;for(i=0;i<open.size();i++){ //遍历open表中元素,找出store中fn值最小的节点if(store[open[i]].fn<=store[min].fn&&store[open[i]].gone==0){min=open[i];i_min=i;}}store[min].gone=1;open.erase(open.begin()+i_min); //把最小节点标记遍历过,并从open表中删除m=store[min].x;n=store[min].y; //空格坐标for(f=0;f<4;f++){ //上下左右移动空格i=m+mx[f];j=n+my[f];if(i>=0&&i<=2&&j>=0&&j<=2){ //当变换后的空格坐标在矩阵中时,开始移动top++;store.push_back(store[min]); //把store[min]压入store中成为新增节点,位置为store[top]store[top].father=min; //新增节点的父节点为minstore[top].gone=0; //新增节点未被访问store[top].deep=store[min].deep+1; //新增节点的深度为父节点深度+1temp=store[top].a[m][n]; //交换空格与相邻数字store[top].a[m][n]=store[top].a[i][j];store[top].a[i][j]=temp;store[top].x=i; //移动后的空格坐标store[top].y=j;store[top].fn=get_fn(top); //移动后的fn值open.push_back(top); //把top压入open表中if(check(top)){ //检查是否到达目标print(top);//system("pause");//return 0;break;}if(search(top)==false){ //检查新增节点是否被访问过,若访问过,则删除此节点top--;store.pop_back();open.pop_back();}}}}QueryPerformanceCounter(&Count2);//获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;//计算时间差，d的单位为ms.cout<<"算法时间为为"<<d<<" ms."<<endl;cout<<endl;}return 0;system("pause");}。