A*算法利用不在位数作为评价指标解决八数码问题（python）

标签：node arr python 算法数码位数 print 节点 def

一、 程序设计思想：

在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8总共八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。

例：

在此问题上两种类型的解决方案它们的区别在于是否有根据信息来引导或者是参考

解决方案一：盲目搜索算法

【思路】采用BFS搜索，一边搜索结点一边生成新的子结点。将新生成的结点放入队列queue中，将访问过的结点放入集合set中。当某结点与目标状态相同时，那么最短路径长度就是该结点的长度。而最短路径可以通过存储父节点信息已经当前的操作算子得出。有两个关键点：如何计算BFS中结点的层数（进而得出最短路径长度），如何记录最短路径。

解决方案二：启发式搜索算法

【思路】启发式算法是在盲目搜索算法的改进，通过评价函数f(n) = g(n) + h(n)为每个状态打分，通过放入优先队列中，即得分低的状态结点优先访问。其他地方处理相同。其中g(n)是指到达这一状态的代价(即层数)，h(n)是指棋盘上与目标状态不同的棋子数目。

本程序因为在生成状态时，可能重复，所以该问题应当用图模型解决，即搜索建立在图上。分别是这两个大类：盲目搜索算法(队列 + BFS)、启发式算法(优先队列 + BFS + 评价函数)即A*算法。该问题的规模为 9 ! = 362880，即有362880种可能的状态。采用盲目搜索法有的求解过程耗费时间、空间都很多，启发式算法效果比盲目搜索算法效率更高更优。

所以说不管是题目要求还是在程序效率方面启发式都占优。

而启发式中有贪婪算法和A*算法，贪婪算法具有非最优，成环易循环出错，所以这里选择A*算法。此算法过程如下：

从起始状态A开始，并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的其他状态，也可能不会。基本上，这是一个待检查方格的列表。
寻找起点周围通过上下左右移动所有可到达的状态。也把他们加入开启列表。为所有这些状态保存状态A作为“父方格”。当我们想描述路径的时候，父方格的资料是十分重要的。后面会解释它的具体用途。

3.从开启列表中删除状态A，把它加入到一个“关闭列表”。

4.取出开启列表中fvalue最低的状态，判断该状态性质

(1) 如果在开启列表中出现，那么判断该状态的gvalue通过当前节点（从open中取出，扩展出该节点的节点）作为父节点带来的gvalue 是否小于原先的父节点，若小于则需要更改它的父节点以及gvalue.

(2) 如果在关闭列表中出现，那么判断该状态的gvalue通过当前节点（从open中取出，扩展出该节点的节点）作为父节点带来的gvalue是否小于原先的父节，若小于则需要从关闭列表中删除该节点，并且将其加入开启列表，并更改其父节点为当前节点。

(3) 既不在开启列表，也不在关闭列表，这样就很简单，直接加入开启列表中就行（保持开启列表升序排列）

(4) 如果取出的节点为目标节点，则成功退出

二、程序

  1 import copy
  2 
  3 import numpy as np
  4 
  5 # 定义节点类
  6 
  7 class Node:
  8 
  9     # node为八码数的list表示，parent为父节点
 10 
 11     # cost为节点代价
 12 
 13     # nd_nums为不在位数
 14 
 15     def __init__(self,node,parent,cost,nd_nums):
 16 
 17         self.node=node
 18 
 19         self.parent=parent
 20 
 21         self.cost=cost
 22 
 23         self.nd_nums=nd_nums
 24 
 25     def get_children(self):  # 获取一层子节点
 26 
 27         children = []
 28 
 29         for i in Nodes_change(self.node):
 30 
 31             # 逐个元素与0交换位置,生成子节点child
 32 
 33             child = Node(node=get_child(self.node, i), parent=self, cost=self.cost + 1,
 34 
 35                          nd_nums=not_digits(self.node, end_arr))
 36 
 37             # 将每一个交换结果（子节点）都存入children
 38 
 39             children.append(child)
 40 
 41         return children
 42 
 43 # 计算逆序数
 44 
 45 def reverseOrdinalNum(numString):
 46 
 47     #逆序数
 48 
 49     num=0
 50 
 51     # 第一个逆序数为0，所以只要从第二个开始算就是八个
 52 
 53     for i in range(1, 9):
 54 
 55         temp=0
 56 
 57         for j in range(0, i):
 58 
 59             if numString[j] > numString[i] and numString[i] != '0':
 60 
 61                 temp += 1
 62 
 63         num = num+temp
 64 
 65     return num
 66 
 67 # 获取与空格0之间交换的节点
 68 
 69 def Nodes_change(arr):
 70 
 71     Nodes=[]
 72 
 73     r, c = find_local(arr, '0')  # 寻找0的的下标
 74 
 75     if r > 0:
 76 
 77         Nodes.append(arr[r - 1][c])  # 上边的数
 78 
 79     if r < 2:
 80 
 81         Nodes.append(arr[r + 1][c])  # 下边的数
 82 
 83     if c > 0:
 84 
 85         Nodes.append(arr[r][c - 1])  # 左边的数
 86 
 87     if c < 2:
 88 
 89         Nodes.append(arr[r][c + 1])  # 右边的数
 90 
 91     return Nodes
 92 
 93  
 94 
 95 # 将字符串转化为列表
 96 
 97 def string_to_list(str):
 98 
 99     str_list=list(str)
