A_star算法與Dijkstra算法 Grassfire 算法主要不一樣的地方就在于加入了一個(gè)度量目前的節(jié)點(diǎn)與目標(biāo)點(diǎn)之間的距離的啟發(fā)函數(shù):
常用的啟發(fā)函數(shù)有:
算法介紹就不詳細(xì)敘述了,本文主要是通過python實(shí)現(xiàn)A*算法在 0 1 地圖中(0 表示可通行區(qū)域,1表示障礙區(qū)域)的最優(yōu)路徑尋找,最終效果為:
下面在程序中,對算法中所設(shè)計(jì)到的需要進(jìn)行抽象的對象及算法的邏輯流程進(jìn)行了概述:
#需要進(jìn)行抽象化的有:節(jié)點(diǎn)(屬性有:x y坐標(biāo) 父節(jié)點(diǎn) g及h ) 地圖(屬性有高度 寬度 數(shù)據(jù)(數(shù)據(jù)中有可通行路徑與障礙兩種))
#A_star :
# open_list (存放待測試的點(diǎn),剛開始有start加入list,后面每一個(gè)current的相鄰點(diǎn)(不能位于colse_list中且不是終點(diǎn))要放到open_list中) 表示已經(jīng)走過的點(diǎn)
# close_list(存放已測試的點(diǎn),已經(jīng)當(dāng)過current的點(diǎn),就放到close_list中) 存放已經(jīng)探測過的點(diǎn),不必再進(jìn)行探測
# current 現(xiàn)在正在測試的點(diǎn),要計(jì)算current周圍的點(diǎn)的代價(jià)f 經(jīng)過current后要放到close_list中 將openlist代價(jià)f最小的node當(dāng)作下一個(gè)current
# start_point end_point
#初始化地圖 openlist closelist node
#將start點(diǎn)放入openlist中
#while(未達(dá)到終點(diǎn)):
#取出 openlist 中的點(diǎn) 將這個(gè)點(diǎn)設(shè)置為current 并放入closelist中
#for node_near in(current的臨近點(diǎn))
#if(current的臨近點(diǎn) node_near 不在closelist中且不為障礙):
#計(jì)算 node_near 的f(f=g+h)大小
# if( node_near 不在 openlist 中)
# 將 node_near 放入 openlist,并將其父節(jié)點(diǎn)設(shè)置為current 然后將f值設(shè)置為計(jì)算出的f值
# else if( node_near 在 openlist 中)
# if(計(jì)算出的f大于在openlist中的f)
# 不動(dòng)作
# else if(計(jì)算出的f小于等于在openlist中的f)
# 將 openlist 中的 node_near 的f值更新為計(jì)算出的新的更小的f值 并將父節(jié)點(diǎn)設(shè)置為current
#返回并繼續(xù)循環(huán)
import sys
#將地圖中的點(diǎn)抽象化成類
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __eq__(self, other): #函數(shù)重載
if((self.x == other.x )and (self.y == other.y)):
return 1
else:
return 0
#通過列表實(shí)現(xiàn)的地圖的建立 類c語言數(shù)組?
class map_2d:
def __init__(self,height,width):
self.height = height
self.width = width
self.data = []
self.data = [[0 for i in range(width)] for j in range(height)]
def map_show(self):
for i in range(self.height):
for j in range(self.width):
print(self.data[i][j], end=' ')
print("")
def obstacle(self,obstacle_x,obstacle_y):
self.data[obstacle_x][obstacle_y]=1
def end_draw(self,point):
self.data[point.x][point.y] = 6
#A*算法的實(shí)現(xiàn)
class A_star:
# 設(shè)置node
class Node:
def __init__(self, point, endpoint, g):
self.point = point # 自己的坐標(biāo)
self.endpoint = endpoint # 自己的坐標(biāo)
self.father = None # 父節(jié)點(diǎn)
self.g = g # g值,g值在用到的時(shí)候會(huì)重新算
self.h = (abs(endpoint.x - point.x) + abs(endpoint.y - point.y)) * 10 # 計(jì)算h值
self.f = self.g + self.h
#尋找臨近點(diǎn)
def search_near(self,ud,rl): # up down right left
nearpoint = Point(self.point.x + rl, self.point.y + ud)
nearnode = A_star.Node(nearpoint, self.endpoint, self.g + 1)
return nearnode
def __init__(self,start_point,end_point,map):#需要傳輸?shù)筋愔械模诖死ㄌ?hào)中寫出
self.path=[]
self.close_list=[] #存放已經(jīng)走過的點(diǎn)
self.open_list=[] #存放需要盡心探索的點(diǎn)
self.current = 0 #現(xiàn)在的node
self.start_point=start_point
self.end_point=end_point
self.map = map #所在地圖
def select_current(self):
min=10000000
node_temp = 0
for ele in self.open_list:
if ele.f < min:
min = ele.f
node_temp = ele
self.path.append(node_temp)
self.open_list.remove(node_temp)
self.close_list.append(node_temp)
return node_temp
def isin_openlist(self,node):
for opennode_temp in self.open_list:
if opennode_temp.point == node.point:
return opennode_temp
return 0
def isin_closelist(self,node):
for closenode_temp in self.close_list:
if closenode_temp.point == node.point:
return 1
return 0
def is_obstacle(self,node):
if self.map.data[node.point.x][node.point.y]==1 :
return 1
return 0
def near_explore(self,node):
ud = 1
rl = 0
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
ud = -1
rl = 0
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
ud = 0
rl = 1
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
ud = 0
rl = -1
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
ud = 1
rl = 1
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
ud = 1
rl = -1
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
ud = -1
rl = 1
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
ud = -1
rl = -1
node_temp = node.search_near(ud,rl) #在調(diào)用另一個(gè)類的方法時(shí)(不論是子類還是在類外定義的類),都要進(jìn)行實(shí)例化才能調(diào)用函數(shù)
if node_temp.point == end_point:
return 1
elif self.isin_closelist(node_temp):
pass
elif self.is_obstacle(node_temp):
pass
elif self.isin_openlist(node_temp) == 0:
node_temp.father = node
self.open_list.append(node_temp)
else:
if node_temp.f < (self.isin_openlist(node_temp)).f:
self.open_list.remove(self.isin_openlist(node_temp))
node_temp.father = node
self.open_list.append(node_temp)
return 0
##建圖并設(shè)立障礙
ss=map_2d(10,20)
for i in range(10):
ss.obstacle(4,i)
for i in range(19):
ss.obstacle(0,i+1)
for i in range(9):
ss.obstacle(i+1,0)
for i in range(9):
ss.obstacle(i+1,19)
for i in range(19):
ss.obstacle(9,i)
ss.obstacle(8,6)
ss.obstacle(6,8)
ss.obstacle(6,15)
ss.obstacle(9,10)
start_point = Point(1,2)
end_point = Point(9,19)
ss.end_draw(end_point)
ss.end_draw(start_point)
#初始化設(shè)置A*
a_star = A_star(start_point,end_point,ss)
start_node = a_star.Node(start_point,end_point,0)
a_star.open_list.append(start_node)
flag=0 #到達(dá)終點(diǎn)的標(biāo)志位
m=0 #步數(shù)統(tǒng)計(jì)
#進(jìn)入循環(huán)
while flag != 1 :
a_star.current = a_star.select_current()#從openlist中選取一個(gè)node
flag=a_star.near_explore(a_star.current)#對選中的node進(jìn)行周邊探索
m=m+1
print(m)
#畫出地圖路徑
for node_path in a_star.path:
ss.end_draw(node_path.point)
ss.map_show()
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
