程序员经验分享-hwhale

A*算法解八数码问题

2023-10-28

1 问题描述

1.1什么是八数码问题

八数码游戏包括一个33的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。与空位相邻的棋子可以滑动到空位中。游戏的目的是要达到一个特定的目标状态。标注的形式化如下：

 

1

2

3

4

5

6

7

8

1.2问题的搜索形式描述

状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

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

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

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

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

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

1.3解决方案介绍

1.3.1 算法思想

估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。估价函数通常由两部分组成，其数学表达式为

f(n)=g(n)+h(n)

其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

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

1.3.2 启发函数

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

2算法介绍

2.1 A*算法的一般介绍

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

A star算法在静态路网中的应用

对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。

2.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表中; //还没有排序}

　　 }//end for

　　将n节点插入CLOSE表中;

　　按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

　　}//end while(OPEN!=NULL)

保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；


判断有无解问题：根据逆序数直接判断有无解，对于一个八数码，依次排列之后，每次是将空位和相邻位进行调换，研究后会发现，每次调换，逆序数增幅都为偶数，也就是不改变奇偶性，所以初始和目标状态的逆序数的奇偶性相同。

3算法实现

3.1实验环境与问题规模

对于８数码问题，每个结点有８个数字和一个空格，可以将空格看成０，那么一共有９个数字，３２位的int可以表示２* 109 ，可以用一个整数表示一个结点对应的信息。计算一个整数中０（即空格）的位置比较耗时间，用一个整数存储当前结点０的位置，还要存储对应的 g , h 值以及该结点由哪个结点扩展来的信息。本实验用C++编写源程序，环境选用Visual Studio 2005。

程序采用文本输入输出，输入文件为astar.in，A*算法输出文件为astar.out，可以用记事本打开。输入格式为一个测试用例由两个中间由一空行隔开的８数码格局组成，输出为对应测试用例的走法路径及相关统计信息，程序假定输入数据符合要求，未做检查。

Astar.in:

2 0 3  //初态

1 8 4

7 6 5

 

1 2 3 // 终态

8 0 4

7 6 5

 

3.2数据结构

3.2.1 open表的数据结构表示
      考虑对open表的操作，每次需要得到所有待扩展结点中 f 值最小的那个结点，用堆进行实现，可以达到O ( log ( heapSize ) ) 时间复杂度。

3.2.2 closed表的数据结构表示
      closed表存储已扩展的结点间的扩展关系，主要用于输出路径。考虑结点扩展的操作，设待扩展的结点为m，由它扩展生成的结点为n1, n2, … 。结点m扩展完成后被放到closed表中，放入后它在closed表中位置不发生变化，可以将n1, n2, …的前驱结点置为m在closed表中的位置，当n1, n2, ..中有结点设为n1被扩展放入closed表时，n1的前驱刚好已经存储好。下面说明closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱结点的下标位置，可以用数组实现，每个结点记录整数表示的８数码格局和它的前驱结点的下标，输出路径时，根据前驱结点形成到达根结点的链条，递归输出即可。

3.2.3 解决结点重复扩展问题
      对于一个结点有多种方式到达该结点，这样就可能多次将它加入open表中，而启发函数满足单调限制条件，后来达到该结点的路径不再是更优的，可以不予考虑。扩展某结点时先看该结点是否已经扩展过，如果扩展过则略过。实现的可以线形遍历closed表，但效率不高时间复杂度为O ( closedSize)，考虑每个结点可以用一个整数标识，用二叉平衡查找树可以得到更好的时间复杂度O ( log (closedSize) ) ，程序中用基于红黑树思想的set实现。

3.3 实验结果

 

输入数据（0表示空格）

步数

扩展结点数

生成结点数

搜索用时(毫秒)

3 1 2 4 0 5 6 7 8

2

5

11

0

3 1 2 4 7 5 6 8 0

4

17

28

0

3 7 2 8 1 5 4 6 0

无解

 

 

 

1 2 3 4 5 6 7 8 0

22

7943

12019

2266

参考文献

王勋，凌云，费玉莲.2005.人工智能导论.北京：科学出版社

广树建，王钰淇.2008.新编C/C++程序设计教程.广州：华南理工大学出版社

王文杰，史忠植.2007.人工智能原理辅导与练习.北京：清华大学出版社出

附录—源代码及其注释

