八数码难题：设问题的初始状态为 S0 和指标状态 Sg，如图所示。请用 A * 算法求解。（定义两种以上的评估函数，别离给出搜寻树和计算过程，并进行不同评估函数的比照剖析）
初始状态 指标状态
2
8
3
1
2
3
1
4
8
4
7
6
5
7
6
5
启发函数（3 种启发函数，能够比拟优劣）：
复制代码
1 def Heuristic(self, list_end): # 启发函数, list_end 是指标状态的八数码
2 self.key = self.h = 0
3 ”’ 启发函数中 h(n) 的求解 ”’
4 # ”’ 1. n 状态时，不在指标状态的数码个数
5 for i in range(9):
6 self.h += 0 if self.digits[i] == list_end[i] else 1
7 # ”’
8
9 # ”’2. n 状态时，不在指标状态的数码挪动到指标状态时的间隔 – 曼哈顿间隔
10 for i in range(1, 9):
11 idx_end = list_end.index(i)
12 idx_self = self.digits.index(i)
13 self.h += abs(idx_end – idx_self) // 3 + abs(idx_end – idx_self – (idx_end – idx_self) // 3 * 3)
14 # ”’
15
16 # ”’3. 数码排成一行，n 状态时，不在指标状态的数码挪动到指标状态时的间隔
17 for i in range(1, 9):
18 idx_end = list_end.index(i)
19 idx_self = self.digits.index(i)
20 self.h += abs(idx_end – idx_self)
21 # ”’
22 self.key = self.h + self.d # 启发函数
复制代码
利用优先队列求解八数码问题:
构造体：蕴含启发函数，数码状态，以及解的门路。选用其中一种启发函数。
复制代码
1 # 设计八数码问题的数据结构
2 class Eight_Node:
3 def __init__(self):
4 self.key = 0 # 启发函数 key = f(n) = d(n) + h(n)
5 self.h = 0 # h(n), 依据 Heuristic(self, list_end) 函数求解 h(n) 与 f(n)
6 self.d = 0 # 树高
7 self.digits = list()*9 # 矩阵, 一行示意
8 self.solutionTree = list() # 解的过程
9
10 def __gt__(self, other):
11 return self.key > other.key
12
13 def Heuristic(self, list_end): # 启发函数, list_end 是指标状态的八数码
14 self.key = self.h = 0
15 ”’ 启发函数中 h(n) 的求解 ”’
16 ”’ 1. n 状态时，不在指标状态的数码个数
17 for i in range(9):
18 self.h += 0 if self.digits[i] == list_end[i] else 1
19 ”’
20
21 ”’2. n 状态时，不在指标状态的数码挪动到指标状态时的间隔 – 曼哈顿间隔
22 for i in range(1, 9):
23 idx_end = list_end.index(i)
24 idx_self = self.digits.index(i)
25 self.h += abs(idx_end – idx_self) // 3 + abs(idx_end – idx_self – (idx_end – idx_self) // 3 * 3)
26 ”’
27
28 # ”’3. 数码排成一行，n 状态时，不在指标状态的数码挪动到指标状态时的间隔
29 for i in range(1, 9):
30 idx_end = list_end.index(i)
31 idx_self = self.digits.index(i)
32 self.h += abs(idx_end – idx_self)
33 # ”’
34 self.key = self.h + self.d # 启发函数
复制代码
解函数：
复制代码
1 def Solve_Eight_Node(start_list1, end_list2): # 函数求解
2 start_node = Eight_Node() # 初始状态
3 end_node = Eight_Node() # 指标状态
4 # 初始状态 start_node，指标状态 end_node，构建八数码
5 start_node.digits = start_list1
6 start_node.solutionTree.append(start_node.digits)
7 end_node.digits = end_list2
8 start_node.Heuristic(end_node.digits)
9 # close 表
10 dic = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 上、下、左、右 – 数码挪动
11 close_base = list() # close_base 记录所有应用过的状态，也可用于去重
12 close_base.append(”.join(str(i) for i in start_node.digits))
13
14 # 优先队列，以启发函数升序
15 priQu = PriorityQueue() # open 表，优先队列实现
16 priQu.put(start_node)
17 # 开始搜寻
18 conclusion = Eight_Node() # 记录搜寻到的后果
19 while not priQu.empty():
20 node = priQu.get()
21 if node.h == 0: # 查找到指标状态，完结，启发函数为 0，和指标状态一样
22 conclusion = node
23 break
24 # 数码进行挪动，解决四个方向
25 idx = node.digits.index(0)
26 x = idx // 3 # 0 于八数码地位的坐标(0,0) <= (x,y) <= (2,2)
27 y = idx – 3 * x
28 for i in range(4): # 0,1,2,3, 别离和上下左右的方块替换
29 new_x = x + dici
30 new_y = y + dici
31 if 0 <= new_x <= 2 and 0 <= new_y <= 2: # 未超过边界
32 new_node = Eight_Node()
33 new_node.digits = copy.deepcopy(node.digits) # 深度复制八数码矩阵
34 new_node.solutionTree = copy.deepcopy(node.solutionTree) # 深度复制八数码解过程
35 new_node.digits[idx] = new_node.digits[new_x * 3 + new_y] # 数码挪动
36 new_node.digits[new_x * 3 + new_y] = 0
37 new_node.d = node.d + 1 # 树高加一
38 new_node.Heuristic(end_node.digits) # 计算 key,h，启发函数
39 new_node.solutionTree.append(new_node.digits) # 解过程减少一个状态
40 node_str = ”.join(str(j) for j in new_node.digits)
41 if node_str not in close_base: # 判重
42 close_base.append(node_str)
43 priQu.put(new_node)
44 return conclusion
复制代码
全副代码；
复制代码
1 from queue import PriorityQueue
2 import copy
3
4 # 设计八数码问题的数据结构
5 class Eight_Node:
6 def __init__(self):
7 self.key = 0 # 启发函数 key = f(n) = d(n) + h(n)
8 self.h = 0 # h(n), 依据 Heuristic(self, list_end) 函数求解 h(n) 与 f(n)
9 self.d = 0 # 树高
10 self.digits = list()*9 # 矩阵, 一行示意
11 self.solutionTree = list() # 解的过程
12
13 def __gt__(self, other):
14 return self.key > other.key
15
16 def Heuristic(self, list_end): # 启发函数, list_end 是指标状态的八数码
17 self.key = self.h = 0
18 ”’ 启发函数中 h(n) 的求解 ”’
19 ”’ 1. n 状态时，不在指标状态的数码个数
20 for i in range(9):
21 self.h += 0 if self.digits[i] == list_end[i] else 1
22 ”’
23
24 ”’2. n 状态时，不在指标状态的数码挪动到指标状态时的间隔 – 曼哈顿间隔
25 for i in range(1, 9):
26 idx_end = list_end.index(i)
27 idx_self = self.digits.index(i)
28 self.h += abs(idx_end – idx_self) // 3 + abs(idx_end – idx_self – (idx_end – idx_self) // 3 * 3)
29 ”’
30
31 # ”’3. 数码排成一行，n 状态时，不在指标状态的数码挪动到指标状态时的间隔
32 for i in range(1, 9):
33 idx_end = list_end.index(i)
34 idx_self = self.digits.index(i)
35 self.h += abs(idx_end – idx_self)
36 # ”’
37 self.key = self.h + self.d # 启发函数
38
39
40 def Solve_Eight_Node(start_list1, end_list2): # 函数求解
41 start_node = Eight_Node() # 初始状态
42 end_node = Eight_Node() # 指标状态
43 # 初始状态 start_node，指标状态 end_node，构建八数码
44 start_node.digits = start_list1
45 start_node.solutionTree.append(start_node.digits)
46 end_node.digits = end_list2
47 start_node.Heuristic(end_node.digits)
48 # close 表
49 dic = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 上、下、左、右 – 数码挪动
50 close_base = list() # close_base 记录所有应用过的状态，也可用于去重
51 close_base.append(”.join(str(i) for i in start_node.digits))
52
53 # 优先队列，以启发函数升序
54 priQu = PriorityQueue() # open 表，优先队列实现
55 priQu.put(start_node)
56 # 开始搜寻
57 conclusion = Eight_Node() # 记录搜寻到的后果
58 while not priQu.empty():
59 node = priQu.get()
60 if node.h == 0: # 查找到指标状态，完结，启发函数为 0，和指标状态一样
61 conclusion = node
62 break
63 # 数码进行挪动，解决四个方向
64 idx = node.digits.index(0)
65 x = idx // 3 # 0 于八数码地位的坐标(0,0) <= (x,y) <= (2,2)
66 y = idx – 3 * x
67 for i in range(4): # 0,1,2,3, 别离和上下左右的方块替换
68 new_x = x + dici
69 new_y = y + dici
70 if 0 <= new_x <= 2 and 0 <= new_y <= 2: # 未超过边界
71 new_node = Eight_Node()
72 new_node.digits = copy.deepcopy(node.digits) # 深度复制八数码矩阵
73 new_node.solutionTree = copy.deepcopy(node.solutionTree) # 深度复制八数码解过程
74 new_node.digits[idx] = new_node.digits[new_x * 3 + new_y] # 数码挪动
75 new_node.digits[new_x * 3 + new_y] = 0
76 new_node.d = node.d + 1 # 树高加一
77 new_node.Heuristic(end_node.digits) # 计算 key,h，启发函数
78 new_node.solutionTree.append(new_node.digits) # 解过程减少一个状态
79 node_str = ”.join(str(j) for j in new_node.digits)
80 if node_str not in close_base: # 判重
81 close_base.append(node_str)
82 priQu.put(new_node)
83 return conclusion
84
85
86 if name == “__main__”:
87 start_list = list(map(int, input(“ 请输出处于初始状态的八数码（一行输出即可）：”).split(“,”)))
88 end_list = list(map(int, input(“ 请输出处于指标状态的八数码（一行输出即可）：”).split(“,”)))
89 result = Solve_Eight_Node(start_list, end_list)
90 print(“ 八数码问题的求解：”)
91 print(“ 初始状态 指标状态 ”)
92 for i in range(3):
93 print(start_list[3 i:3 i + 3], ‘ ‘, end_list[3 i:3 i + 3])
94 print(“ 求解树：”)
95 index_i = 0
96 for li in result.solutionTree:
97 print(“step # %d：” % index_i)
98 for i in range(3):
99 print(li[3 i:3 i + 3])
100 print(“———–“)
101 index_i += 1
102 # 2,8,3,1,0,4,7,6,5 [0,1,2,3,4,5,6,7,8] [1,2,3,8,0,4,7,6,5] [0,1,2,3,4,5,6,7,8]
103 # 1,2,3,8,0,4,7,6,5 [8,7,6,5,4,3,2,1,0] [2,1,6,4,0,8,7,5,3] [8,7,6,5,4,3,2,1,0]
复制代码