啟發(fā)式搜索-八數(shù)碼問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上啟發(fā)式搜索1. 介紹八數(shù)碼問題也稱為九宮問題。在3×3的棋盤，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個(gè)空格（以數(shù)字0來表示），與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。所謂問題的一個(gè)狀態(tài)就是棋子在棋盤上的一種擺法。解八數(shù)碼問題實(shí)際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。2. 使用啟發(fā)式搜索算法求解8數(shù)碼問題。1) A ，A星算法采用估價(jià)函數(shù)，其中：是搜索樹中結(jié)點(diǎn)的深度；為結(jié)點(diǎn)的數(shù)據(jù)庫中錯(cuò)放的棋子個(gè)

2、數(shù)；為結(jié)點(diǎn)的數(shù)據(jù)庫中每個(gè)棋子與其目標(biāo)位置之間的距離總和。2) 寬度搜索采用f(i)為i的深度，深度搜索采用f(i)為i的深度的倒數(shù)。3. 算法流程 把起始節(jié)點(diǎn)S放到OPEN表中，并計(jì)算節(jié)點(diǎn)S的； 如果OPEN是空表，則失敗退出，無解； 從OPEN表中選擇一個(gè)值最小的節(jié)點(diǎn)。如果有幾個(gè)節(jié)點(diǎn)值相同，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)；否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)； 把節(jié)點(diǎn)從 OPEN 表中移出，并把它放入 CLOSED 的已擴(kuò)展節(jié)點(diǎn)表中； 如果是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解； 擴(kuò)展節(jié)點(diǎn)，生成其全部后繼節(jié)點(diǎn)。對于的每一個(gè)后繼節(jié)點(diǎn)：計(jì)算；如果 既不在OPEN表中，又不在CLOCED表中

3、，則用估價(jià)函數(shù)把它添入OPEN表中。從加一指向其父節(jié)點(diǎn)的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑；如果已在OPEN表或CLOSED表中，則比較剛剛對計(jì)算過的和前面計(jì)算過的該節(jié)點(diǎn)在表中的值。如果新的較小，則(I)以此新值取代舊值。(II)從指向，而不是指向他的父節(jié)點(diǎn)。(III)如果節(jié)點(diǎn)在CLOSED表中，則把它移回OPEN表中。 轉(zhuǎn)向，即GOTO。4. 估價(jià)函數(shù)計(jì)算一個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)，可以分成兩個(gè)部分：1、 已經(jīng)付出的代價(jià)（起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)）；2、 將要付出的代價(jià)（當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)）。節(jié)點(diǎn)n的估價(jià)函數(shù)定義為從初始節(jié)點(diǎn)、經(jīng)過n、到達(dá)目標(biāo)節(jié)點(diǎn)的路徑的最小代價(jià)的估計(jì)值，即 = + 。是從初始節(jié)