源代码及测试数据
/*
        算法：        A*
        是否最优解：是
        启发函数：   每一个数字位与目标中该数字位的距离，满足单调限制。说明：A*算法是启发式搜索算法，搜索时充分利用当前状态距目标距离远近的启发信息，选取当前未扩展结点中估价函数最小的进行扩展，生成结点数少，搜索空间较小，实现稍复杂，
        备注：       程序未对输入数据进行检查
*/

[cpp]  view plain  copy   在CODE上查看代码片 派生到我的代码片
  1. #pragma warning(disable:4786)   
  2. #include <algorithm>   
  3. #include <cstdio>   
  4. #include <set>   
  5. #include <utility>   
  6. #include <ctime>   
  7. #include <cassert>   
  8. #include <cstring>   
  9. #include <iostream>  
  10. using namespace std;  
  11.   
  12. /*item记录搜索空间中一个结点          
  13. state 记录用整数形式表示的8数码格局           
  14. blank 记录当前空格位置，主要用于程序优化， 
  15. 扩展时可不必在寻找空格位置          
  16. g, h  对应g(n), h(n)           
  17. pre   记录当前结点由哪个结点扩展而来 */  
  18. struct item    
  19. {            
  20.     int state;            
  21.     int blank;           
  22.     int g;           
  23.     int h;             
  24.     int pre;   
  25. };  
  26.   
  27. const int MAXSTEPS = 100000;   
  28. const int MAXCHAR = 100;   
  29. char buf[MAXCHAR][MAXCHAR]; //open表   
  30. item open[MAXSTEPS];   
  31. //vector<item> open;  
  32. int steps = 0;  
  33.   
  34. //closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径   
  35. //每次只需得到对应f值最小的待扩展结点，用堆实现提高效率  
  36. pair<int, int> closed[MAXSTEPS];  
  37. //读入，将8数码矩阵格局转换为整数表示   
  38.   
  39. bool read(pair<int,int> &state)   
  40. {            
  41.     if (!gets(buf[0]))                   
  42.         return false;           
  43.     if (!gets(buf[1]))                   
  44.         return false;           
  45.     if (!gets(buf[2]))                   
  46.         return false;   
  47.   
  48.     //cout << strlen(buf[0]) << ' ' << strlen(buf[1]) << ' ' << strlen(buf[2]) << endl;  
  49.     assert(strlen(buf[0]) == 5 && strlen(buf[1]) == 5 && strlen(buf[2]) == 5);  
  50.     // astar.in中的每行数据长度必须为5  
  51.     state.first = 0;  
  52.     for (int i = 0, p = 1; i < 3; ++i)           
  53.     {                    
  54.         for (int j = 0; j < 6; j += 2)                    
  55.         {                            
  56.             if (buf[i][j] == '0')                                    
  57.                 state.second = i * 3 + j / 2;     // state.second为0（空格）在节点中的位置                      
  58.             else                                    
  59.                 state.first += p * (buf[i][j] - '0');                  
  60.             p *= 10;                   
  61.         }           
  62.     }  
  63.   
  64.     /* 若初试节点为:    
  65.     1 2 3 
  66.     8 0 4 
  67.     7 6 5 
  68.     则state.first为567408321，state.second为4 
  69.     */  
  70.     return true;  
  71. }  
  72.   
  73. //计算当前结点距目标的距离   
  74. int calculate(int current, int target)  // return h=the sum of distances each block have to move to the right position,这里的each block不包括空格  
  75. {            
  76.     int c[9], t[9];           
  77.     int i, cnt = 0;            
  78.     for (i = 0; i < 9; ++i)           
  79.     {                    
  80.         c[current % 10] = t[target % 10] = i;                   
  81.         current /= 10;                  
  82.         target /= 10;           
  83.     }    
  84.   
  85.     for (i = 1; i < 9; ++i)                    
  86.         cnt += abs(c[i] / 3 - t[i] / 3) + abs(c[i] % 3 - t[i] % 3);           
  87.   
  88.     return cnt;   
  89. }  
  90.   
  91. //open表中结点间选择时的规则 f(n) = g(n) + h(n)  
  92.   
  93. class cmp   
  94. {   
  95. public: inline bool operator()(item a, item b)           
  96.         {                    
  97.             return a.g + a.h > b.g + b.h;           
  98.         }   
  99. };   
  100.   
  101. //将整数形式表示转换为矩阵表示输出  
  102. void pr(int state)   
  103. {            
  104.     memset(buf, ' ', sizeof(buf));           
  105.     for (int i = 0; i < 3; ++i)           
  106.     {                    
  107.         for (int j = 0; j < 6; j += 2)                   
  108.         {                            
  109.             if (state % 10)  
  110.                 buf[i][j] = state % 10 + '0';                           
  111.             state /= 10;                   
  112.         }         
  113.   
  114.         buf[i][5] = '\0';                   
  115.         puts(buf[i]);  
  116.     }  
  117. }  
  118.   
  119. //用于判断当前空格是否可以向对应方向移动  
  120. inline bool suit(int a, int b)  //空格移动后的坐标为(a,b)  
  121. {            
  122.     return (a >= 0 && a < 3 && b >= 0 && b < 3);   
  123. }   
  124.   
  125.   
  126. //递归输出搜索路径  
  127. void path(int index)   
  128. {            
  129.     if (index == 0)           
  130.     {                    
  131.         pr(closed[index].first);                   
  132.         puts("");                   
  133.         return;           
  134.     }            
  135.     path(closed[index].second);           
  136.     pr(closed[index].first); //将整数形式表示转换为矩阵表示输出           
  137.     puts("");           
  138.     ++steps;   
  139. }  
  140.   
  141. int getNixuNum( int state ) //求节点的逆序对数  
  142. {  
  143.     int sum = 0;  
  144.     int result[9];  
  145.     memset( result, 0, sizeof(result) );  
  146.     //cout << result[8] << result[7] << endl;  
  147.   
  148.     char buf[10];  
  149.     itoa( state, buf, 10 );  
  150.     //cout << buf << endl;  
  151.     int k = 0;  
  152.     while( buf[k] != '\0' )  
  153.     {  
  154.         result[9-k-1] = buf[k] - '0';  
  155.         k++;  
  156.     }  
  157.       
  158.     for( int i = 0; i < 9; i++ )  
  159.     {  
  160.         for( int j = i + 1; j < 9; j++ )  
  161.         {  
  162.             if( result[i] && result[j] && result[i] > result[j] )  
  163.             {  
  164.                 sum++;  
  165.             }  
  166.         }  
  167.     }  
  168.     return sum; //返回3*3方格数组的逆序对数  
  169. }  
  170.   
  171. int main()   
  172. {      
  173.     //cout << getNixuNum(87654321);  
  174.     //open.resize(MAXSTEPS);  
  175.     unsigned int t1 = clock();      
  176.     //cout << open.size() << endl;  
  177.     if( freopen("astar.in", "r", stdin) == NULL )   
  178.     {  
  179.         cout << "file not find\n";  
  180.         exit(0);  
  181.     };      
  182.   
  183.     freopen("astar2.out", "w", stdout);           
  184.     set<int>states;           
  185.     char tmp[100];            
  186.     int i, x, y, a, b, nx, ny, end, next, index, kase = 0;           
  187.     pair<int,int> start, target;           
  188.     item head;          //4个方向移动时的偏移量            
  189.     const int xtran[4] = {-1, 0, 1, 0};           
  190.     const int ytran[4] = {0, 1, 0, -1};            
  191.     const int p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};  
  192.   
  193.     while (read(start))  // 读取初试状态节点         
  194.     {                    
  195.         unsigned int t2 = clock();                    
  196.         printf("Case %d:\n\n", ++kase);                   
  197.         gets(tmp);                   
  198.         read(target);  // 读取目标状态节点            
  199.         gets(tmp);   
  200.   
  201.         int targetNixuNum = getNixuNum(target.first);  
  202.         //若两者的逆序对数不是同为奇数或同为偶数，则无解  
  203.         if( !(getNixuNum(start.first)&1 && targetNixuNum&1 || !(getNixuNum(start.first)&1) && !(targetNixuNum&1)) )  
  204.         {  
  205.             cout << "无法从初始节点到终态节点\n";  
  206.             exit(0);  
  207.         }  
  208.         //初始化open表，将初始状态加入  
  209.         open[0].state = start.first;                    
  210.         open[0].h = calculate(start.first, target.first); // 计算当前节点到目标节点的估计距离                  
  211.         open[0].blank = start.second;                   
  212.         open[0].pre = -1;    // 初始节点无父节点               
  213.         open[0].g = 0;  // 初始节点的g为0                 
  214.         index = 0;                    
  215.         states.insert(start.first); // 扩展过节点保存在states中，即出现过的状态保存在states中，states为set<int>类型，其中的states中的元素唯一  
  216.   
  217.         //提取open表中f值最小元素放入closed表，并对该结点进行扩展  
  218.         for (end = 1; end > 0; ++index)   // end为open表中的元素个数，一直循环到open表为空                
  219.         {                            
  220.             assert(index < MAXSTEPS);         
  221.             //临时存储                           
  222.             head = open[0]; // 由于使用pop_heap函数和push_heap函数，所以open[0]为g+h最小的元素  
  223.   
  224.             //放入closed表记录当前格局和由哪个结点扩展而来（该结点肯定已在closed表中）  
  225.             closed[index].first = open[0].state; //放入close表中，表示已经扩展完的节点，下面的for循环会扩展其节点                           
  226.             closed[index].second = open[0].pre; // index表示当前close表中当前扩展节点的下标  
  227.             //从open表中删除该结点                            
  228.             pop_heap(open, open + end, cmp());//为algorithm文件中的函数，第一个参数指定开始位置，第二个指定结束，第三个指定比较函数                           
  229.             --end;        
  230.   
  231.             //得到结果，递归输出路径  
  232.             if (head.state == target.first)                           
  233.             {                                    
  234.                 path(index);                                   
  235.                 break;                           
  236.             }  
  237.   
  238.             x = head.blank / 3;                           
  239.             y = head.blank % 3; //空格在3*3方格中的x,y坐标  
  240.             /* 
  241.                 |2 0 3| 
  242.             A = |1 8 4| 
  243.                 |7 6 5| // 看成3*3的数组 
  244.             则head.blank=1 
  245.             x=0,y=1,即空格的在3*3的数组中下标为(0,1) 
  246.             */  
  247.             for (i = 0; i < 4; ++i)                           
  248.             {                                    
  249.                 nx = x + xtran[i];                                   
  250.                 ny = y + ytran[i];     
  251.                 /* 
  252.                 i=0时：(nx,ny）为当前空格向上移动一格后的坐标 
  253.                 i=1时：(nx,ny）为当前空格向右移动一格后的坐标 
  254.                 i=2时：(nx,ny）为当前空格向下移动一格后的坐标 
  255.                 i=3时：(nx,ny）为当前空格向左移动一格后的坐标 
  256.                 */  
  257.                 if (suit(nx, ny)) // 判断是否能够移动  
  258.                 {                                            
  259.                     a = head.blank; // 空格当前位置,以上面矩阵A为例，a=1                                         
  260.                     b = nx * 3 + ny; // 空格移动后的新位置,开始是能够向右边移动，故b=0*3+2=2                                          
  261.                     //调换十进制表示整数对应两个数字位                                            
  262.                     next = head.state + ((head.state % p[a + 1]) / p[a] - (head.state % p[b + 1]) / p[b]) * p[b]  + ((head.state % p[b + 1]) / p[b] - (head.state % p[a + 1]) / p[a]) * p[a];     
  263.                     // 如head.state=567481302,空格向右移动一次后，next=567481032,即为移动后的节点  
  264.                       
  265.                     // 判断能否由当前节点到达目标节点  
  266.                     if( ( getNixuNum(next)&1 && targetNixuNum&1 ) || ( !(getNixuNum(next)&1) && !(targetNixuNum&1) ) )  
  267.                     {  
  268.                         //判断是否已经扩展过，即已经出现过  
  269.                         if (states.find(next) == states.end()) //没出现就保存一下，也存入open表                                          
  270.                         {                                                    
  271.                             states.insert(next);                                                       
  272.                             open[end].pre = index; //扩展后的子节点，其父节点为当前扩展节点                                                  
  273.                             open[end].blank = b;                                                   
  274.                             open[end].state = next;                                                    
  275.                             open[end].h = calculate(next,target.first);   
  276.                             open[end].g  = head.g + 1;    
  277.                             ++end;  //open表中元素加1                                                  
  278.                             push_heap(open, open + end, cmp());    //压入堆中                                       
  279.                         }             
  280.                     }  
  281.                                             
  282.                 }                           
  283.             }                   
  284.         }   
  285.   
  286.         if (end <= 0)                            
  287.             puts("No solution");  
  288.         else                   
  289.         {                            
  290.             printf("Num of steps: %d\n", steps);                            
  291.             printf("Num of expanded: %d\n", index);                           
  292.             printf("Num of generated: %d\n", index + end);                           
  293.             printf("Time consumed: %d\n\n", clock() - t2);                   
  294.         }   
  295.   
  296.         states.clear();                   
  297.         steps = 0;           
  298.     }            
  299.     printf("Total time consumed: %d\n", clock() - t1);           
  300.     return 0;  
  301. }  

