《启发式搜索-八数码问题》由会员分享，可在线阅读，更多相关《启发式搜索-八数码问题（11页珍藏版）》请在金锄头文库上搜索。
1、启发式搜索1. 简介八数码问题也称为九宫问题。在33的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相似。棋盘上尚有一种空格（以数字0来表达），与空格相邻的棋子可以移到空格中。规定解决的问题是：给出一种初始状态和一种目的状态，找出一种从初始转变成目的状态的移动棋子步数至少的移动环节。所谓问题的一种状态就是棋子在棋盘上的一种摆法。解八数码问题事实上就是找出从初始状态达到目的状态所通过的一系列中间过渡状态。2. 使用启发式搜索算法求解8数码问题。1) A ，A星算法采用估价函数，其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目的位
2、置之间的距离总和。2) 宽度搜索采用f(i)为i的深度，深度搜索采用f(i)为i的深度的倒数。3. 算法流程 把起始节点S放到OPEN表中，并计算节点S的； 如果OPEN是空表，则失败退出，无解； 从OPEN表中选择一种值最小的节点。如果有几种节点值相似，当其中有一种为目的节点时，则选择此目的节点；否则就选择其中任一种节点作为节点； 把节点从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； 如果是个目的节点，则成功退出，求得一种解； 扩展节点，生成其所有后继节点。对于的每一种后继节点：计算；如果 既不在OPEN表中，又不在CLOCED表中，则用估价函数把它添入OPEN表中。从
3、加一指向其父节点的指针，以便一旦找到目的节点时记住一种解答途径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则(I)以此新值取代旧值。(II)从指向，而不是指向她的父节点。(III)如果节点在CLOSED表中，则把它移回OPEN表中。 转向，即GOTO。4. 估价函数计算一种节点的估价函数，可以提成两个部分：1、 已经付出的代价（起始节点到目前节点）；2、 将要付出的代价（目前节点到目的节点）。节点n的估价函数定义为从初始节点、通过n、达到目的节点的途径的最小代价的估计值，即 = + 。是从初始节点达到目前节点n的实际代价； 是从节点
4、n到目的节点的最佳途径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表达启发性能就越强。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 jiedian.f = depth; (4) 深度搜索采用OPEN-jiedian.f
5、 = -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. NodeLink *next;17. Node
6、Link *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. if (ai != goali)34. if (goali
7、!= 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 jiedian.shuzui = TEM-jiedian.shuzui;44. switch (flag)45. 46. case 1:47. 48. temp-jiedian.shuzu0-;49. temp-jiedian.shuzusgoaltemp-jiedian.shu
8、zu0+; /向左移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-jiedian.shuzu0 += 3; /向上移62. break;63. 64. case 4:65. 66. temp-jiedian.shuzu0 += 3;67. temp-j
9、iedian.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(sgoal);74. temp-jiedian.e = flag;75. temp-parent = TEM;76. return temp;77. 78. /把新节点加入OPEN队列79. NodeLink *addnode(
10、NodeLink *head, NodeLink *node) /把node插入到head链中80. 81. NodeLink *TEM;82. TEM = head;83. head = node;84. head-next = TEM;85. head-previous = NULL;86. if (TEM)87. TEM-previous = head; /TEM已为空,无需操作88. return head;89. 90.91. /求启发值最小的结点92. NodeLink *minf(NodeLink *head)93. 94. NodeLink *min, *forward;95.
11、 min = head;96. forward = head;97. while (forward)98. 99. if (min-jiedian.fforward-jiedian.f)100. min = forward;101. forward = forward-next;102. 103. return 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,
12、*TEM;114.115. printf(请输入初始状态：n);116. for (i = 0;ijiedian.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-jiedian.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;
