【人工智能】實驗報告及A*搜索方法走迷宮（基于曼哈頓距離）

2020-06-07 22:41 作者:Aiello筱郁 0人讀過 | 我要投稿

編譯器：Pycharm+Anaconda虛擬環(huán)境

Python版本：3.7

采用啟發(fā)函數(shù)：曼哈頓距離

一、關于理解八數(shù)碼問題

參考文章：https://blog.csdn.net/qq_41417335/article/details/86359831

????????????? ? https://www.runoob.com/python/python-att-dictionary-pop.html

????????? https://blog.csdn.net/yangysc/article/details/50710439

在正式開展A*算法的話題前我們或許需要花點時間來稍微捋一捋搜索算法在實現(xiàn)過程中的一些問題（筆記形式）。

解決八數(shù)碼經(jīng)典問題主要采取的三種方法：寬度優(yōu)先、深度優(yōu)先、A*算法

1.???? 寬度優(yōu)先同深度優(yōu)先

在參考給出的例代碼中寬度優(yōu)先和深度優(yōu)先都屬于遍歷類型的盲目搜索算法，唯一的區(qū)別就是書本上提到的：寬度優(yōu)先法是將n其余的子狀態(tài)按生成的順序加入到open表的后端，而深度優(yōu)先算法則是前端。對應代碼的編寫的不同之處就是對代碼中的“open”表（即“stack_layouts”）

正如參考文章中所說，只需將curLayout = stack_layouts.pop(0) 改作curLayout = stack_layouts.pop()，即可對應實現(xiàn)深度優(yōu)先搜索算法。原因就是pop和append兩個函數(shù)的性質(zhì)。

由于append和pop函數(shù)均是默認添加集合到列表末尾/移出列表最后一個集合，而curLayout = stack_layouts.pop(0)則是移除“stack_layouts”中首位集合，就實現(xiàn)了同一種open表存儲，不同的優(yōu)先展開（考察節(jié)點）的方式（前端優(yōu)先或后端優(yōu)先），同專業(yè)書（王萬良《人工智能及其應用》第3版·高等教育出版社，2016.2）上的改變添加方式是本質(zhì)相同的。

2.???? A*算法的理解

啟發(fā)函數(shù)h(x)同專業(yè)書上相同，是八數(shù)碼表中當前位置同目標位置相比較，處于不同位置的數(shù)字到達目標位所需移動的距離之和。在swap_chr函數(shù)（定義的交換數(shù)碼的函數(shù)）中，b是以一個數(shù)列的形式存儲的（對應九宮格的數(shù)），運用的組合方法則是切片再組合（分5個部分）。其中fn就是f(x)，deep就是g(x)，destLayout就是目標狀態(tài)。

3.???? 程序本身的實現(xiàn)

程序主要以以下三個字典來定義當前九宮格狀態(tài)（以數(shù)組表示的排列形式，搜索深度，當前狀態(tài)的fn值）：

????g_dict_layouts = {}
????g_dict_layouts_deep = {}
????g_dict_layouts_fn = {}

???

g_dict_shifts則是以字典形式定義了整個九宮格內(nèi)每個位置可以實現(xiàn)的移動交換方式：

?g_dict_shifts?=?{0:[1,?3],?1:[0,?2,?4],?2:[1,?5],
??????????????????????????????????3:[0,4,6],?4:[1,3,5,7],?5:[2,4,8],
??????????????????????????6:[3,7],??7:[4,6,8],?8:[5,7]}

一、關于走迷宮中的A*算法的實現(xiàn)

參考八數(shù)碼中的代碼格式，我在網(wǎng)上找尋了經(jīng)典的走迷宮問題，其中不乏有各種遍歷式的盲目算法，但運用啟發(fā)式的并且明確實現(xiàn)的很少，我便準備仿照建立字典表定義移動交換方式和具體狀態(tài)的方法以A*算法的方式實現(xiàn)最優(yōu)走迷宮。

參考文章：https://blog.csdn.net/qq_29681777/article/details/83719680

?????????????? ?https://blog.csdn.net/diamonjoy_zone/article/details/65630144

首先，我們需要有一個可解的迷宮maze（用1代表不可走的墻，用0代表可走的路），并且需要定義走迷宮的方法（上下左右四個方向，由于對于迷宮內(nèi)任何一個點我們都可以四個方向轉(zhuǎn)，于是就不用字典的表達方式而另加一個函數(shù)passable來判斷是否轉(zhuǎn)向是可行的）。之后我們仿照八數(shù)碼的形式建立我們的字典表格架構，修改原有的遞歸函數(shù)find_path并加入我們定義的啟發(fā)函數(shù)判斷方法，編寫find_path_A。

/修改前通過遞歸的方法實現(xiàn)的遍歷搜索可視化路徑（代碼中的find_path函數(shù)）

其中S代表開始位置，E代表目標終點，*為尋找到的路徑，#代表尋路中走過的無用路徑/

1.???? 最終代碼如下：

import math
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]? # 當前位置四個方向的偏移量,即可以轉(zhuǎn)動的四個方向
path = []? # 存找到的路徑
#仿照八數(shù)碼解決方法中的表結(jié)構
g_dict_layouts = {}
g_dict_layouts_deep = {} #深度
g_dict_layouts_fn = {} #啟發(fā)函數(shù)值