测试：

输入文件：astar.in

输出文件：astar2.out


astar.in文件内容：

3 1 2
4 0 5
6 7 8

0 1 2
3 4 5
6 7 8

1 2 3
4 5 6
7 8 0

0 1 2
3 4 5
6 7 8

注：上面前两个3*3矩阵为第一个测试案例，其中第一个3*3为初态节点，第二个3*3为终态节点，后面两个3*3矩阵为第二个测试案例，

其中第一个3*3为初态节点，第二个3*3为终态节点，各个矩阵之间需要空一行


测试案例1：

astar.in:

3 1 2
4 0 5
6 7 8

0 1 2
3 4 5
6 7 8


astar2.out:

Case 1:

3 1 2
4   5
6 7 8

3 1 2
  4 5
6 7 8

  1 2
3 4 5
6 7 8

Num of steps: 2
Num of expanded: 2
Num of generated: 6
Time consumed: 64

Total time consumed: 92


测试案例2：

astar.in:

3 7 2
8 1 5
4 6 0

0 1 2
3 4 5
6 7 8

astar2.out:

Case 1:

无法从初始节点到终态节点

注：astar.in中每一行数据长度只能是5,0表示空格


测试案例3：

astar.in:

1 2 3
4 5 6
7 8 0

0 1 2
3 4 5
6 7 8

