N数码问题和A-Star 算法的介绍,网上讲解的有很多,基本意思都是一样的,所以在这里就不再做详细的介绍了,本文主要是讲解python实现A-Star算法对N数码问题的求解过程。

python代码实现

        以下是代码,并附有详细注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import numpy as np
import time
import copy
from operator import itemgetter

def get_loc(mat,num): #获取某个元素num的位置
for i in range(n):
for j in range(n):
if num == mat[i][j]:
return i,j

def get_dis(mat1,mat2): #计算当前矩阵和目标矩阵的曼哈顿距离
dis = 0
for i in range(n):
for j in range(n):
if mat1[i][j] != mat2[i][j] and mat2[i][j] != 0:
x , y = get_loc(mat1,mat2[i][j])
d = abs(i-x) + abs(j-y) #曼哈顿距离的计算
dis += d
return dis

def get_act(mat): #获取当前位置的下步可移动位置,可减少不必要的移动
x , y = get_loc(mat,0)
act = [(-1,0),(1,0),(0,-1),(0,1)] #对应的是上下左右
if x == 0:
act.remove((-1,0))
if y == 0:
act.remove((0,-1))
if x == n-1:
act.remove((1,0))
if y == n-1:
act.remove((0,1))

return list(act)

def move(mat,act): #移动交换元素
x , y = get_loc(mat,0)
(a , b) = act
h = mat[x+a][y+b]
s = copy.deepcopy(mat) #注意不能在原有矩阵移动,否则下次移动就不是在原本矩阵的移动
s[x+a][y+b] = 0
s[x][y] = h

return s

def expand(node,act,step): #节点扩展
children = []
for a in act:
child = {}
child['parent'] = node
child['mat'] = move(node['mat'],a)
child['dis'] = get_dis(goal['mat'],child['mat']) #h(n)
child['step'] = step + 1 #g(n)
child['dis'] = child['step'] + child['dis'] #f(n) = g(n) + h(n)
child['act'] = get_act(child['mat'])
children.append(child)

return children

def main():
A = [[2,8,3],[1,6,4],[7,0,5]] #初始矩阵,0表示空白
B = [[1,2,3],[8,0,4],[7,6,5]] #目标矩阵
openlist = []
closelist = []
global goal,n
goal = {}
goal['mat'] = np.array(B)
n = len(goal['mat'])

cs = {} #初始矩阵信息的配置
cs['mat'] = np.array(A) #存放矩阵
cs['dis'] = get_dis(cs['mat'],goal['mat']) #f(n)=g(n)+h(n),初始g(n)=0
cs['step'] = 0 #步数
cs['act'] = get_act(cs['mat']) #可移动位置列表
cs['parent'] = {} #存放父节点,初始无空

if (goal['mat'] == cs['mat']).all():
print("初始矩阵与目标矩阵相同,无需操作")
return

openlist.append(cs) #加入初始状态
start_time = time.perf_counter() #计时
while openlist:
children = []
node = openlist.pop()
closelist.append(node)

if (node['mat'] == goal['mat']).all(): #如果当前矩阵与目标矩阵相同,输出相关信息,退出
end_time = time.perf_counter()
print('步数:%d' % node['dis'])
print('运行时间:%f s' % (end_time-start_time))
print('解的路径:')
way = []
while closelist:
way.append(node['mat'])
node = node['parent'] #寻找当前节点的父节点,直至初始矩阵
if (node['mat'] == cs['mat']).all():
way.append(node['mat'])
break
print('初状态') #输出打印出移动过程
print(cs['mat'])
for i in range(1,len(way)):
print('\n第 %d 步' % i)
print(way[::-1][i])
return

children = expand(node,node['act'],node['step']) #如果当前矩阵与目标矩阵不相同,则节点扩展

for child in children:
f = flag = False
j = 0
for i in range(len(openlist)): #判断扩展后的节点是否在openlist中
if (child['mat'] == openlist[i]['mat']).all():
j = i
flag = True
break
for i in range(len(closelist)): #判断扩展后的节点是否在closelist中
if (child['mat'] == closelist[i]).all():
f = True
break
if f == False and flag == False: #如果扩展后的节点不在open和close中,则加入openlist中
openlist.append(child)
elif flag == True: #如果扩展后的节点已经在openlist中,则就行比较,保留路径较短的
if child['dis'] < openlist[j]['dis']:
del openlist[j]
openlist.append(child)

openlist = sorted(openlist,key = itemgetter('dis'),reverse = True) #对扩展后的新openlis按路径长度排序

if __name__ == '__main__':
main()