A_star算法與Dijkstra算法 Grassfire 算法主要不一樣的地方就在于加入了一個度量目前的節(jié)點與目標(biāo)點之間的距離的啟發(fā)函數(shù)：
常用的啟發(fā)函數(shù)有：

算法介紹就不詳細(xì)敘述了，本文主要是通過python實現(xiàn)A*算法在 0 1 地圖中（0 表示可通行區(qū)域，1表示障礙區(qū)域）的最優(yōu)路徑尋找，最終效果為：

其中6是其進(jìn)行行走的路徑。

下面在程序中，對算法中所設(shè)計到的需要進(jìn)行抽象的對象及算法的邏輯流程進(jìn)行了概述：

            
              
#需要進(jìn)行抽象化的有：節(jié)點（屬性有：x y坐標(biāo)  父節(jié)點  g及h ）  地圖（屬性有高度 寬度  數(shù)據(jù)(數(shù)據(jù)中有可通行路徑與障礙兩種)）
#A_star :
# open_list (存放待測試的點，剛開始有start加入list，后面每一個current的相鄰點（不能位于colse_list中且不是終點）要放到open_list中) 表示已經(jīng)走過的點
# close_list(存放已測試的點，已經(jīng)當(dāng)過current的點，就放到close_list中) 存放已經(jīng)探測過的點，不必再進(jìn)行探測
# current 現(xiàn)在正在測試的點，要計算current周圍的點的代價f  經(jīng)過current后要放到close_list中 將openlist代價f最小的node當(dāng)作下一個current
# start_point end_point

#初始化地圖  openlist closelist node
#將start點放入openlist中
#while（未達(dá)到終點）：
#取出 openlist 中的點 將這個點設(shè)置為current 并放入closelist中
#for node_near in（current的臨近點）
#if（current的臨近點 node_near 不在closelist中且不為障礙）：
#計算 node_near 的f（f=g+h）大小
# if( node_near 不在 openlist 中)
# 將 node_near 放入 openlist，并將其父節(jié)點設(shè)置為current 然后將f值設(shè)置為計算出的f值
# else if( node_near 在 openlist 中)
#  if（計算出的f大于在openlist中的f）
#    不動作
#  else if（計算出的f小于等于在openlist中的f）
#     將 openlist 中的 node_near 的f值更新為計算出的新的更小的f值 并將父節(jié)點設(shè)置為current
#返回并繼續(xù)循環(huán)
import sys
#將地圖中的點抽象化成類
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

#通過列表實現(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*算法的實現(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é)點
            self.g = g  # g值，g值在用到的時候會重新算
            self.h = (abs(endpoint.x - point.x) + abs(endpoint.y - point.y)) * 10  # 計算h值
            self.f = self.g + self.h

        #尋找臨近點
        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ù)筋愔械?，在此括號中寫?        self.path=[]
        self.close_list=[] #存放已經(jīng)走過的點
        self.open_list=[] #存放需要盡心探索的點
        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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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)用另一個類的方法時（不論是子類還是在類外定義的類），都要進(jìn)行實例化才能調(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á)終點的標(biāo)志位
m=0 #步數(shù)統(tǒng)計

#進(jìn)入循環(huán)
while  flag != 1 :
    a_star.current = a_star.select_current()#從openlist中選取一個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()