astar2.out:

Case 1:

1 2 3
4 5 6
7 8  

1 2 3
4 5 6
7   8

1 2 3
4   6
7 5 8

1 2 3
4 6  
7 5 8

1 2  
4 6 3
7 5 8

1   2
4 6 3
7 5 8

  1 2
4 6 3
7 5 8

4 1 2
  6 3
7 5 8

4 1 2
6   3
7 5 8

4 1 2
6 3  
7 5 8

4 1  
6 3 2
7 5 8

4   1
6 3 2
7 5 8

4 3 1
6   2
7 5 8

4 3 1
6 5 2
7   8

4 3 1
6 5 2
  7 8

4 3 1
  5 2
6 7 8

  3 1
4 5 2
6 7 8

3   1
4 5 2
6 7 8

3 1  
4 5 2
6 7 8

3 1 2
4 5  
6 7 8

3 1 2
4   5
6 7 8

3 1 2
  4 5
6 7 8

  1 2
3 4 5
6 7 8

Num of steps: 22
Num of expanded: 1104
Num of generated: 1742
Time consumed: 123

Total time consumed: 126


转载来源：http://wenku.baidu.com/view/87c92ef1ba0d4a7302763a29.html


八数码问题的另一个实现：

[cpp]  view plain  copy   在CODE上查看代码片 派生到我的代码片
  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<cstring>  
  4. #include<algorithm>  
  5. #include<queue>  
  6. #include<vector>  
  7. #include<cmath>  
  8. #include<map>  
  9. #include<string>  
  10. #define inf 1<<30  
  11. #define eps 1e-7  
  12. #define LD long double  
  13. #define LL long long  
  14. #define maxn 1000000005  
  15. using namespace std;  
  16. struct Node{  
  17.     int maze[3][3];   //八数码具体情况   
  18.     int h,g;    //两个估价函数  
  19.     int x,y;   //空位的位置  
  20.     int Hash;   //HASH值  
  21.     bool operator<(const Node n1)const{     //优先队列第一关键字为h,第二关键字为g  
  22.         return h!=n1.h?h>n1.h:g>n1.g;  
  23.     }  
  24.     bool check(){    //判断是否合法  
  25.         if(x>=0&&x<3&&y>=0&&y<3)  
  26.             return true;  
  27.         return false;  
  28.     }  
  29. }s,u,v,tt;  
  30. int HASH[9]={1,1,2,6,24,120,720,5040,40320};   //HASH的权值  
  31. int destination=322560;   //目标情况的HASH值   
  32. /* 
  33. 目标状态： 
  34. 1 2 3 
  35. 4 5 6  
  36. 7 8 0 
  37. 其hash值为322560 
  38. */  
  39. int vis[400000];            //判断状态已遍历，初始为-1，否则为到达这步的转向  
  40. int pre[400000];        //路径保存  
  41. int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};   //四个方向  
  42. void debug(Node tmp){  
  43.     for(int i=0;i<3;i++){  
  44.         for(int j=0;j<3;j++)  
  45.             printf("%d ",tmp.maze[i][j]);  
  46.         printf("\n");  
  47.     }  
  48.     printf("%d %d\n%d %d\n",tmp.x,tmp.y,tmp.g,tmp.h);  
  49.     printf("hash=%d\n",tmp.Hash);  
  50. }  
  51. int get_hash(Node tmp){    //获得HASH值  
  52.     int a[9],k=0;  
  53.     for(int i=0;i<3;i++)  
  54.         for(int j=0;j<3;j++)  
  55.             a[k++]=tmp.maze[i][j];  
  56.     int res=0;  
  57.     for(int i=0;i<9;i++){  
  58.         int k=0;  
  59.         for(int j=0;j<i;j++)  
  60.             if(a[j]>a[i])  
  61.                 k++;  
  62.         res+=HASH[i]*k;  
  63.     }  
  64.     return res;  
  65. }  
  66.   
  67. bool isok(Node tmp){    //求出逆序对，判断是否有解  
  68.     int a[9],k=0;  
  69.     for(int i=0;i<3;i++)  
  70.         for(int j=0;j<3;j++)  
  71.             a[k++]=tmp.maze[i][j];  
  72.     int sum=0;  
  73.     for(int i=0;i<9;i++)  
  74.         for(int j=i+1;j<9;j++)  
  75.             if(a[j]&&a[i]&&a[i]>a[j])  
  76.                 sum++;  
  77.     return !(sum&1);    //由于目标解为偶数，所以状态的逆序数为偶数才可行,交换空格，逆序数增幅为偶数，故初始节点和目标的节点的逆序数奇偶性相同  
  78. }  
  79.   
  80. int get_h(Node tmp){   //获得估价函数H  
  81.     int ans=0;  
  82.     for(int i=0;i<3;i++)  
  83.         for(int j=0;j<3;j++)  
  84.             if(tmp.maze[i][j])  
  85.                 ans+=abs(i-(tmp.maze[i][j]-1)/3)+abs(j-(tmp.maze[i][j]-1)%3);  
  86.     return ans;  
  87. }  
  88. void astar(){    //搜索  
  89.     priority_queue<Node>que;  
  90.     que.push(s);  
  91.     while(!que.empty()){  
  92.         u=que.top();  
  93.         que.pop();  
  94.         for(int i=0;i<4;i++){  
  95.             v=u;  
  96.             v.x+=way[i][0];  
  97.             v.y+=way[i][1];  
  98.             if(v.check()){  
  99.                 swap(v.maze[v.x][v.y],v.maze[u.x][u.y]);   //将空位和相邻位交换  
  100.                 v.Hash=get_hash(v);             //得到HASH值  
  101.                 if(vis[v.Hash]==-1&&isok(v)){   //判断是否已遍历且是否可行，后者可以不要  
  102.                     vis[v.Hash]=i;           //保存方向  
  103.                     v.g++;;                  //已花代价+1  
  104.                     pre[v.Hash]=u.Hash;     //保存路径  
  105.                     v.h=get_h(v);           //得到新的估价函数H  
  106.                     que.push(v);     //入队  
  107.                 }  
  108.                 if(v.Hash==destination)  
  109.                     return ;  
  110.             }  
  111.         }  
  112.     }  
  113. }  
  114. void print(){  
  115.     string ans;  
  116.     ans.clear();  
  117.     int nxt=destination;  
  118.     while(pre[nxt]!=-1){  //从终点往起点找路径  
  119.         switch(vis[nxt]){   //四个方向对应  
  120.         case 0:ans+='r';break;  
  121.         case 1:ans+='l';break;  
  122.         case 2:ans+='d';break;  
  123.         case 3:ans+='u';break;  
  124.         }  
  125.         nxt=pre[nxt];     
  126.     }  
  127.     for(int i=ans.size()-1;i>=0;i--)  
  128.         putchar(ans[i]);  
  129.     puts("");  
  130. }  
  131. int main(){  
  132.     Node test;  
  133.     /*int value = 0; 
  134.     for( int i = 0; i < 3; i++ ) 
  135.     { 
  136.         for( int j = 0; j < 3; j++ ) 
  137.         { 
  138.             test.maze[i][j] = value++; 
  139.         } 
  140.     }*/  
  141.   
  142.     //cout << get_hash(test) << endl;  
  143.       
  144.     char str[100];  
  145.     while(gets(str)!=NULL){  
  146.         int k=0;  
  147.         memset(vis,-1,sizeof(vis));  
  148.         memset(pre,-1,sizeof(pre));  
  149.         for(int i=0;i<3;i++)  
  150.             for(int j=0;j<3;j++){  
  151.                 if((str[k]<='9'&&str[k]>='0')||str[k]=='x'){  
  152.                     if(str[k]=='x'){  
  153.                         s.maze[i][j]=0;  
  154.                         s.x=i;  
  155.                         s.y=j;  
  156.                     }  
  157.                     else  
  158.                         s.maze[i][j]=str[k]-'0';  
  159.                 }  
  160.                 else  
  161.                     j--;  
  162.                 k++;  
  163.             }  
  164.             if(!isok(s)){   //起始状态不可行  
  165.                 printf("unsolvable\n");  
  166.                 continue;  
  167.             }  
  168.             s.Hash=get_hash(s);  
  169.             if(s.Hash==destination){   //起始状态为目标状态  
  170.                 puts("");  
  171.                 continue;  
  172.             }  
  173.             vis[s.Hash]=-2;  
  174.             s.g=0;s.h=get_h(s);  
  175.             astar();  
  176.             print();  
  177.     }  
  178.     return 0;  
  179. }  
  180.   
  181. /* 
  182. 输入格式： 
  183. 1234567x8表示：x代表空格，0表示空格 
  184. 1 2 3 
  185. 4 5 6 
  186. 7 0 8 
  187. 终态： 
  188. 1 2 3 
  189. 4 5 6 
  190. 7 8 0 
  191. */  

