基于Python的A*算法解決八數(shù)碼問題實現(xiàn)步驟
一、問題描述
八數(shù)碼問題是人工智能領(lǐng)域一個經(jīng)典的問題。也是我們所熟悉的最簡單的3×3數(shù)字華容道游戲:在一個3×3的九宮格棋盤上,擺有8個正方形方塊,每一個方塊都標有1~8中的某一個數(shù)字。棋盤中留有一個空格,要求按照每次只能將與空格相鄰的方塊與空格交換的原則,將任意擺放的數(shù)碼盤(初始狀態(tài))逐步擺成某種給定的數(shù)碼盤的排列方式(目標狀態(tài))。
二、涉及算法
啟發(fā)式搜索又稱為有信息搜索,是利用問題擁有啟發(fā)信息引導(dǎo)搜索,以達到減小搜索范圍、降低問題復(fù)雜度的目的。在啟發(fā)式搜索過程中,要對Open表進行排序,這就要有一種方法來計算待擴展結(jié)點有希望通向目標結(jié)點的不同程度,人們總是希望找到最有可能通向目標結(jié)點的待擴展結(jié)點優(yōu)先擴展。一種最常用的方法是定義一個評價函數(shù)對各個結(jié)點進行計算,其目的就是用來估算出“有希望”的結(jié)點。用f來標記評價函數(shù),用f(n)表示結(jié)點n的評價函數(shù)值,并用f來排列等待擴展的結(jié)點,然后選擇具有最小f值的結(jié)點作為下一個要擴展的結(jié)點。
A*算法是一種有序搜索算法,其特點在于對評價函數(shù)的定義上。這個評估函數(shù)f使得在任意結(jié)點上其函數(shù)值f(n)能估算出結(jié)點S到結(jié)點n的最小代價路徑的代價與從節(jié)點n到某一目標節(jié)點的最小代價路徑的代價的總和,也就是說f(n)是約束通過結(jié)點n的一條最小代價路徑的代價的估計。
算法具體內(nèi)容見文獻:
https://wenku.baidu.com/view/4a80a40fa2161479171128de?_wkts_=1713600420821
三、實現(xiàn)步驟
在運行前,需要提前準備好infile.txt文件,第一行規(guī)定N的大小,即棋盤的大小,第二行則放置起始狀態(tài)棋盤中的數(shù)字排列,從上往下,從左往右一次排成一列,空格置為0。
1.定義狀態(tài)結(jié)點的類
定義一個State類,主要用于表示搜索過程中的狀態(tài)結(jié)點,包括結(jié)點的代價和狀態(tài)信息,以及結(jié)點之間的關(guān)系。
屬性:
- gn:從起始結(jié)點到當前結(jié)點的實際代價。
- hn:從當前結(jié)點到目標結(jié)點的估計代價(啟發(fā)式函數(shù))。
- fn:綜合代價,即gn+hn。
- child:子結(jié)點列表,存儲從當前結(jié)點可以到達的所有子結(jié)點。
- par:父結(jié)點,指向生成當前結(jié)點的父結(jié)點。
- state:當前結(jié)點的狀態(tài)矩陣。
- hash_value:當前結(jié)點狀態(tài)矩陣的哈希值,用于在查找表中快速查找。
方法:
- __lt__:小于運算符重載,用于結(jié)點比較。
- __eq__:等于運算符重載,用于結(jié)點比較。
- __ne__:不等于運算符重載,用于結(jié)點比較。
class State(object): def __init__(self, gn=0, hn=0, state=None, hash_value=None, par=None): self.gn = gn self.hn = hn self.fn = self.gn + self.hn self.child = [] self.par = par self.state = state self.hash_value = hash_value def __lt__(self, other): return self.fn < other.fn def __eq__(self, other): return self.hash_value == other.hash_value def __ne__(self, other): return not self.__eq__(other)
2.定義曼哈頓距離計算函數(shù)
計算兩個狀態(tài)結(jié)點之間的曼哈頓距離,作為啟發(fā)式函數(shù)的一部分,用于評估當前結(jié)點到目標結(jié)點的估計代價。
def manhattan_dis(cur_node, end_node): # 定義一個名為manhattan_dis的函數(shù),接受兩個參數(shù)cur_node(當前結(jié)點)和end_node(目標結(jié)點) # 獲取當前結(jié)點和目標結(jié)點的狀態(tài)矩陣 cur_state = cur_node.state end_state = end_node.state dist = 0 N = len(cur_state) # 獲取狀態(tài)矩陣的大小,假設(shè)為N # 遍歷狀態(tài)矩陣中的每個位置 for i in range(N): for j in range(N): # 如果當前結(jié)點的值與目標結(jié)點的值相等,則跳過當前位置,因為這個位置已經(jīng)在目標狀態(tài)中 if cur_state[i][j] == end_state[i][j]: continue num = cur_state[i][j] # 獲取當前結(jié)點在狀態(tài)矩陣中的值 # 如果當前結(jié)點的值為0(空白格),則將目標位置設(shè)置為狀態(tài)矩陣的右下角 if num == 0: x = N - 1 y = N - 1 # 如果當前結(jié)點的值不為0,則根據(jù)當前結(jié)點的值計算其目標位置,假設(shè)目標位置為(x,y) else: x = num / N y = num - N * x - 1 # 計算當前結(jié)點與目標位置之間的曼哈頓距離,并累加到總距離中 dist += (abs(x - i) + abs(y - j)) # 返回計算得到的曼哈頓距離作為當前結(jié)點到目標結(jié)點的估計代價 return dist
3.預(yù)留占位函數(shù)
test_fn是一個占位函數(shù),接受當前結(jié)點和目標結(jié)點作為參數(shù)。目前這個函數(shù)沒有實際的功能。
def test_fn(cur_node, end_node): return 0
4.生成子結(jié)點函數(shù)
創(chuàng)建generate_child函數(shù),接受當前結(jié)點cur_node、目標結(jié)點end_node、哈希集合hash_set、OPEN表open_table和距離函數(shù)dis_fn作為參數(shù)。實現(xiàn)了在當前結(jié)點基礎(chǔ)上生成可行的子結(jié)點,并考慮了重復(fù)狀態(tài)的處理,是A*算法中搜索過程的重要一步。
def generate_child(cur_node, end_node, hash_set, open_table, dis_fn): # 如果當前結(jié)點就是目標結(jié)點,則直接將目標結(jié)點假如OPEN表,并返回,表示已經(jīng)找到了解 if cur_node == end_node: heapq.heappush(open_table, end_node) return # 獲取當前結(jié)點狀態(tài)矩陣的大小 num = len(cur_node.state) # 遍歷當前結(jié)點狀態(tài)矩陣的每一個位置 for i in range(0, num): for j in range(0, num): # 如果當前位置不是空格,則跳過,因為空格是可以移動的位置 if cur_node.state[i][j] != 0: continue # 遍歷當前位置的四個鄰居位置,即上下左右四個方向 for d in direction: x = i + d[0] y = j + d[1] if x < 0 or x >= num or y < 0 or y >=num: continue # 記錄生成的結(jié)點數(shù)量 global SUM_NODE_NUM SUM_NODE_NUM += 1 # 交換空格和鄰居位置的數(shù)字,生成一個新的狀態(tài)矩陣 state = copy.deepcopy(cur_node.state) state[i][j], state[x][y] = state[x][y], state[i][j] # 計算新狀態(tài)矩陣的哈希值,并檢查是否已經(jīng)在哈希集合中存在,如果存在則表示已經(jīng)生成過相同的狀態(tài),跳過 h = hash(str(state)) if h in hash_set: continue # 將新狀態(tài)的哈希值添加到哈希集合中,計算新狀態(tài)結(jié)點的gn(從起始結(jié)點到當前結(jié)點的代價)和hn(當前結(jié)點到目標結(jié)點的估計代價) hash_set.add(h) gn = cur_node.gn + 1 hn = dis_fn(cur_node, end_node) # 創(chuàng)建新的狀態(tài)結(jié)點對象,并將其加入到當前結(jié)點的子結(jié)點列表中,并將其加入到OPEN表中。 node = State(gn, hn, state, h, cur_node) cur_node.child.append(node) heapq.heappush(open_table, node)
5.定義輸出路徑函數(shù)
定義了一個名為print_path的函數(shù),接受一個參數(shù)node,表示目標結(jié)點。通過回溯父結(jié)點的方式,從目標結(jié)點一直回溯到起始結(jié)點,并將沿途經(jīng)過的狀態(tài)矩陣打印出來,以展示搜索路徑。
def print_path(node): # 獲取從起始結(jié)點到目標結(jié)點的路徑長度,即目標結(jié)點的實際代價 num = node.gn # 定義了一個內(nèi)部函數(shù)show_block,用于打印狀態(tài)矩陣 def show_block(block): print("---------------") for b in block: print(b) # 創(chuàng)建一個棧,用于存儲路徑中經(jīng)過的結(jié)點 stack = [] # 從目標結(jié)點開始,沿著父結(jié)點指針一直回溯到起始結(jié)點,并將沿途經(jīng)過的狀態(tài)矩陣入棧 while node.par is not None: stack.append(node.state) node = node.par stack.append(node.state) # 從棧中依次取出狀態(tài)矩陣,并打印出來 while len(stack) != 0: t = stack.pop() show_block(t) # 返回路徑長度 return num
6.定義A*算法
定義A_start函數(shù),接受起始狀態(tài)start、目標狀態(tài)end、距離函數(shù)distance_fn、生成子結(jié)點函數(shù)generate_child_fn和可選的時間限制time_limit作為參數(shù)。實現(xiàn)了A*算法的整個搜索過程,包括結(jié)點的擴展、路徑的搜索和時間限制的處理。
def A_start(start, end, distance_fn, generate_child_fn, time_limit=10): # 創(chuàng)建起始狀態(tài)結(jié)點和目標狀態(tài)結(jié)點對象,并分別計算其哈希值 root = State(0, 0, start, hash(str(BLOCK)), None) end_state = State(0, 0, end, hash(str(GOAL)), None) # 檢查起始狀態(tài)是否就是目標狀態(tài),如果是,則直接輸出提示信息 if root == end_state: print("start == end !") # 將起始狀態(tài)結(jié)點加入到OPEN表中,并對OPEN表進行堆化操作 OPEN.append(root) heapq.heapify(OPEN) # 創(chuàng)建一個哈希集合,用于存儲已經(jīng)生成的狀態(tài)結(jié)點的哈希值,并將起始狀態(tài)結(jié)點的哈希值添加到集合中 node_hash_set = set() node_hash_set.add(root.hash_value) # 記錄算法開始的時間 start_time = datetime.datetime.now() # 進入主循環(huán),直到OPEN表為空(搜索完成)或達到時間限制 while len(OPEN) != 0: top = heapq.heappop(OPEN) # 如果當前結(jié)點就是目標狀態(tài)結(jié)點,則直接輸出路徑 if top == end_state: return print_path(top) # 產(chǎn)生孩子節(jié)點,孩子節(jié)點加入OPEN表 generate_child_fn(cur_node=top, end_node=end_state, hash_set=node_hash_set, open_table=OPEN, dis_fn=distance_fn) # 記錄當前時間 cur_time = datetime.datetime.now() # 超時處理,如果運行時間超過了設(shè)定的時間限制,則輸出超時提示信息并返回 if (cur_time - start_time).seconds > time_limit: print("Time running out, break !") print("Number of nodes:", SUM_NODE_NUM) return -1 # 如果循環(huán)結(jié)束時OPEN表為空,則表示沒有找到路徑,輸出提示信息并返回-1 print("No road !") # 沒有路徑 return -1
7.讀取數(shù)據(jù)作為原始狀態(tài)
定義read_block函數(shù),接受三個參數(shù)block(狀態(tài)矩陣列表)、line(輸入的一行數(shù)據(jù))、N(狀態(tài)矩陣的大小)。將文本數(shù)據(jù)解析為狀態(tài)矩陣的形式,并存儲在列表中,為后續(xù)的狀態(tài)表示和求解提供原始數(shù)據(jù)。
def read_block(block, line, N): # 使用正則表達式提取輸入行中的數(shù)字數(shù)據(jù),并存儲在列表res中 pattern = re.compile(r'\d+') # 正則表達式提取數(shù)據(jù) res = re.findall(pattern, line) # 初始化計數(shù)變量t和臨時列表tmp t = 0 tmp = [] # 遍歷提取的數(shù)字數(shù)據(jù),將其轉(zhuǎn)換為整數(shù),并添加到臨時列表tmp中 for i in res: t += 1 tmp.append(int(i)) # 當計數(shù)變量t達到狀態(tài)矩陣的大小N時,表示當前行數(shù)據(jù)處理完畢,將臨時表添加到狀態(tài)矩陣列表中,并清空臨時表 if t == N: t = 0 block.append(tmp) tmp = []
8.定義主函數(shù)查看結(jié)果
通過主函數(shù)if __name__ == 'main'讀取輸入數(shù)據(jù)、調(diào)用A*算法求解八數(shù)碼問題,并輸出求解結(jié)果的相關(guān)信息。
if __name__ == '__main__': # 嘗試打開infile.txt文件,如果文件打開失敗,則輸出錯誤信息并退出程序 try: file = open('infile.txt', "r") except IOError: print("can not open file infile.txt !") exit(1) # 打開名為infile.txt文件,并將文件對象賦值給變量f f = open("infile.txt") # 讀取文件的第一行,獲取棋盤的大小NUMBER NUMBER = int(f.readline()[-2]) # 根據(jù)棋盤大小生成目標狀態(tài),并將目標狀態(tài)存儲在列表GOAL中 n = 1 for i in range(NUMBER): l = [] for j in range(NUMBER): l.append(n) n += 1 GOAL.append(l) GOAL[NUMBER - 1][NUMBER - 1] = 0 # 逐行讀取文件中的數(shù)據(jù) for line in f: # 讀取每一行數(shù)據(jù) # 在每次處理新的輸入數(shù)據(jù)之前,需要清空OPEN表和BLOCK表 OPEN = [] BLOCK = [] # 調(diào)用讀取數(shù)據(jù)的函數(shù),將當前行的數(shù)據(jù)解析并存儲為狀態(tài)矩陣 read_block(BLOCK, line, NUMBER) # 初始化生成的結(jié)點數(shù)量為0 SUM_NODE_NUM = 0 # 記錄算法開始的時間 start_t = datetime.datetime.now() # 這里添加5秒超時處理,可以根據(jù)實際情況選擇啟發(fā)函數(shù) # 將求解路徑長度存儲在length中 length = A_start(BLOCK, GOAL, manhattan_dis, generate_child, time_limit=10) # 記錄算法結(jié)束時間 end_t = datetime.datetime.now() # 如果找到了路徑,則輸出路徑長度、算法執(zhí)行時間和生成的結(jié)點數(shù)量 if length != -1: print("length =", length) print("time =", (end_t - start_t).total_seconds(), "s") print("Nodes =", SUM_NODE_NUM)
四、運行結(jié)果
A*算法在解決八數(shù)碼問題中表現(xiàn)出較高的準確性。通過啟發(fā)式函數(shù)曼哈頓距離的計算,能夠較準確的評估當前結(jié)點到目標節(jié)點的代價,并在搜索過程中選擇代價最小的路徑。通過和實際路徑長度的比較,可以驗證算法的準確性。
同時,A*算法在搜索過程中充分利用了啟發(fā)式函數(shù)的估計值,能夠更優(yōu)先的擴展可能更接近目標的結(jié)點,從而提高搜索效率,但是,在某些復(fù)雜的情況下,仍可能耗費較長時間或無法找到解,這取決于問題的復(fù)雜度和啟發(fā)式函數(shù)的選擇。
以下結(jié)果顯示的是從初始狀態(tài)轉(zhuǎn)變成目標狀態(tài)的一個具體過程。
--------------- [7, 2, 6] [8, 1, 4] [3, 5, 0] --------------- [7, 2, 6] [8, 1, 0] [3, 5, 4] --------------- [7, 2, 0] [8, 1, 6] [3, 5, 4] --------------- [7, 0, 2] [8, 1, 6] [3, 5, 4] --------------- [7, 1, 2] [8, 0, 6] [3, 5, 4] --------------- [7, 1, 2] [8, 5, 6] [3, 0, 4] --------------- [7, 1, 2] [8, 5, 6] [0, 3, 4] --------------- [7, 1, 2] [0, 5, 6] [8, 3, 4] --------------- [0, 1, 2] [7, 5, 6] [8, 3, 4] --------------- [1, 0, 2] [7, 5, 6] [8, 3, 4] --------------- [1, 5, 2] [7, 0, 6] [8, 3, 4] --------------- [1, 5, 2] [7, 3, 6] [8, 0, 4] --------------- [1, 5, 2] [7, 3, 6] [8, 4, 0] --------------- [1, 5, 2] [7, 3, 0] [8, 4, 6] --------------- [1, 5, 2] [7, 0, 3] [8, 4, 6] --------------- [1, 5, 2] [7, 4, 3] [8, 0, 6] --------------- [1, 5, 2] [7, 4, 3] [0, 8, 6] --------------- [1, 5, 2] [0, 4, 3] [7, 8, 6] --------------- [1, 5, 2] [4, 0, 3] [7, 8, 6] --------------- [1, 0, 2] [4, 5, 3] [7, 8, 6] --------------- [1, 2, 0] [4, 5, 3] [7, 8, 6] --------------- [1, 2, 3] [4, 5, 0] [7, 8, 6] --------------- [1, 2, 3] [4, 5, 6] [7, 8, 0] length = 22 time = 0.09839 s Nodes = 8274 進程已結(jié)束,退出代碼為 0
五、完整代碼
import heapq import copy import re import datetime BLOCK = [] GOAL = [] direction = [[0, 1], [0, -1], [1, 0], [-1, 0]] OPEN = [] SUM_NODE_NUM = 0 class State(object): def __init__(self, gn=0, hn=0, state=None, hash_value=None, par=None): self.gn = gn self.hn = hn self.fn = self.gn + self.hn self.child = [] self.par = par self.state = state self.hash_value = hash_value def __lt__(self, other): return self.fn < other.fn def __eq__(self, other): return self.hash_value == other.hash_value def __ne__(self, other): return not self.__eq__(other) def manhattan_dis(cur_node, end_node): cur_state = cur_node.state end_state = end_node.state dist = 0 N = len(cur_state) for i in range(N): for j in range(N): if cur_state[i][j] == end_state[i][j]: continue num = cur_state[i][j] if num == 0: x = N - 1 y = N - 1 else: x = num / N y = num - N * x - 1 dist += (abs(x - i) + abs(y - j)) return dist def test_fn(cur_node, end_node): return 0 def generate_child(cur_node, end_node, hash_set, open_table, dis_fn): if cur_node == end_node: heapq.heappush(open_table, end_node) return num = len(cur_node.state) for i in range(0, num): for j in range(0, num): if cur_node.state[i][j] != 0: continue for d in direction: x = i + d[0] y = j + d[1] if x < 0 or x >= num or y < 0 or y >= num: continue global SUM_NODE_NUM SUM_NODE_NUM += 1 state = copy.deepcopy(cur_node.state) state[i][j], state[x][y] = state[x][y], state[i][j] h = hash(str(state)) if h in hash_set: continue hash_set.add(h) gn = cur_node.gn + 1 hn = dis_fn(cur_node, end_node) node = State(gn, hn, state, h, cur_node) cur_node.child.append(node) heapq.heappush(open_table, node) def print_path(node): num = node.gn def show_block(block): print("---------------") for b in block: print(b) stack = [] while node.par is not None: stack.append(node.state) node = node.par stack.append(node.state) while len(stack) != 0: t = stack.pop() show_block(t) return num def A_start(start, end, distance_fn, generate_child_fn, time_limit=10): root = State(0, 0, start, hash(str(BLOCK)), None) end_state = State(0, 0, end, hash(str(GOAL)), None) if root == end_state: print("start == end !") OPEN.append(root) heapq.heapify(OPEN) node_hash_set = set() node_hash_set.add(root.hash_value) start_time = datetime.datetime.now() while len(OPEN) != 0: top = heapq.heappop(OPEN) if top == end_state: return print_path(top) generate_child_fn(cur_node=top, end_node=end_state, hash_set=node_hash_set, open_table=OPEN, dis_fn=distance_fn) cur_time = datetime.datetime.now() if (cur_time - start_time).seconds > time_limit: print("Time running out, break !") print("Number of nodes:", SUM_NODE_NUM) return -1 print("No road !") return -1 def read_block(block, line, N): pattern = re.compile(r'\d+') res = re.findall(pattern, line) t = 0 tmp = [] for i in res: t += 1 tmp.append(int(i)) if t == N: t = 0 block.append(tmp) tmp = [] if __name__ == '__main__': try: file = open('infile.txt', "r") except IOError: print("can not open file infile.txt !") exit(1) f = open("infile.txt") NUMBER = int(f.readline()[-2]) n = 1 for i in range(NUMBER): l = [] for j in range(NUMBER): l.append(n) n += 1 GOAL.append(l) GOAL[NUMBER - 1][NUMBER - 1] = 0 for line in f: OPEN = [] BLOCK = [] read_block(BLOCK, line, NUMBER) SUM_NODE_NUM = 0 start_t = datetime.datetime.now() length = A_start(BLOCK, GOAL, manhattan_dis, generate_child, time_limit=10) end_t = datetime.datetime.now() if length != -1: print("length =", length) print("time =", (end_t - start_t).total_seconds(), "s") print("Nodes =", SUM_NODE_NUM)
總結(jié)
到此這篇關(guān)于基于Python的A*算法解決八數(shù)碼問題實現(xiàn)步驟的文章就介紹到這了,更多相關(guān) Python A*算法解決八數(shù)碼問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
用python實現(xiàn)的可以拷貝或剪切一個文件列表中的所有文件
python 實現(xiàn)剪切或是拷貝一個文件列表中的所有文件2009-04-04Python OpenCV實現(xiàn)基于模板的圖像拼接
基于特征點的圖像拼接如果是多張圖,每次計算變換矩陣,都有誤差,最后可以圖像拼完就變形很大,基于模板的方法可以很好的解決這一問題,本文就來和大家具體聊聊2022-10-10Python利用 SVM 算法實現(xiàn)識別手寫數(shù)字
支持向量機 (Support Vector Machine, SVM) 是一種監(jiān)督學(xué)習(xí)技術(shù),它通過根據(jù)指定的類對訓(xùn)練數(shù)據(jù)進行最佳分離,從而在高維空間中構(gòu)建一個或一組超平面。本文將介紹通過SVM算法實現(xiàn)手寫數(shù)字的識別,需要的可以了解一下2021-12-12pycharm無法安裝第三方庫的問題及解決方法以scrapy為例(圖解)
這篇文章主要介紹了pycharm無法安裝第三方庫的解決辦法以scrapy為例,本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-05-05python SQLAlchemy的Mapping與Declarative詳解
這篇文章主要介紹了python SQLAlchemy的Mapping與Declarative詳解,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-07-07python啟動應(yīng)用程序和終止應(yīng)用程序的方法
今天小編就為大家分享一篇python啟動應(yīng)用程序和終止應(yīng)用程序的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-06-06