def mark(maze, pos):? # 給迷宮maze的位置pos標"2"表示“倒過了”
??? maze[pos[0]][pos[1]] = 2

def passable(maze, pos):? # 檢查迷宮maze的位置pos是否可通行
??? return maze[pos[0]][pos[1]] == 0

#啟發(fā)函數(shù)
def get_dist(pos, end):
??????? return math.sqrt((end[0]-pos[0])*(end[0]-pos[0]))+ math.sqrt((end[1]-pos[1])*(end[1]-pos[1]))
??????? #曼哈頓距離

def turn_best(pos, i, deep, end):
??? nextp = pos[0] + i[0], pos[1] + i[1] ##注意修改后的維度##
??? #存儲fn啟發(fā)函數(shù)值,A*算法
??? fn = get_dist(nextp, end) + deep
??? return nextp, fn

#修改后的A*解決法
def find_path_A(maze,pos,end):
??? # 構建開始節(jié)點和表格
??? g_dict_layouts[pos] = -1
??? g_dict_layouts_deep[pos] = 1
??? g_dict_layouts_fn[pos] = 1 + get_dist(pos, end)
??? stack_layouts = []
??? stack_layouts.append(pos)? # 當前狀態(tài)存入列表

??? while len(stack_layouts) > 0:
??????? mark(maze, pos)#標記走到的位置
??????? curLayout = min(g_dict_layouts_fn, key=g_dict_layouts_fn.get)
??????? print(curLayout)
??????? del g_dict_layouts_fn[curLayout]
??????? stack_layouts.remove(curLayout)? #找到最小fn，并移除,擴展節(jié)點向下搜尋

??????? if curLayout == end:? # 判斷當前狀態(tài)是否為目標狀態(tài)
??????????? break
??????? lst_shifts = dirs? # 當前可進行移動的四個方向，接下來對每個方向進行可行性判斷
??????? for nShift in lst_shifts:
??????????? newLayout, fn = turn_best(curLayout, nShift, g_dict_layouts_deep[curLayout] + 1, end)
??????????? if g_dict_layouts.get(newLayout) == None:? # 判斷交換后的狀態(tài)是否已經(jīng)查詢過
??????????????? if passable(maze, newLayout):? # 不可行的相鄰位置不管
??????????????????? g_dict_layouts_deep[newLayout] = g_dict_layouts_deep[curLayout] + 1? # 存入深度
??????????????????? g_dict_layouts_fn[newLayout] = fn? # 存入fn
??????????????????? g_dict_layouts[newLayout] = curLayout? # 定義前驅(qū)結(jié)點
??????????????? stack_layouts.append(newLayout)? # 存入集合

??? path.append(curLayout) #存入每次找到的最優(yōu)解決，之后可以不用g_dict_layouts表直接調(diào)用path
??? while g_dict_layouts[curLayout] != -1:? # 存入路徑
??????? curLayout = g_dict_layouts[curLayout]
??????? path.append(curLayout)
??? path.reverse()
??? return 0

#修改前的遞歸解決法
def find_path(maze, pos, end):
??? mark(maze, pos)
??? if pos == end:
??????? print(pos, end=" ")? # 已到達出口，輸出這個位置。成功結(jié)束
??????? path.append(pos)
??????? return True
??? for i in range(4):? # 否則按四個方向順序檢查
??????? nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1]
??????? # 考慮下一個可能方向
??????? if passable(maze, nextp):? # 不可行的相鄰位置不管
??????????? if find_path(maze, nextp, end):? # 如果從nextp可達出口，輸出這個位置，成功結(jié)束
??????????????? print(pos, end=" ")
??????????????? path.append(pos)
??????????????? return True
??? return False

# 使尋找到的路徑可視化
def see_path(maze, path):
??? for i, p in enumerate(path):
??????? if i == 0:
??????????? maze[p[0]][p[1]] = "E"
??????? elif i == len(path) - 1:
??????????? maze[p[0]][p[1]] = "S"
??????? else:
??????????? maze[p[0]][p[1]] = 3
??? print("\n")
??? for r in maze:
??????? for c in r:
??????????? if c == 3:
??????????????? print('\033[0;31m' + "*" + " " + '\033[0m', end="")
??????????? elif c == "S" or c == "E":
??????????????? print('\033[0;34m' + c + " " + '\033[0m', end="")
??????????? elif c == 2:
??????????????? print('\033[0;32m' + "#" + " " + '\033[0m', end="")
??????????? elif c == 1:
??????????????? print('\033[0;;40m' + " " * 2 + '\033[0m', end="")
??????????? else:
??????????????? print(" " * 2, end="")
??????? print()

if __name__ == '__main__':
??? maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
????????? [1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
????????? [1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
????????? [1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
????????? [1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
????????? [1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
????????? [1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
????????? [1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
????????? [1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
????????? [1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
????????? [1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
????????? [1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
??? start=(1,1)
??? end=(10,12)
??? #find_path(maze,start,end)
??? find_path_A(maze, start, end)
??? see_path(maze,path)