人工智能-A*启发式搜索算法解决八数码问题 Python实现

一.问题描述

        八数码问题也称为九宫问题。在 3×3 的棋盘，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字 0 来表示），与空 格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

该问题可用A*启发式搜索算法求解。

A*算法的估价函数如下: 

        其中启发函数可选择w(n)和p(n)两种，本文以w(n)为例编写程序

---

二.算法实现【理论部分】

本文以如下情况为例进行分析：

         1.对问题进行抽象

                 ①.操作算子的选取

                若着眼在数码上，则相应的操作算子就是数码的移动，可知共有4(方向)*8(码的个数)=32 种算子，设计起来较为复杂。

                若着眼在空格上，则相应的操作算子就是空格的移动，在最理想的情况下【即空格在棋盘正中间时】，最多有4种算子【上移up,下移down,左移left，右移right】，设计较为简单。

                综上所述，本程序选择着眼于空格，使用上下左右四种操作算子进行程序编写

               ②.数码移动过程的抽象

                可将数码在3*3棋盘上的分布抽象为一维数组，这样每次空格的移动就等价于交换一维数组种两个元素的位置，如下图所示:

     

 至此，数码的移动问题转换成了寻找两个待交换元素在数组中的下标并交换的问题

                2.实际执行过程

                        ①.搜索树

✅2023/12/17修正：

下图搜索树中的A(4)应该修改为A(6)

因为此时序列中共有：

2,8,3,1,6,4,(0),7,5 六个元素（标红）不在【目标位置】

1,2,3,8,(0),4,7,6,5（目标序列）

由上图的搜索树可知：

        树上的任意一个节点应该包含如下信息：

                ·该节点在树中的深度

                ·该节点的估价函数值 f(n)

                · 该节点的数码序列【抽象为一维数组】

                        ②.open表和closed表

由上表可知:

        open表中存放的是按估价函数值排序的节点，closed表存放的是每次从循环从open表中取出的第一个节点，直到取出节点的数码序列等于最终的数码序列,算法结束。 

          3.无解的情况

首先明确： 八数码问题是存在无解的情况的，在编写程序时，首先就需要判断初始序列和目标序列之间的变换是否是有解的，若将无解的两个序列执行算法，算法将陷入死循环

        两个状态有无解的判断，由两个序列的逆序数奇偶性决定，若两序列的逆序数同为奇数或同为偶数，则两序列的变换有解，否则无解。

        何为逆序数？ 如何求逆序数？ 看这篇文章，这里不多赘述  逆序数文章

            4.操作算子的选择

                       ①.边界条件                   

                         ②.防止死循环

前一次执行UP操作，下一次迭代时应该禁用DOWN操作

前一次执行LEFT操作，下一次迭代应该禁用RIGHT操作 ，

反之亦然，目的是为了避免出现死循环

具体示例如下图:        

                总之，操作算子的选择在不考虑②中的约束条件时，其选取是的结果是十分固定的，例如0位置只能选择DOWN和RIGHT，5位置只能选择LEFT，UP和DOWN。在实际程序中可根据元素在数组中的位置+约束条件得到此次可选择的操作算子。

        5.数据结构的设计

        经过如上分析可知，要实现算法，关键要设计出搜索树中每个节点的数据结构，本次设计的结构如下:

1. class statusObject:
2. def __init__(self):
3. # 当前状态的序列
4. self.array = []
5. # 当前状态的估价函数值
6. self.Fn = 0
7. # cameFrom表示该状态由上一步由何种operation得到
8. # 目的是为了过滤 【死循环】
9. # 0表示初始无状态 1表示up 2表示down 3表示left 4表示right
10. self.cameFrom = 0
11. # 第一次生成该节点时在图中的深度 计算估价函数使用
12. self.Dn = 0
13. # 该节点的父亲节点，用于最终溯源最终解
14. self.Father = statusObject

---

三.算法实现【代码部分】

         1.流程图:

                 2.程序源码

程序使用了numpy包，运行前请自行安装

另外在调试过程中使用了很多print语句查看结果，现已注释，若不需要请自行删除

