N數碼問題的啟發式搜尋演算法--A*演算法python實現
- 一、 啟發式搜尋： A演算法
1）評價函式的一般形式 : f(n) = g(n) + h(n)
g(n):從S0到Sn的實際代價(搜尋的橫向因子)
h(n):從N到目標節點的估計代價,稱為啟發函式(搜尋的縱向因子);
特點 : 效率高, 無回溯,
搜尋演算法
OPEN表 : 存放待擴充套件的節點.
CLOSED表 : 存放已被擴充套件過的節點.
2）評價函式 f(x) = g(x) + h(x)
當 f(x) = g(x) 時，為寬度優先搜尋
當 f(x) = 1/g(x)時，為深度優先搜尋
當 f(x) = h(x) 時，為全域性優先搜尋
比較 f(x)大小，決定節點搜尋順序，即在OPEN表中的順序
3)Step1: 把初始節點S0放入OPEN表中;
Step2: 若OPEN表為空,則搜尋失敗,退出.
Step3: 移出OPEN中第一個節點N放入CLOSED表 中 , 並標以順序號n;
Step4: 若目標節點Sg=N, 則搜尋成功,結束.
Step5: 若N不可擴充套件, 則轉Step2;
Step6: 擴充套件 N, 生成一組子節點, 對這組子節點作如下處理後, 放入 OPEN表, 按f值 重新排序 OPEN表, 轉 Step2;
刪除重複節點和修改返回指標處理 .
- 二、 啟發式搜尋： A*演算法
1）評價函式的一般形式:
f(n) = g(n) + h(n) 且 h(n) <= h*(n)
g(n),h(n):定義同A演算法;
h*(n):從N到目標節點的最短路徑; 稱此時的 A演算法為A*演算法.
2）程式關鍵點
節點的擴充套件：close表存放已經擴充套件後的狀態，open表存放未擴充套件的狀態。首先獲取節點能擴充套件的方向，擴充套件後將父節點放入close表中，如果轉移之後的節點，既不在close表也不再open表，表明該節點還未被擴充套件，則插入open表，如果在close表中表明之前已經擴充套件過該狀態，為了避免無限擴充套件應將該狀態從open表捨棄，如果在open表則比較這兩個矩陣的f值（選取最優解），留小的在open表，之後對open表中的節點根據f值進行排序，pop出f值最小的節點進行擴充套件，依次進行該過程，直至該節點為目標狀態。
- 三、python程式碼實現
1 # -*- coding: utf-8 -*-
2 """
3 Created on Sun Sep 16 14:31:40 2018
4 A*演算法解決N數碼問題
5 執行程式後如下是輸入格式:
6請輸入矩陣的行數
7
83輸入對應的N
9請輸入初始矩陣A
10
111 0 2一行行輸入，每行數字空格隔開，每行最後一個數字輸入完成後直接回車開始輸入第二行
12
134 5 6
14
153 7 8
16請輸入目標矩陣B
17
181 2 3
19
208 0 4
21
227 6 5
23
24 """
25 import numpy as np
26 import copy
27 import time
28 from operator import itemgetter
29
30 goal = {}
31
32 def get_location(vec, num):#根據num元素獲取num在矩陣中的位置
33row_num = vec.shape[0]#numpy-shape函式獲得矩陣的維數
34line_num = vec.shape[1]
35
36for i in range(row_num):
37for j in range(line_num):
38if num == vec[i][j]:
39return i, j
40
41 def get_actions(vec):#獲取當前位置可以移動的下一個位置，返回移動列表
42row_num = vec.shape[0]
43line_num = vec.shape[1]
44
45(x, y) = get_location(vec, 0)#獲取0元素的位置
46action = [(0, 1), (0, -1), (1, 0), (-1, 0)]
47
48if x == 0:#如果0在邊緣則依據位置情況，減少0的可移動位置
49action.remove((-1, 0))
50if y == 0:
51action.remove((0, -1))
52if x == row_num - 1:
53action.remove((1, 0))
54if y == line_num - 1:
55action.remove((0, 1))
56
57return list(action)
58
59 def result(vec, action):#移動元素，進行矩陣轉化
60(x, y) = get_location(vec, 0)#獲取0元素的位置
61(a, b) = action#獲取可移動位置
62
63n = vec[x+a][y+b]#位置移動，交換元素
64s = copy.deepcopy(vec)
65s[x+a][y+b] = 0
66s[x][y] = n
67
68return s
69
70 def get_ManhattanDis(vec1, vec2):#計算兩個矩陣的曼哈頓距離,vec1為目標矩陣,vec2為當前矩陣
71row_num = vec1.shape[0]
72line_num = vec1.shape[1]
73dis= 0
74
75for i in range(row_num):
76for j in range(line_num):
77if vec1[i][j] != vec2[i][j] and vec2[i][j] != 0:
78k, m = get_location(vec1, vec2[i][j])
79d = abs(i - k) + abs(j - m)
80dis += d
81
82return dis
83
84 def expand(p, actions, step):#actions為當前矩陣的可擴充套件狀態列表,p為當前矩陣,step為已走的步數
85children = []#children用來儲存當前狀態的擴充套件節點
86for action in actions:
87child = {}
88child['parent'] = p
89child['vec'] = (result(p['vec'], action))
90child['dis'] = get_ManhattanDis(goal['vec'], child['vec'])
91child['step'] = step + 1#每擴充套件一次當前已走距離加1
92child['dis'] = child['dis'] + child['step']#更新該節點的f值f=g+h（step+child[dis]）
93child['action'] = get_actions(child['vec'])
94children.append(child)
95
96return children
97
98 def node_sort(nodelist):#按照節點中字典的距離欄位對列表進行排序,從大到小
99return sorted(nodelist, key = itemgetter('dis'), reverse=True)
100
101 def get_input(num):
102A = []
103for i in range(num):
104temp = []
105p = []
106s = input()
107temp = s.split(' ')
108for t in temp:
109t = int(t)
110p.append(t)
111A.append(p)
112
113return A
114
115 def get_parent(node):
116q = {}
117q = node['parent']
118return q
119
120 def test():
121openlist = []#open表
122close = []#儲存擴充套件的父節點
123
124print('請輸入矩陣的行數')
125num = int(input())
126
127print("請輸入初始矩陣A")
128A = get_input(num)
129
130print("請輸入目標矩陣B")
131B = get_input(num)
132
133print("請輸入結果檔名")
134resultfile = input()
135
136goal['vec'] = np.array(B)#建立矩陣
137
138p = {}
139p['vec'] = np.array(A)
140p['dis'] = get_ManhattanDis(goal['vec'], p['vec'])
141p['step'] = 0
142p['action'] = get_actions(p['vec'])
143p['parent'] = {}
144
145if (p['vec'] == goal['vec']).all():
146return
147
148openlist.append(p)
149
150start_CPU = time.clock()#開始擴充套件時CPU開始計算
151
152while openlist:
153
154children = []
155
156node = openlist.pop()#node為字典型別，pop出open表的最後一個元素
157close.append(node)#將該元素放入close表
158
159if (node['vec'] == goal['vec']).all():#比較當前矩陣和目標矩陣是否相同
160end_CPU = time.clock()#CPU結束計算
161
162h = open(resultfile,'w',encoding='utf-8',)#將結果寫入檔案並在控制檯輸出
163h.write('搜尋樹規模：' + str(len(openlist)+len(close)) + '\n')
164h.write('close：' + str(len(close)) + '\n')
165h.write('openlist：' + str(len(openlist)) + '\n')
166h.write('cpu執行時間：' + str(end_CPU - start_CPU) + '\n')
167h.write('路徑長：' + str(node['dis']) + '\n')
168
169h.write('解的路徑：' + '\n')
170i = 0
171way = []
172while close:
173way.append(node['vec'])#從最終狀態開始依次向上回溯將其父節點存入way列表中
174node = get_parent(node)
175if(node['vec'] == p['vec']).all():
176way.append(node['vec'])
177break
178while way:
179i += 1
180h.write(str(i) + '\n')
181h.write(str(way.pop()) + '\n')
182h.close()
183f = open(resultfile,'r',encoding='utf-8',)
184print(f.read())
185
186return
187
188children = expand(node, node['action'], node['step'])#如果不是目標矩陣，對當前節點進行擴充套件，取矩陣的可能轉移情況
189
190for child in children:#如果轉移之後的節點，既不在close表也不再open表則插入open表，如果在close表中則捨棄，如果在open表則比較這兩個矩陣的f值，留小的在open表
191f = False
192flag = False
193j = 0
194for i in range(len(openlist)):
195if (child['vec'] == openlist[i]['vec']).all():
196j = i
197flag = True
198break
199for i in range(len(close)):
200if(child['vec'] == close[i]).all():
201f = True
202break
203iff == False and flag == False :
204openlist.append(child)
205
206elif flag == True:
207if child['dis'] < openlist[j]['dis']:
208del openlist[j]
209openlist.append(child)
210
211
212openlist = node_sort(openlist)#對open表進行從大到小排序
213
214 test()
- 四、 程式執行結果如下圖所示
圖 1
圖 2
圖 3
- 五、 總結
通過這次程式設計瞭解到了搜尋具有探索性，要提高搜尋效率 (儘快地找到目標節點)，或要找最佳路徑(最佳解)就必須注意搜尋策略。對於狀態圖搜尋，已經提出了許多策略，它們大體可分為盲目搜尋（bland search)和啟發式搜尋（heuristic search）兩大類。其中盲目搜尋是無嚮導搜尋。啟發式搜尋是有嚮導搜尋，即利用啟發資訊（函式）引導去尋找問題解。通過A*演算法解決N數碼問題實驗過程中也遇到很多問題，比如節點擴充套件的方向問題等，通過這次實驗不僅鍛鍊了自己python程式設計能力，也讓自己對N數碼求解最優路徑問題有了更清晰的認識，希望自己能在老師和同學的幫助下，能不斷進步，當然最重要的是自己得付出，只會幻想而不行動的人,永遠也體會不到收穫果實時的喜悅。加油！！