1. 题目说明
在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。
例：
题目要求：使用启发式规则
2. 设计思路
正如前面题目所言八数码问题是将一个带空格的八个数码块从初始状态通过空格之间上下左右的方块交换变换成数码的目标状态（此时我们将空格用数字0来表示）
首先我们可以把每一个变化状态想象成一个节点，这个节点包含了它所代表的状态序列，这样我们就把八数码问题转换为从一个节点到目标节点的问题了。这显然进入到图论上的问题了，此时我们考虑的便是节点到节点可不可达的问题，通过一些资料的查找发现当出发节点的序列和目的节点的序列的逆序数同为奇数或者同为偶数便是可达的，否则不可达。
此时我们处理好路径可不可达的问题之后，若可达进入搜索序列程序，不可达则直接退出即可。
搜索主程序主要在如下步骤，先初始化一个节点为根节点（初始序列），通过调用节点类定义的方法获取它相应的子节点（表示空格能与周边移动的单元），而每次变换都是一个新的状态，也就是为一个新的节点。
这个时候便会引申出来一个问题，在每个节点都有其子节点我们要以何种方式来进行寻找呢？
此时在对节点搜索上在大方向上分为两块：
一个是传统的搜索算法，它主要是通过一定固定规则进行遍历查找，例如广度搜索，深度搜索等，它们在不断递归搜索没有相应的变通，在数据规模较小的情况下可能可以迅速得出结果，但是在处理问题规模大的时候它便变得笨拙起来了。所谓笨拙是因为没有利用一些有用的信息为自己筛选规划，不管什么信息它都会进行处理，这也就占用了大量的时空复杂度。
第二个是启发式规则的方法来搜索。所谓启发式规则在我的理解看来就是它在搜索过程中较为智能，有一定的判断依据或者说是判优过程，优先选择优先级高即代价更低、优先选择更高概率的搜索路径，经过一系列的判断执行过程最终找到目标。上面说的那些流程也同样引申出来一个问题，如何判优？有什么相对应的规则来进行？
对于上面规则的回答也就对应在启发式上两种不同的算法分支：贪婪算法和A*算法
贪婪算法在解决从出发点到目的地最优规划上，它通过本节点到目的节点计算的最优路径上选择一个离目的节点更近的节点作为下一跳，不断此番选择，最后找到目的节点。不过它存在着的问题也很严重，那便是如此选择的不一定是最优的路线，以及选择路线上可能会陷入循环回路之中导致一直在路上的子环搜索。
所以说对于以上问题A*算法应运而生，不过在我看来它跟贪婪算法区别在于在评价方式方面加入了从出发节点到本节点的代价估量，所以说A*算法加入了前面说的估量值可以让代价选择上是不断增加的最终找到目的节点为止。
本题我便是用的A*算法，在初始节点到目前节点的代价评估计算用的是深度值，每向下一层我便代价值加一，而现节点到目的节点的损失代价有两种不同的评估方式，一个是以不在位数作为评估，一个是利用曼哈顿距离来评估。我们在这里探讨这两种方式之间差异，不在位数的评估利用的是跟目的状态比对没有在对于位置的数码数，而曼哈顿距离同样也是比对不过它是利用曼哈顿距离来计算代价，要说谁提供的代价信息更为可靠，当属于经典图论上曼哈顿距离莫属了，因为它处理的就是空间中的两点在非欧几里得方式下最优到目的地的距离。
介绍了选择选择A*算法的哈曼顿方式来搜索之后，我用一张流程图来介绍其中流程。
3.作品设计完整代码
1 import copy
2
3 import numpy as np
4
5 class Node:
6
7 def __init__(self,node,parent,cost,distance):
8
9 self.node=node
10
11 self.parent=parent
12
13 self.cost=cost
14
15 self.distance = distance
16
17 def get_children(self):
18
19 children = []
20
21 for i in canGoNodes(self.node):
22
23 child = Node(node=get_child(self.node, i),
24
25 parent=self,
26
27 cost=self.cost + 1,
28
29 distance=self.distance + mhdDistance(self.node, goal_arr))
30
31 children.append(child)
32
33 return children
34
35 # 计算逆序数
36
37 def reverseOrdinalNum(numString):
38
39 num=0
40
41 for i in range(1, 9):
42
43 temp=0
44
45 for j in range(0, i):
46
47 if numString[j] > numString[i] and numString[i] != '0':
48
49 temp += 1
50
51 num = num+temp
52
53 return num
54
55 # 找到目标在arr节点的位置
56
57 def findNode(arr,target):
58
59 for i in arr:
60
61 for j in i:
62
63 if j==target:
64
65 return arr.index(i),i.index(j)
66
67 # 获取能够和空格交换的子节点
68
69 def canGoNodes(arr):
70
71 nodes=[]
72
73 # 首先得先寻找到空格在此节点的下标位置
74
75 x,y=findNode(arr,'0')
76
77 # 向上
78
79 if x>0:
80
81 nodes.append(arr[x-1][y])
82
83 # 向左
84
85 if y>0:
86
87 nodes.append(arr[x][y-1])
88
89 # 向下
90
91 if x<2:
92
93 nodes.append(arr[x+1][y])
94
95 # 向右
96
97 if y<2:
98
99 nodes.append(arr[x][y+1])
100
101 return nodes
102
103 # 将字符串转换为列表
104
105 def string_to_list(str):
106
107 str_list = list(str)
108
109 return [str_list[i:i + 3] for i in range(0, len(str_list), 3)]
110
111
112
113 def get_child(arr,i):
114
115 node_new=copy.deepcopy(arr)
116
117 x, y = findNode(node_new, '0')
118
119 x1,y1=findNode(node_new,i)
120
121 node_new[x][y],node_new[x1][y1]=node_new[x1][y1],node_new[x][y]
122
123 return node_new
124
125 def isSolution(initState,endState):
126
127 initState=initState.replace(" ", "")
128
129 endState=endState.replace(" ", "")
130
131 if (reverseOrdinalNum(initState)%2)==(reverseOrdinalNum(endState)%2):
132
133 return True
134
135 else:
136
137 return False
138
139 # 计算曼哈顿距离
140
141 def mhdDistance(node1,node2):
142
143 distance = []
144
145 for i in node1:
146
147 for j in i:
148
149 loc1 = findNode(node1, j)
150
151 loc2 = findNode(node2, j)
152
153 distance.append(abs(loc1[0] - loc2[0]) + abs(loc1[1] - loc2[1]))
154
155 return sum(distance)
156
157 # A*算法-曼哈顿距离
158
159 def AStar_MHT(initial_arr, goal_arr):
160
161 open = [initial_arr]
162
163 close = []
164
165 while len(open) > 0: # OPEN表是否为空表
166
167 open_1 = [i.node for i in open]
168
169 close_1 = [i.node for i in close]
170
171 n = open.pop(0)
172
173 close.append(n)
174
175 if n.node == goal_arr:
176
177 print('最优路径如下：')
178
179 print(np.array(n.node,dtype=object)) # 转换成矩阵打印最终节点
180
181 best_path(n)
182
183 break
184
185 else:
186
187 for i in n.get_children(): # 添加子节点进OPEN
188
189 if i.node not in open_1:
190
191 if i.node not in close_1:
192
193 open.insert(0, i)
194
195 open.sort(key=lambda x: x.distance + x.cost) # 按曼哈顿距离＋cost 进行排序
196
197 print("=====================================================================================")
198
199 print("=====================================================================================")
200
201 print("=====================================================================================")
202
203 search_line(close)
204
205 print('搜索步数为：', len(close) - 1, '总代价为：', close[-1].cost + close[-1].distance)
206
207 # 展示最优路径
208
209 def best_path(n):
210
211 if n.parent==None:
212
213 return
214
215 else:
216
217 print("^")
218
219 print("|")
220
221 print("|")
222
223 print(np.array(n.parent.node, dtype=object))
224
225 best_path(n.parent)
226
227 def search_line(close):
228
229 print('搜索路径如下：')
230
231 for i in close[:-1]:
232
233 print(np.array(i.node,dtype=object))
234
235 print("|")
236
237 print("|")
238
239 print("V")
240
241 print(np.array(close[-1].node,dtype=object))
242
243
244
245 if __name__=='__main__':
246
247 print(
248
249 """
250
251 在一个在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。
252
253 这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。
254
255 现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。
256
257 3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。
258
259 这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。
260
261 现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。
262
263 输入样例：
264
265 输入序列：283 104 765
266
267 输入目的序列：123 804 765
268
269 """
270
271 )
272
273 initStr = input("输入序列：")
274
275 endStr = input("输入目的序列：")
276
277 if isSolution(initStr, endStr):
278
279 init_arr = string_to_list(initStr)
280
281 goal_arr = string_to_list(endStr)
282
283 inital_arr = Node(init_arr, parent=None, cost=0,distance=mhdDistance(init_arr,goal_arr))
284
285 AStar_MHT(inital_arr, goal_arr)
286
287 else:
288
289 print("此初始序列到不了目的序列，问题无解！")
290
291 input("please input any key to exit!")
4.运行结果截图
5.设计中遇到的问题与解决
设计之中遇到的问题有一下几个方面：
- 对启发式规则不太熟悉，解决问题的方案一时间不知道如何下手
- 在确定解决方法时代码功底不够，经常要将前面的翻到从来
- 程序出现BUG时，对程序查找错误迅速定位不够精炼。
- 将程序打包过程出现的解码错误使得.exe文件生成出来无法运行
解决过程：
我利用各大互联网开源平台（B站、CSDN、github等）先是仔细研习了启发式规则的相关知识点重新温习了相关思想，在具体落地实现上首先学会看懂他人的代码，在仔细琢磨其中的流程是否和自己理解的算法思想一致，是否流程上相一致。在具体到写代码时，是否对一些细节上的操作疏忽了导致程序并没有达到我们想要的预期效果，利用开源资源来一步步实现从无到实现出来。在对程序报错方面，我利用分割出不同的模块将错误不断定位更小的空间，直到查找到最终的错误所在。对程序进行打包也同样去阅读相应的函数开发文档找到参数的使用不同点以及能带来的情况变换是什么，对症下药调整配置文件将问题解决。
6.作品设计感受
通过这份期末大作业的整个完成过程，我对解决问题上的相关流程以及对问题的科学思考、理性分析和问题的转换都有了一定的锻炼。八数码问题上转换为图论相关求解，利用启发式规则来进行求解。首先是要想到解决方案，再而是将方案落地，用编程语言来实现，这开始考验的是你的代码能力，最后得出结果再进行验证是否可行，准确性如何，一切都可行之后才算是初步落地成功。虽然上面大体步骤就短短几句话，但是考查的是一个人综合能力，逻辑思维如何，代码功底怎么样，利用互联网查找资料的能力强不强等。出现问题无法解决时，心态稳定也是一个重要的因素，有一个稳定的心态是能解决一切的钥匙，要沉下心来去找到问题出错的答案和知识点，如果心态不好，也许会把问题越弄越糟糕。
最后特别感谢那些开源工作者们以及知识经验分享者们，也让我意识到构建一个完好的开源生态的有利之处，我以后也会积极成为贡献者之一，同样也是受益者，让知识没有围墙，让感兴趣的人都能够找到资源提升自己，看到这里的小伙伴必然能是未来计算机界中流砥柱（苗子），让我们共勉！
标签：node,arr,python,空格,曼哈顿,数码,print,节点 From： https://www.cnblogs.com/sangGou/p/17019407.html