1. import operator
2. import sys
4. import numpy as np
7. class statusObject:
8. def __init__(self):
9. # 当前状态的序列
10. self.array = []
11. # 当前状态的估价函数值
12. self.Fn = 0
13. # cameFrom表示该状态由上一步由何种operation得到
14. # 目的是为了过滤 【死循环】
15. # 0表示初始无状态 1表示up 2表示down 3表示left 4表示right
16. self.cameFrom = 0
17. # 第一次生成该节点时在图中的深度 计算估价函数使用
18. self.Dn = 0
19. self.Father = statusObject
22. def selectOperation(i, cameFrom):
23. # @SCY164759920
24. # 根据下标和cameFromReverse来选择返回可选择的操作
25. selectd = []
26. if (i >= 3 and i <= 8 and cameFrom != 2): # up操作
27. selectd.append(1)
28. if (i >= 0 and i <= 5 and cameFrom != 1): # down操作
29. selectd.append(2)
30. if (i == 1 or i == 2 or i == 4 or i == 5 or i == 7 or i == 8): # left操作
31. if (cameFrom != 4):
32. selectd.append(3)
33. if (i == 0 or i == 1 or i == 3 or i == 4 or i == 6 or i == 7): # right操作
34. if (cameFrom != 3):
35. selectd.append(4)
36. return selectd
39. def up(i):
40. return i - 3
43. def down(i):
44. return i + 3
47. def left(i):
48. return i - 1
51. def right(i):
52. return i + 1
54. def setArrayByOperation(oldIndex, array, operation):
55. # i为操作下标
56. # 根据operation生成新状态
57. if (operation == 1): # up
58. newIndex = up(oldIndex) # 得到交换的下标
59. if (operation == 2): # down
60. newIndex = down(oldIndex)
61. if (operation == 3): # left
62. newIndex = left(oldIndex)
63. if (operation == 4): # right
64. newIndex = right(oldIndex)
65. # 对调元素的值
66. temp = array[newIndex]
67. array[newIndex] = array[oldIndex]
68. array[oldIndex] = temp
69. return array
72. def countNotInPosition(current, end): # 判断不在最终位置的元素个数
73. count = 0 # 统计个数
74. current = np.array(current)
75. end = np.array(end)
76. for index, item in enumerate(current):
77. if ((item != end[index]) and item != 0):
78. count = count + 1
79. return count
82. def computedLengthtoEndArray(value, current, end): # 两元素的下标之差并去绝对值
83. def getX(index): # 获取当前index在第几行
84. if 0 <= index <= 2:
85. return 0
86. if 3 <= index <= 5:
87. return 1
88. if 6 <= index <= 8:
89. return 2
91. def getY(index): # 获取当前index在第几列
92. if index % 3 == 0:
93. return 0
94. elif (index + 1) % 3 == 0:
95. return 2
96. else:
97. return 1
99. currentIndex = current.index(value) # 获取当前下标
100. currentX = getX(currentIndex)
101. currentY = getY(currentIndex)
102. endIndex = end.index(value) # 获取终止下标
103. endX = getX(endIndex)
104. endY = getY(endIndex)
105. length = abs(endX - currentX) + abs(endY - currentY)
106. return length
108. def countTotalLength(current, end):
109. # 根据current和end计算current每个棋子与目标位置之间的距离和【除0】
110. count = 0
111. for item in current:
112. if item != 0:
113. count = count + computedLengthtoEndArray(item, current, end)
114. return count
116. def printArray(array): # 控制打印格式
117. print(str(array[0:3]) + '\n' + str(array[3:6]) + '\n' + str(array[6:9]) + '\n')
119. def getReverseNum(array): # 得到指定数组的逆序数 包括0
120. count = 0
121. for i in range(len(array)):
122. for j in range(i + 1, len(array)):
123. if array[i] > array[j]:
124. count = count + 1
125. return count
128. openList = [] # open表 存放实例对象
129. closedList = [] # closed表
130. endArray = [1, 2, 3, 8, 0, 4, 7, 6, 5] # 最终状态
131. countDn = 0 # 执行的次数
133. initObject = statusObject() # 初始化状态
134. # initObject.array = [2, 8, 3, 1, 6, 4, 7, 0, 5]
135. initObject.array = [2, 8, 3, 1, 6, 4, 7, 0, 5]
136. # initObject.array = [2, 1, 6, 4, 0, 8, 7, 5, 3]
137. initObject.Fn = countDn + countNotInPosition(initObject.array, endArray)
138. # initObject.Fn = countDn + countTotalLength(initObject.array, endArray)
139. openList.append(initObject)
140. zeroIndex = openList[0].array.index(0)
141. # 先做逆序奇偶性判断 0位置不算
142. initRev = getReverseNum(initObject.array) - zeroIndex # 起始序列的逆序数
143. print("起始序列逆序数", initRev)
144. endRev = getReverseNum(endArray) - endArray.index(0) # 终止序列的逆序数
145. print("终止序列逆序数", endRev)
146. res = countTotalLength(initObject.array, endArray)
147. # print("距离之和为", res)
148. # @SCY164759920
149. # 若两逆序数的奇偶性不同，则该情况无解
151. if((initRev%2==0 and endRev%2==0) or (initRev%2!=0 and endRev%2!=0)):
152. finalFlag = 0
153. while(1):
154. # 判断是否为end状态
155. if(operator.eq(openList[0].array,endArray)):
156. # 更新表，并退出
157. deep = openList[0].Dn
158. finalFlag = finalFlag +1
159. closedList.append(openList[0])
160. endList = []
161. del openList[0]
162. if(finalFlag == 1):
163. father = closedList[-1].Father
164. endList.append(endArray)
165. print("最终状态为:")
166. printArray(endArray)
167. while(father.Dn >=1):
168. endList.append(father.array)
169. father = father.Father
170. endList.append(initObject.array)
171. print("【变换成功,共需要" + str(deep) +"次变换】")
172. for item in reversed(endList):
173. printArray(item)
174. sys.exit()
175. else:
176. countDn = countDn + 1
177. # 找到选中的状态0下标
178. zeroIndex = openList[0].array.index(0)
179. # 获得该位置可select的operation
180. operation = selectOperation(zeroIndex, openList[0].cameFrom)
181. # print("0的下标", zeroIndex)
182. # print("cameFrom的值", openList[0].cameFrom)
183. # print("可进行的操作",operation)
184. # # print("深度",openList[0].Dn)
185. # print("选中的数组:")
186. # printArray(openList[0].array)
187. # 根据可选择的操作算出对应的序列
188. tempStatusList = []
189. for opeNum in operation:
190. # 根据操作码返回改变后的数组
191. copyArray = openList[0].array.copy()
192. newArray = setArrayByOperation(zeroIndex, copyArray, opeNum)
193. newStatusObj = statusObject() # 构造新对象插入open表
194. newStatusObj.array = newArray
195. newStatusObj.Dn = openList[0].Dn + 1 # 更新dn 再计算fn
196. newFn = newStatusObj.Dn + countNotInPosition(newArray, endArray)
197. # newFn = newStatusObj.Dn + countTotalLength(newArray, endArray)
198. newStatusObj.Fn = newFn
199. newStatusObj.cameFrom = opeNum
200. newStatusObj.Father = openList[0]
201. tempStatusList.append(newStatusObj)
202. # 将操作后的tempStatusList按Fn的大小排序
203. tempStatusList.sort(key=lambda t: t.Fn)
204. # 更新closed表
205. closedList.append(openList[0])
206. # 更新open表
207. del openList[0]
208. for item in tempStatusList:
209. openList.append(item)
210. # 根据Fn将open表进行排序
211. openList.sort(key=lambda t: t.Fn)
212. # print("第"+str(countDn) +"次的结果:")
213. # print("open表")
214. # for item in openList:
215. # print("Fn" + str(item.Fn))
216. # print("操作" + str(item.cameFrom))
217. # print("深度"+str(item.Dn))
218. # printArray(item.array)
219. # @SCY164759920
220. # print("closed表")
221. # for item2 in closedList:
222. # print("Fn" + str(item2.Fn))
223. # print("操作" + str(item2.cameFrom))
224. # print("深度" + str(item2.Dn))
225. # printArray(item2.array)
226. # print("==================分割线======================")
227. else:
228. print("该种情况无解")