4、點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)； 是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià)，體現(xiàn)出搜索過程中采用的啟發(fā)式信息（背景知識(shí)），稱之為啟發(fā)函數(shù)。所占的比重越大，越趨向于寬度優(yōu)先或等代價(jià)搜索；反之，的比重越大，表示啟發(fā)性能就越強(qiáng)。5. 實(shí)驗(yàn)代碼為方便起見，目標(biāo)棋局為不變(1)以下代碼估價(jià)函數(shù)為深度+錯(cuò)放棋子個(gè)數(shù)(2) 若估價(jià)函數(shù)為深度+每個(gè)棋子與其目標(biāo)位置之間的距離總和，則加入估價(jià)函數(shù)int calvalue1(int a) /不在位棋子數(shù)int c = 0; int b=0;for (int i = 0;i <= 8;i+)for (int j = 0;j <= 8;j+) if (ai =

5、 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->jiedian.f = -depth;源代碼：1. #include "stdio.h" 2.3. int goal9 = 1,2,3,8,0,4,7,6,5 , sgoal9;/goal為棋盤的目標(biāo)布局,并用中間狀態(tài)sgoal與之比較4.5. struct Board6. 7. int shuzu9;8. int

6、d, f, e;/d:深度;f:啟發(fā)函數(shù);e:記錄前一次的擴(kuò)展節(jié)點(diǎn)9. ;10.11. struct NodeLink12. 13. Board jiedian;14. NodeLink *parent;15. NodeLink *previous;16. NodeLink *next;17. NodeLink *path;18. ;19. /更新紀(jì)錄八數(shù)碼的狀態(tài)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.

7、abi = i;25. else26. bai = i;27. 28. /計(jì)算啟發(fā)值的函數(shù)29. int calvalue(int a) /不在位棋子數(shù)30. 31. int c = 0;32. for (int i = 0;i <= 8;i+)33. if (ai != goali)34. if (goali != 0)35. c+;36. return c;37. 38. /生成一個(gè)新節(jié)點(diǎn)的函數(shù)39. NodeLink *newnode(NodeLink *TEM, int depth, int flag)40. 41. NodeLink *temp = new NodeLink;4

8、2. for (int i = 0;i <= 8;i+)43. temp->jiedian.shuzui = TEM->jiedian.shuzui;44. switch (flag)45. 46. case 1:47. 48. temp->jiedian.shuzu0-;49. temp->jiedian.shuzusgoaltemp->jiedian.shuzu0+; /向左移50. break;51. 52. case 2:53. 54. temp->jiedian.shuzu0+;55. temp->jiedian.shuzusgoalt

9、emp->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->jiedian.shuzusgoaltemp->jiedian.shuzu0 -= 3; /向下移68. break;69. 70.

10、 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. /把新節(jié)點(diǎn)加入OPEN隊(duì)列79. NodeLink *addnode(NodeLink *head, NodeLink *node) /把node插入

11、到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. /求啟發(fā)值最小的結(jié)點(diǎn)92. NodeLink *minf(NodeLink *head)93. 94. NodeLink *min, *forward;95. min = head;96. forward = he

12、ad;97. while (forward)98. 99. if (min->jiedian.f>forward->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, *TEM;114.115

13、. printf("請輸入初始狀態(tài)：n");116. for (i = 0;i<9;i+)117. scanf_s("%d", &sourcei);118.119. setboard(source, OPEN->jiedian.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

14、->previous = NULL;125. OPEN->parent = NULL;126.127. while (OPEN)128. 129. TEMP = minf(OPEN); /求具有最小啟發(fā)值的節(jié)點(diǎn)130. setboard(sgoal, TEMP->jiedian.shuzu, 1); /寫棋盤131. if (!calvalue(sgoal)132. break;133. if (TEMP != OPEN) /如果不是第一個(gè)節(jié)點(diǎn)134. 135. TEMP->previous->next = TEMP->next;136. TEMP->

15、next->previous = TEMP->previous;137. 138. else /是第一個(gè)節(jié)點(diǎn)139. 140. if (OPEN->next) /如果還有節(jié)點(diǎn)141. 142. OPEN = OPEN->next;143. OPEN->previous = NULL;144. 145. else OPEN = NULL; /否則置為空146. 147.148. if (TEMP->jiedian.shuzu0 - 1 >= 0 && TEMP->jiedian.e != 2) /防止棋子回到原狀態(tài)149. OPEN

16、 = 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);152. if (TEMP->jiedian.shuzu0 - 3 >= 0 && TEMP->jiedian.e != 4)153. OPEN = addnode(OPEN, newnode(TEMP, depth, 3)

17、;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) /如有解,則打印出解的步驟160. 161. TEMP->path = NULL;162. while (TEMP->parent) /每次回溯父節(jié)點(diǎn)，生成路徑163. 164. TEMP->parent->path = TEMP;165.

18、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. printf(" %d", sgoali);174. printf(" n");175. for (i = 3;i <= 5;i+)176. printf(" %d&qu

19、ot;, 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->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", sg