启发式搜索八数码问题

1、启发式搜索1 .介绍八数码问题也称为九宫问题。在3X3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示)，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2 .使用启发式搜索算法求解8数码问题。1 ) A , A星算法采用估价函数其中：d (n )是搜索树中结点n的深度；w(n )为结点n的数据库中错放的棋子个数；p(

2、n )为结点n的数据库中每个棋子与其目标位置之间的距离总和。2 )宽度搜索采用f(i)为i的深度，深度搜索采用f(i)为i的深度的倒数。3 .算法流程 把起始节点S放到OPEN表中，并计算节点 S的f(S)； 如果OPEN是空表，则失败退出，无解； 从OPEN表中选择一个f值最小白节点i。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ;把节点i从OPEN表中移出，并把它放入 CLOSED的已扩展节点表中； 如果i是个目标节点，则成功退出，求得一个解； 扩展节点i ,生成其全部后继节点。对于 i的每一个后继节点j :计算f(j)；如果j既

3、不在OPEN表中，又不在 CLOCED表中，则用估价函数 f把 它添入OPEN表中。从j加一指向其父节点i的指针，以便一旦找到目标节点时记住一个解 答路径；如果j已在OPEN表或CLOSED表中，则比较刚刚对 j计算过的f和前面计算过 的该节点在表中的 f值。如果新的f较小，则(I)以此新值取代旧值。(II)从j指向i ,而不是指向他的父节点。(III)如果节点j在CLOSED表中，则把它移回 OPEN表中。转向，即GOTO)。4 .估价函数计算一个节点的估价函数，可以分成两个部分：1、已经付出的代价(起始节点到当前节点)；2、将要付出的代价(当前节点到目标节点)。节点n的估价函数f(n)定义

4、为从初始节点、经过 n、到达目标节点的路径的最小代价 一 * , 、 * * 的估计值，即 f (n) = g (n) + h (n)。 * g (n)是从初始节点到达当前节点 n的实际代价； * . . . . . . . . . .h (n)是从节点n到目标节点的最佳路径的估计代价， 体现出搜索过程中采用的启发式 信息(背景知识)，称之为启发函数。* 一 . 、 . 一 . . . . 一 . . g (n)所占的比重越大，越趋向于宽度优先或等代价搜索；反之， h (n)的比重越大, 表示启发性能就越强。5 .实验代码1 |2 | 3| ；8 4 S为方便起见，目标棋局为不变/ U J 窿

5、(1)以下代码估价函数为深度+错放棋子个数(2)若估价函数为深度+每个棋子与其目标位置之间的距离总和，则加入估价函数int calvalue1(int a)/ 不在位棋子数(int c = 0;int b=0;for (int i = 0;i <= 8;i+)for (int j = 0;j <= 8;j+)if (ai = goalj)if (goalj != 0)c=c+abs(i%3-j%3)+abs(i- i%3)/3+(j- j%3)/3);return c;(3)宽度搜索采用 OPEN->jiedian.f = depth;(4)深度搜索采用 OPEN->j

6、iedian.f = -depth;源代码：1. #include "stdio.h"2.3. int goal9 = 1,2,3,8,0,4,7,6,5 , sgoal9;/goal为棋盘的目标布局，并用中间状态 sgoal与之比较4.5. struct Board6. 7. int shuzu9;8. int d, f, e;/d:深度;f:启发函数；e:记录前一次的扩展节点9. ;10.11. struct NodeLink12. 13. Board jiedian;14. NodeLink *parent;15. NodeLink "previous;16

7、. NodeLink *next;17. NodeLink *path;18. ;19. 更新纪录八数码的状态20. void setboard(int a, int b, int flag) /flag=0,写棋子;flag=1,写棋盘21. 22. for (int i = 0;i <= 8;i+)23. if (flag)24. abi = i;25. else26. bai = i;27. 28. 计算启发值的函数29. int calvalue(int a)不在位棋子数30. 31. int c = 0;32. for (int i = 0;i <= 8;i+)33. i

8、f (ai != goali)34. if (goali != 0)35. c+;36. return c;37. 38. 生成一个新节点的函数39. NodeLink *newnode(NodeLink *TEM, int depth, int flag)40. 41. NodeLink *temp = new NodeLink;42. for (int i = 0;i <= 8;i+)43. temp->jiedian.shuzui = TEM->jiedian.shuzui;44. switch (flag)45. 46. case 1:47. 48. temp->

9、;jiedian.shuzu0-;49. temp->jiedian.shuzusgoaltemp->jiedian.shuzu0+;向左移50. break;51. 52. case 2:53. 54. temp->jiedian.shuzu0+;55. temp->jiedian.shuzusgoaltemp->jiedian.shuzu0-;向右移56. break;57. 58. case 3:59. 60. temp->jiedian.shuzu0 -= 3;61. temp->jiedian.shuzusgoaltemp->jiedi