100 
101     return [str_list[i:i+3] for i in range(0,len(str_list),3)]
102 
103 # 计算能否通过移动空格从初始态到目的状态
104 
105 def isSolution(initState,endState):
106 
107     #把输入的空格删除
108 
109     initState=initState.replace(" ", "")
110 
111     endState=endState.replace(" ", "")
112 
113     if (reverseOrdinalNum(initState)%2)==(reverseOrdinalNum(endState)%2):
114 
115         return True
116 
117     else:
118 
119         return False
120 
121 # 不在位数
122 
123 def not_digits(arr1, arr2):
124 
125     num = 0
126 
127     for i in range(0, 3):
128 
129         for j in range(0, 3):
130 
131             if arr1[i][j] != arr2[i][j]:
132 
133                 num = num + 1
134 
135     return num
136 
137 # A*算法-不在位数
138 
139 def AStar_ND(initial_arr, end_arr):
140 
141     open = [initial_arr]
142 
143     close = []
144 
145  
146 
147     while len(open) > 0:  # OPEN表是否为空表
148 
149         open_1 = [i.node for i in open]  # 访问open节点内的node
150 
151         close_1 = [i.node for i in close]
152 
153  
154 
155         n = open.pop(0)  # 删除OPEN队头节点
156 
157         close.append(n)  # n注入CLOSE表
158 
159  
160 
161         if n.node == end_arr:
162 
163             print('最优路径如下：')
164 
165             print(np.array(n.node,dtype=object))
166 
167             best_path(n)
168 
169             break
170 
171         else:
172 
173             for i in n.get_children():  # 添加子节点进OPEN
174 
175                 if i.node not in open_1:
176 
177                     if i.node not in close_1:
178 
179                         open.insert(0, i)
180 
181                         open.sort(key=lambda x: x.nd_nums + x.cost)  # 按不在位数＋cost 进行排序
182 
183     print('--' * 20)
184 
185     print('--' * 20)
186 
187     print('--' * 20)
188 
189     search_line(close)
190 
191     print('搜索步骤为', len(close) - 1)
192 
193 # 整一个搜索路径：
194 
195 def search_line(close):
196 
197     print('搜索路径如下：')
198 
199     for i in close[:-1]:
200 
201         print(np.array(i.node,dtype=object))
202 
203         print('||')
204 
205         print('||')
206 
207         print('||')
208 
209         print('\/')
210 
211     print(np.array(close[-1].node,dtype=object))
212 
213 # 交换位置,并获得子节点
214 
215 def get_child(arr, e):
216 
217     arr_new = copy.deepcopy(arr)  # 深拷贝，复制一份新的节点
218 
219     r, c = find_local(arr_new, '0')  # 寻找0的位置的坐标
220 
221     r1, c1 = find_local(arr_new, e)  # 寻找可交换的位置的坐标
222 
223     # 交换位置
224 
225     arr_new[r][c], arr_new[r1][c1] = arr_new[r1][c1], arr_new[r][c]
226 
227     return arr_new
228 
229 # 寻找target的位置
230 
231 def find_local(arr, target):  # arr是节点的list，target是寻找的目标
232 
233     for i in arr:
234 
235         for j in i:
236 
237             if j == target:
238 
239                 return arr.index(i), i.index(j)  # 返回target的下标
240 
241 def best_path(n):
242 
243     if n.parent == None:
244 
245         return
246 
247     else:
248 
249         print("↑")
250 
251         print(np.array(n.parent.node,dtype=object))
252 
253         best_path(n.parent)
254 
255 def demo():
256 
257     print("""
258 
259     在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,
260 
261     每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：
262 
263     与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。
264 
265  
266 
267     本方法使用启发式
268 
269     启发式有两种途径(贪婪式和A*)
270 
271     为了达到最优解，运用A*算法
272 
273     """)
274 
275     print("-" * 50)
276 
277     print("1.本程序解决的是八数码问题(基于启发式途径解决)")
278 
279     print("2.输入的数码为按行输入换行需加空格再输入")
280 
281     print("3.例如：")
282 
283     print("         1 2 3\n         4 5 6\n         7 8 9")
284 
285     print("它的输入表示为：'123 456 789'")
286 
287     print("-" * 50)
288 
289 if __name__ == '__main__':
290 
291     demo()
292 
293     initStr = input("按要求输入初始状态")
294 
295     endStr = input("按要求输入最终状态")
296 
297     if isSolution(initStr,endStr):
298 
299         init_arr=string_to_list(initStr)
300 
301         end_arr=string_to_list(endStr)
302 
303         inital_arr=Node(init_arr,parent=None,cost=0,nd_nums=not_digits(init_arr,end_arr))
304 
305         AStar_ND(inital_arr,end_arr)
306 
307     else:
308 
309         print("此初始序列到不了目的序列，问题无解！！！")

三、 程序部分说明解释

def demo():本程序的展示窗口为一些特别性的介绍和解决哪类问题

def isSolution(initState,endState):这个函数是来判断初始序列到目的序列是可达的，基于（两者逆序数是否同奇或同偶）

def string_to_list(str):此函数将输入的字符转化成对应代表真实矩阵维度的列表

class Node:定义的节点类，同样它有cost属性（代表从初始序列到现节点序列的花费值），node属性（代表本节点序列），parent属性（代表此节点的父节点），nd_nums属性（代表为此状态离目标状态的差距，本算法用的是不再为位数即：nd_nums为不在位数），Node类有一个方法为get_children，它可以获取本节点的子节点有哪些并返回。

def Nodes_change(arr):获取空格可以交换的节点（即空格可以移动的位置）

def reverseOrdinalNum(numString):计算numString字符序列的逆序数

def get_child(arr, e):在arr节点中，e为空格可以移动的位置节点（也就是其子节点），将空格和向对应方向运动通过交换的方式进行移动变化。

def search_line(close): 打印出一整个的搜索路径

def AStar_ND(initial_arr, end_arr): 此函数为A*算法-不在位数算法实现主体。

def not_digits(arr1, arr2):计算此状态arr1与目的状态arr2之间的不在位数。

四、调试过程中容易出现的错误