---

2022.10.28 13:32更新： 

        经测试后发现，源代码的输出在某些情况下会BUG，现已修改，修改了原数据结构，在每个节点中添加了“Father”属性，用以存放每个节点的父亲节点。修改后，经测试已经能正常输出，若读者是在更新时间之后阅读本文，直接可忽略。

更新:

         原程序的启发函数只提供了w(n)的方法，现更新p(n)的实现:

        【p(n)即:节点n的每个棋子与目标位置之间的距离总和】

修改方法:

        将源程序中两处计算Fn的函数进行替换 并添加两个计算函数

第一处

 【原】：initObject.Fn = countDn + countNotInPosition(initObject.array, endArray)

【替换】:initObject.Fn = countDn + countTotalLength(initObject.array, endArray)

第二处:

【原】:newFn = newStatusObj.Dn + countNotInPosition(newArray, endArray)

【替换】:newFn = newStatusObj.Dn + countTotalLength(newArray, endArray)

添加两个计算函数:

1. def computedLengthtoEndArray(value, current, end): # 两元素的下标之差并去绝对值
2. def getX(index): # 获取当前index在第几行
3. if 0 <= index <= 2:
4. return 0
5. if 3 <= index <= 5:
6. return 1
7. if 6 <= index <= 8:
8. return 2
10. def getY(index): # 获取当前index在第几列
11. if index % 3 == 0:
12. return 0
13. elif (index + 1) % 3 == 0:
14. return 2
15. else:
16. return 1
18. currentIndex = current.index(value) # 获取当前下标
19. currentX = getX(currentIndex)
20. currentY = getY(currentIndex)
21. endIndex = end.index(value) # 获取终止下标
22. endX = getX(endIndex)
23. endY = getY(endIndex)
24. length = abs(endX - currentX) + abs(endY - currentY)
25. return length
27. def countTotalLength(current, end):
28. # 根据current和end计算current每个棋子与目标位置之间的距离和【除0】
29. count = 0
30. for item in current:
31. if item != 0:
32. count = count + computedLengthtoEndArray(item, current, end)
33. return count

分别运行启发函数取w(n)和p(n)发现，在本次选取的示例转换中:

        取p(n)时转换过程共需要5步

        取w(n)时转换过程共需要5步