10、an.shuzu0 += 3;向上移62. break;63. 64. case 4:65. 66. temp->jiedian.shuzu0 += 3;67. temp->jiedian.shuzusgoaltemp->jiedian.shuzu0 -= 3;向下移68. break;69. 70. 71. temp->jiedian.d = depth + 1;72. setboard(sgoal, temp->jiedian.shuzu, 1);73. temp->jiedian.f = temp->jiedian.d + calvalue(sg

11、oal);74. temp->jiedian.e = flag;75. temp->parent = TEM;76. return temp;77. 78. 把新节点加入OPEN队列79. NodeLink *addnode(NodeLink *head, NodeLink *node) 把 node 插入至U head链中80. 81. NodeLink *TEM;82. TEM = head;83. head = node;84. head->next = TEM;85. head->previous = NULL;86. if (TEM)87. TEM->p

12、revious = head;/TEM 已为空，无需操作88. return head;89. 90.91. 求启发值最小的结点92. NodeLink *minf(NodeLink *head)93. 94. NodeLink *min, *forward;95. min = head;96. forward = head;97. while (forward)98. 99. if (min->jiedian.f>forward->jiedian.f)100. min = forward;101. forward = forward->next;102. 103. r

13、eturn min;104. 105.106. int main()107. 108. int depth = 0;109. int source9;110. int i, j;111.112. NodeLink *OPEN =new NodeLink;113. NodeLink *TEMP, *TEM;114.115. printf("请输入初始状态：n");116. for (i = 0;i<9;i+)117. scanf_s("%d", &sourcei);118.119. setboard(source, OPEN->jied

14、ian.shuzu, 0);120. OPEN->jiedian.d = depth;121. OPEN->jiedian.e = 0;122. OPEN->jiedian.f = depth + calvalue(source);123. OPEN->next = NULL;124. OPEN->previous = NULL;125. OPEN->parent = NULL;126.127. while (OPEN)128. 求具有最129. TEMP = minf(OPEN);小启发值的节点130. setboard(sgoal, TEMP->j

15、iedian.shuzu, 1);写棋盘131. if (!calvalue(sgoal)132. break;133. if (TEMP != OPEN)如果不是第一个节点134. 135. TEMP->previous->next= TEMP->next;136. TEMP->next->previous=TEMP->previous;137. 138. else是第一个节点139.(140.if (OPEN->next)如果还有节点141.(142.OPEN = OPEN->next;143.OPEN->previous = NULL

16、;144.145.else OPEN = NULL;否贝空146.147.148.if (TEMP->jiedian.shuzu0 - 1 >= 0 && TEMP->jiedian.e != 2)子回到原状态149.OPEN = addnode(OPEN, newnode(TEMP, depth, 1);150.if (TEMP->jiedian.shuzu0 + 1 <= 8 && TEMP->jiedian.e != 1)151.OPEN = addnode(OPEN, newnode(TEMP, depth, 2);1

17、52.if (TEMP->jiedian.shuzu0 - 3 >= 0 && TEMP->jiedian.e != 4)153.OPEN = addnode(OPEN, newnode(TEMP, depth, 3);154.if (TEMP->jiedian.shuzu0 + 3 <= 8 && TEMP->jiedian.e != 3)155.OPEN = addnode(OPEN, newnode(TEMP, depth, 4);156.depth+;157.158.159.if (OPEN)/如有解，则打印出解的步骤

18、160.(161.TEMP->path = NULL;162.while (TEMP->parent)/每次回溯父节点，生成路径163.(164.TEMP->parent->path = TEMP;165.TEMP = TEMP->parent;166.167.j = 0;168.while (TEMP->path)169.(170.setboard(sgoal, TEMP->jiedian.shuzu, 1);171.printf("第 d 步：n", j);172.for (i = 0;i <= 2;i+)173.prin

19、tf(" %d", sgoali);174.printf(" n");175.for (i = 3;i <= 5;i+)176.printf(" %d", sgoali);177.printf("n");178.for (i = 6;i <= 8;i+)179.printf(" %d", sgoali);180.printf("n");181.TEMP = TEMP->path;182.j+;防止棋183. 184. setboard(sgoal, TEMP

20、->jiedian.shuzu, 1);185. printf("第 d 步：n", j);186. for (i = 0;i <= 2;i+)187. printf(" %d",sgoali);188. printf("n");189. for (i = 3;i <=5;i+)190. printf(" %d",sgoali);191. printf("n");192. for (i = 6;i <=8;i+)193. printf(" %d",sg

21、oali);194. printf("n");195. 196. else197. printf("无法求解！");198. (1)以上代码估价函数为深度+错放棋子个数(2)若估价函数为深度+每个棋子与其目标位置之间的距离总和，则函数改为int calvalue(int a口)不在位棋子数int c = 0;int b=0;for (int i = 0;i <= 8;i+)for (int j = 0;j <= 8;j+)if (ai = goalj)if (goalj != 0)c=c+abs(i%3-j%3)+abs(i- i%3)/3+(j- j%3)/3);return c;(3)宽度搜索采用 OPEN->jiedian.f = depth;(4)深度搜索采用 O