亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

A*算法與其python實(shí)現(xiàn)

系統(tǒng) 1615 0

A_star算法與Dijkstra算法 Grassfire 算法主要不一樣的地方就在于加入了一個(gè)度量目前的節(jié)點(diǎn)與目標(biāo)點(diǎn)之間的距離的啟發(fā)函數(shù):
常用的啟發(fā)函數(shù)有:
A*算法與其python實(shí)現(xiàn)_第1張圖片
算法介紹就不詳細(xì)敘述了,本文主要是通過python實(shí)現(xiàn)A*算法在 0 1 地圖中(0 表示可通行區(qū)域,1表示障礙區(qū)域)的最優(yōu)路徑尋找,最終效果為:

A*算法與其python實(shí)現(xiàn)_第2張圖片
其中6是其進(jìn)行行走的路徑。

下面在程序中,對算法中所設(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)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會(huì)非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产99精品一区二区三区免费 | 久久国产精品一国产精品 | 成人在线视频国产 | 奇米影视四色7777 | 国产成人精品曰本亚洲77美色 | 4hu四虎 | 日本免费人做人一区在线观看 | 96影院 | 国产亚洲午夜精品 | 91粉嫩萝控精品福利网站 | 天天操狠狠操 | 亚洲精品美女视频 | 亚洲欧美日韩精品中文乱码 | 日本中文字幕在线观看视频 | 国产精品成人观看视频国产奇米 | 亚洲综合日韩在线亚洲欧美专区 | 琪琪色在线视频 | 四虎永久在线免费观看 | 福利网站在线播放 | 国产专区日韩精品欧美色 | 成人免费视频一区二区三区 | 伊人网伊人 | 色网站综合| 91孕妇精品一区二区三区 | 九九精彩视频在线观看视频 | 99精品一区二区三区 | 免费视频爰爱太爽了 | 亚洲成人在线网站 | 最新亚洲精品国自产在线观看 | 一级黄色录像视频 | 久久亚洲国产最新网站 | 久久影院在线观看 | 激情在线播放免费视频高清 | 欧美一级毛片免费播放器 | 91久国产在线观看 | 亚洲成在人线免费视频 | 亚洲另类视频在线观看 | 久久不卡精品 | 日本在线中文 | 综合久久久| 黄色一级网 |