转载来源： http://blog.csdn.net/acm_cxlove/article/details/7745323

人工智能A*课件：

http://wenku.baidu.com/link?

url=1TbH7biYFTuyNVE65fy26uXLbnRRNwe9Flhy6dFwX6gs42Sp919efN6uoJWKm_tJNNv1MNl2pGkVGxl3OZz1v1rtY4Ge98m6LPfiG6Ms47G

http://www.docin.com/p-506506343.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法

代码

A*算法解八数码问题 的相关文章

随机推荐

  • OAuth基础介绍

    什么是OAuth OAuth是为解决应用之间 网站之间互相访问的一种简单 标准 安全的API授权协议 官网对其的定义 An open protocol to allow secure API authorization in a simpl

  • 面试题 03.02. 栈的最小值-辅助栈做法

    面试题 03 02 栈的最小值 请设计一个栈 除了常规栈支持的pop与push函数以外 还支持min函数 该函数返回栈元素中的最小值 执行push pop和min操作的时间复杂度必须为O 1 示例 MinStack minStack new

  • 计算梯度的三种方法： 数值法，解析法，反向传播法

    coding gbk function f x y z x y z first method 解析法 def grad1 x y z dx z dy z dz x y return dx dy dz second method 数值法 de

  • List接口及其实现类

    List接口 鉴于Java中数组用来存储数据的局限性 我们通常使用List替代数组 List集合类中元素有序 且可重复 集合中的每个元素都有其对应的顺序索引 List容器中的元素都对应一个整数型的序号记载其在容器中的位置 可以根据 序号存取

  • Linux无法连通外网情况下缺少依赖（CentOS7环境）

    在有外网的情况下 可以用yum很容易的完成服务及其相关依赖的安装 而由于客户要求 导致生产服务器上无法连通外网 于是在搭建生产环境的时候 由于外网不通 导致缺少依赖的问题频频出现 现将解决此类问题的方法归纳如下 直接下载 此方法适用于缺少单

  • GD32F103调试小记(二)之USART(接收中断、接收空闲中断+DMA、发送DMA)

    前言 上篇文章摸完了GD32F103调试小记 一 之ADC DMA 接下来摸下GD32的USART DMA 数据的搬运工 CPU的好助手 USART 一种串行通信协议 说白了就是让两根线按照一定的规律去切换高低电平 根据一个单位时间内高低电

  • Linux基础—系统结构介绍（一）

    一 系统结构由内核 shell 文件系统 应用程序一起组合而成的文件操作系统 它们使得用户可以运行程序 管理文件 资源调度 计算 1 Linux 内核由如下几部分组成 SCI 层系统调用接口 虚拟文件系统 内存管理 进程管理 设备驱动程序

  • Ubuntu下 Hyperledger Farbic 环境配置

    Hyperledger Farbic Hyperledger作为IBM旗下主推的区块链 是首个面向企业的开放区块链技术的重要探索 现阶段也推出了1 0稳定版本 虽然IBM也有相关的配置文档 并且完善度十分高 但是依旧有些坑点 配置目录 以下

  • 人脸检测算法YuNet再次提升，参数量降至54K

    我们的人脸检测项目libfacedetection是2015年创建的开源项目 算法模型为YuNet 已经持续维护8年至今 在GitHub上已经获得11 7K星 欢迎大家三连 使用 反馈和建议 2022 2023年我们对训练部分进行了大幅改进

  • 让安全动起来

    山石网科带你 分分钟拿下靶标 一 信息收集 信息收集是整个攻击流程当中最重要的一步 从 web 入手 首先需要收集子域名 可以通过枚举的方式收集子域名 例如经典的 layzer子域名挖掘机 另外还可以通过搜索引擎收集子域名 例如 fofa

  • js对数据进行加密（账户密码加密）@莫成尘

    先看代码 复制使用即可 这是一个比较常用的场景我们借助了 crypto es gt vue3 crypto es gt vue2 库 如您满意请给莫成尘点个star 将他封装为单独的js文件 import CryptoJS from cry

  • Fabric CA国密版本的一种替代方案--使用cryptogen工具增加新用户

    在Fabric超级账本中 如果我们想动态增加用户发行证书 一般会使用Fabric CA或者其它CA 然而在国密改造场景中 当前缺乏可用的开源的Fabric CA国密版本 因此 笔者研究了一下 发现了一种可不使用CA直接使用cryptogen

  • 7-2 交换最小值和最大值 (15分)

    7 2 交换最小值和最大值 15分 本题要求编写程序 先将输入的一系列整数中的最小值与第一个数交换 然后将最大值与最后一个数交换 最后输出交换后的序列 注意 题目保证最大和最小值都是唯一的 输入格式 输入在第一行中给出一个正整数N 10 第

  • Chapter5 --Clocks（时钟及虚拟时钟）

    文章目录 5 3 create clock 5 3 1 Specifying Clock Period 5 3 2 Identifying the Clock Source 5 3 3 Naming the Clock 5 3 4 Spec

  • 操作系统处理机调度及常见的调度算法

    处理机调度的层次 高级调度 高级调度又称为作业调度或长程调度 其主要功能是根据某种算法 把外存上处于后备队列中的那些作业调入内存 也就是说 它的调度对象是作业 中级调度 又称为中程调度 引入中程调度的目的是为了提高内存利用率和系统吞吐量 中

  • IDEA与IDEA（2020.1版本)的安装

    DEA简介 IDEA 全称 IntelliJ IDEA 是 Java 语言开发的集成环境 IntelliJ 在业界被公认为最好的 Java 开发工具之一 IDEA 是 JetBrains 公司的产品 这家公司总部位于捷克共和国的首都布拉格

  • elementUI中的el-date-picker日期月份时间选择器禁用

    1 时间选择器禁用 当开始时间已经选择时 结束时间不能小于开始时间 即禁用结束时间选择器中开始时间前 反之亦然 template内容

  • 【HarmonyOS】实现将pcm音频文件进行编码并写入文件（API6 Java）

    关键字 音频编码 管道模式 createEncoder 写在前面 在使用API6开发HarmonyOS应用时 如何将pcm源文件进行编码并写入文件 最后生成aac文件 本文直接附上主要代码开发步骤供大家参考 主要功能代码 import oh

  • 现阶段项目介绍及电脑网络/RFID/NFC概述

    现阶段项目介绍及电脑网络 RFID NFC概述 文章目录 现阶段项目介绍及电脑网络 RFID NFC概述 1 现阶段项目介绍和行业前景 2 RFID 1 RFID概述 2 应用 3 技术及性能参数 4 使用风险 3 NFC 1 概述 2 工

  • A*算法解八数码问题

    1 问题描述 1 1什么是八数码问题 八数码游戏包括一个33的棋盘 棋盘上摆放着8个数字的棋子 留下一个空位 与空位相邻的棋子可以滑动到空位中 游戏的目的是要达到一个特定的目标状态 标注的形式化如下 1 2 3 4 5 6 7 8 1 2问

热门标签