蜜桃av色欲a片精品一区,麻豆aⅴ精品无码一区二区,亚洲人成网站在线播放影院在线,亚洲 素人 字幕 在线 最新

微立頂科技

新聞資訊

創(chuàng)新 服務(wù) 價(jià)值

  A* and Weighted A* Search

發(fā)布日期：2022/9/3 0:22:54      瀏覽量：

思路

啟發(fā)式搜索算法

要理解A*搜尋算法，還得從啟發(fā)式搜索算法開始談起。

所謂啟發(fā)式搜索，就在于當(dāng)前搜索結(jié)點(diǎn)往下選擇下一步結(jié)點(diǎn)時(shí)，可以通過一個(gè)啟發(fā)函數(shù)(Heuristic Function)來進(jìn)行選擇，選擇代價(jià)最少的結(jié)點(diǎn)作為下一步搜索結(jié)點(diǎn)而跳轉(zhuǎn)其上（遇到有一個(gè)以上代價(jià)最少的結(jié)點(diǎn)，不妨選距離當(dāng)前搜索點(diǎn)最近一次展開的搜索點(diǎn)進(jìn)行下一步搜索）。

DFS和BFS在展開子結(jié)點(diǎn)時(shí)均屬于盲目型搜索，也就是說，它不會選擇哪個(gè)結(jié)點(diǎn)在下一次搜索中更優(yōu)而去跳轉(zhuǎn)到該結(jié)點(diǎn)進(jìn)行下一步的搜索。在運(yùn)氣不好的情形中，均需要試探完整個(gè)解集空間, 顯然，只能適用于問題規(guī)模不大的搜索問題中。

而與DFS,BFS不同的是，一個(gè)經(jīng)過仔細(xì)設(shè)計(jì)的啟發(fā)函數(shù)，往往在很快的時(shí)間內(nèi)就可得到一個(gè)搜索問題的最優(yōu)解，對于NP問題，亦可在多項(xiàng)式時(shí)間內(nèi)得到一個(gè)較優(yōu)解。是的，關(guān)鍵就是如何設(shè)計(jì)這個(gè)啟發(fā)函數(shù)。

A*搜尋算法

A*搜尋算法，俗稱A星算法，作為啟發(fā)式搜索算法中的一種，這是一種在圖形平面上，有多個(gè)節(jié)點(diǎn)的路徑，求出最低通過成本的算法。常用于游戲中的NPC的移動計(jì)算，或線上游戲的BOT的移動計(jì)算上。該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS一樣，進(jìn)行啟發(fā)式的搜索。

A*算法最為核心的部分，就在于它的一個(gè)估值函數(shù)的設(shè)計(jì)上：

f(n)=g(n)+h(n)f(n)=g(n)+h(n)

其中f(n)f(n)是每個(gè)可能試探點(diǎn)的估值，它有兩部分組成：

  • 一部分，為g(n)，它表示從起始搜索點(diǎn)到當(dāng)前點(diǎn)的代價(jià)（通常用某結(jié)點(diǎn)在搜索樹中的深度來表示）。
  • 另一部分，即h(n)，它表示啟發(fā)式搜索中最為重要的一部分，即當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估值，

h(n)設(shè)計(jì)的好壞，直接影響著具有此種啟發(fā)式函數(shù)的啟發(fā)式算法的是否能稱為A*算法。

一種具有f(n)=g(n)+h(n)f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：
1、搜索樹上存在著從起始點(diǎn)到終了點(diǎn)的最優(yōu)路徑。
2、問題域是有限的。
3、所有結(jié)點(diǎn)的子結(jié)點(diǎn)的搜索代價(jià)值>0>0。
4、h(n)=<h?(n)h(n)=<h?(n) （h?(n)h?(n)為實(shí)際問題的代價(jià)值）。

當(dāng)此四個(gè)條件都滿足時(shí)，一個(gè)具有f(n)=g(n)+h(n)f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法，并一定能找到最優(yōu)解。

對于一個(gè)搜索問題，顯然，條件1,2,3都是很容易滿足的，而條件4： h(n)<=h?(n)h(n)<=h?(n)是需要精心設(shè)計(jì)的，由于h?(n)h?(n)顯然是無法知道的，所以，一個(gè)滿足條件4的啟發(fā)策略h(n)h(n)就來的難能可貴了。

不過，對于圖的最優(yōu)路徑搜索和八數(shù)碼問題，有些相關(guān)策略h(n)不僅很好理解，而且已經(jīng)在理論上證明是滿足條件4的，從而為這個(gè)算法的推廣起到了決定性的作用。

且h(n)h(n)距離h?(n)h?(n)的呈度不能過大，否則h(n)h(n)就沒有過強(qiáng)的區(qū)分能力，算法效率并不會很高。對一個(gè)好的h(n)h(n)的評價(jià)是：h(n)h(n)在h?(n)h?(n)的下界之下，并且盡量接近h?(n)h?(n)。


示例程序 

"""

A* grid planning

author: Atsushi Sakai(@Atsushi_twi)
        Nikos Kanargias ([email protected])

See Wikipedia article (https://en.wikipedia.org/wiki/A*_search_algorithm)

""" import math import matplotlib.pyplot as plt

show_animation = True class AStarPlanner: def __init__(self, ox, oy, reso, rr): """
        Initialize grid map for a star planning

        ox: x position list of Obstacles [m]
        oy: y position list of Obstacles [m]
        reso: grid resolution [m]
        rr: robot radius[m]
        """ self.reso = reso
        self.rr = rr
        self.calc_obstacle_map(ox, oy)
        self.motion = self.get_motion_model() class Node: def __init__(self, x, y, cost, pind):
            self.x = x # index of grid self.y = y # index of grid self.cost = cost
            self.pind = pind def __str__(self): return str(self.x) + "," + str(self.y) + "," + str(self.cost) + "," + str(self.pind) def planning(self, sx, sy, gx, gy): """
        A star path search

        input:
            sx: start x position [m]
            sy: start y position [m]
            gx: goal x position [m]
            gy: goal y position [m]

        output:
            rx: x position list of the final path
            ry: y position list of the final path
        """ nstart = self.Node(self.calc_xyindex(sx, self.minx),
                           self.calc_xyindex(sy, self.miny), 0.0, -1)
        ngoal = self.Node(self.calc_xyindex(gx, self.minx),
                          self.calc_xyindex(gy, self.miny), 0.0, -1)

        open_set, closed_set = dict(), dict()
        open_set[self.calc_grid_index(nstart)] = nstart while 1: if len(open_set) == 0: print("Open set is empty..") break c_id = min(
                open_set, key=lambda o: open_set[o].cost + self.calc_heuristic(ngoal, open_set[o]))
            current = open_set[c_id] # show graph if show_animation: # pragma: no cover plt.plot(self.calc_grid_position(current.x, self.minx),
                         self.calc_grid_position(current.y, self.miny), "xc") # for stopping simulation with the esc key. plt.gcf().canvas.mpl_connect(’key_release_event’, lambda event: [exit(0) if event.key == ’escape’ else None]) if len(closed_set.keys()) % 10 == 0:
                    plt.pause(0.001) if current.x == ngoal.x and current.y == ngoal.y: print("Find goal")
                ngoal.pind = current.pind
                ngoal.cost = current.cost break # Remove the item from the open set del open_set[c_id] # Add it to the closed set closed_set[c_id] = current # expand_grid search grid based on motion model for i, _ in enumerate(self.motion):
                node = self.Node(current.x + self.motion[i][0],
                                 current.y + self.motion[i][1],
                                 current.cost + self.motion[i][2], c_id)
                n_id = self.calc_grid_index(node) # If the node is not safe, do nothing if not self.verify_node(node): continue if n_id in closed_set: continue if n_id not in open_set:
                    open_set[n_id] = node # discovered a new node else: if open_set[n_id].cost > node.cost: # This path is the best until now. record it open_set[n_id] = node

        rx, ry = self.calc_final_path(ngoal, closed_set) return rx, ry def calc_final_path(self, ngoal, closedset): # generate final course rx, ry = [self.calc_grid_position(ngoal.x, self.minx)], [
            self.calc_grid_position(ngoal.y, self.miny)]
        pind = ngoal.pind while pind != -1:
            n = closedset[pind]
            rx.append(self.calc_grid_position(n.x, self.minx))
            ry.append(self.calc_grid_position(n.y, self.miny))
            pind = n.pind return rx, ry  @staticmethod def calc_heuristic(n1, n2):
        w = 1.0 # weight of heuristic d = w * math.hypot(n1.x - n2.x, n1.y - n2.y) return d def calc_grid_position(self, index, minp): """
        calc grid position

        :param index:
        :param minp:
        :return:
        """ pos = index * self.reso + minp return pos def calc_xyindex(self, position, min_pos): return round((position - min_pos) / self.reso) def calc_grid_index(self, node): return (node.y - self.miny) * self.xwidth + (node.x - self.minx) def verify_node(self, node):
        px = self.calc_grid_position(node.x, self.minx)
        py = self.calc_grid_position(node.y, self.miny) if px < self.minx: return False elif py < self.miny: return False elif px >= self.maxx: return False elif py >= self.maxy: return False # collision check if self.obmap[node.x][node.y]: return False return True def calc_obstacle_map(self, ox, oy):

        self.minx = round(min(ox))
        self.miny = round(min(oy))
        self.maxx = round(max(ox))
        self.maxy = round(max(oy)) print("minx:", self.minx) print("miny:", self.miny) print("maxx:", self.maxx) print("maxy:", self.maxy)

        self.xwidth = round((self.maxx - self.minx) / self.reso)
        self.ywidth = round((self.maxy - self.miny) / self.reso) print("xwidth:", self.xwidth) print("ywidth:", self.ywidth) # obstacle map generation self.obmap = [[False for i in range(self.ywidth)] for i in range(self.xwidth)] for ix in range(self.xwidth):
            x = self.calc_grid_position(ix, self.minx) for iy in range(self.ywidth):
                y = self.calc_grid_position(iy, self.miny) for iox, ioy in zip(ox, oy):
                    d = math.hypot(iox - x, ioy - y) if d <= self.rr:
                        self.obmap[ix][iy] = True break  @staticmethod def get_motion_model(): # dx, dy, cost motion = [[1, 0, 1],
                  [0, 1, 1],
                  [-1, 0, 1],
                  [0, -1, 1],
                  [-1, -1, math.sqrt(2)],
                  [-1, 1, math.sqrt(2)],
                  [1, -1, math.sqrt(2)],
                  [1, 1, math.sqrt(2)]] return motion def main(): print(__file__ + " start!!") # start and goal position sx = 10.0 # [m] sy = 10.0 # [m] gx = 50.0 # [m] gy = 50.0 # [m] grid_size = 2.0 # [m] robot_radius = 1.0 # [m] # set obstable positions ox, oy = [], [] for i in range(-10, 60):
        ox.append(i)
        oy.append(-10.0) for i in range(-10, 60):
        ox.append(60.0)
        oy.append(i) for i in range(-10, 61):
        ox.append(i)
        oy.append(60.0) for i in range(-10, 61):
        ox.append(-10.0)
        oy.append(i) for i in range(-10, 40):
        ox.append(20.0)
        oy.append(i) for i in range(0, 40):
        ox.append(40.0)
        oy.append(60.0 - i) if show_animation: # pragma: no cover plt.plot(ox, oy, ".k")
        plt.plot(sx, sy, "og")
        plt.plot(gx, gy, "xb")
        plt.grid(True)
        plt.axis("equal")

    a_star = AStarPlanner(ox, oy, grid_size, robot_radius)
    rx, ry = a_star.planning(sx, sy, gx, gy) if show_animation: # pragma: no cover plt.plot(rx, ry, "-r")
        plt.pause(0.001)
        plt.show() if __name__ == ’__main__’:
    main()

核心代碼 

def planning(self, sx, sy, gx, gy): """
        A star path search

        input:
            sx: start x position [m]
            sy: start y position [m]
            gx: goal x position [m]
            gy: goal y position [m]

        output:
            rx: x position list of the final path
            ry: y position list of the final path
        """ nstart = self.Node(self.calc_xyindex(sx, self.minx),
                           self.calc_xyindex(sy, self.miny), 0.0, -1)
        ngoal = self.Node(self.calc_xyindex(gx, self.minx),
                          self.calc_xyindex(gy, self.miny), 0.0, -1)

        open_set, closed_set = dict(), dict()
        open_set[self.calc_grid_index(nstart)] = nstart while 1: if len(open_set) == 0: print("Open set is empty..") break c_id = min(
                open_set, key=lambda o: open_set[o].cost + self.calc_heuristic(ngoal, open_set[o]))
            current = open_set[c_id] # show graph if show_animation: # pragma: no cover plt.plot(self.calc_grid_position(current.x, self.minx),
                         self.calc_grid_position(current.y, self.miny), "xc") # for stopping simulation with the esc key. plt.gcf().canvas.mpl_connect(’key_release_event’, lambda event: [exit(0) if event.key == ’escape’ else None]) if len(closed_set.keys()) % 10 == 0:
                    plt.pause(0.001) if current.x == ngoal.x and current.y == ngoal.y: print("Find goal")
                ngoal.pind = current.pind
                ngoal.cost = current.cost break # Remove the item from the open set del open_set[c_id] # Add it to the closed set closed_set[c_id] = current # expand_grid search grid based on motion model for i, _ in enumerate(self.motion):
                node = self.Node(current.x + self.motion[i][0],
                                 current.y + self.motion[i][1],
                                 current.cost + self.motion[i][2], c_id)
                n_id = self.calc_grid_index(node) # If the node is not safe, do nothing if not self.verify_node(node): continue if n_id in closed_set: continue if n_id not in open_set:
                    open_set[n_id] = node # discovered a new node else: if open_set[n_id].cost > node.cost: # This path is the best until now. record it open_set[n_id] = node

        rx, ry = self.calc_final_path(ngoal, closed_set) return rx, ry

其中，

c_id = min(open_set, key=lambda o: open_set[o].cost + self.calc_heuristic(ngoal, open_set[o])) current = open_set[c_id]
把min函數(shù)的比較函數(shù)換成open_set[o].cost + self.calc_heuristic(ngoal, open_set[o])，也即f(n)=g(n)+h(n)f(n)=g(n)+h(n)，通過這兩行，找到在open_set中cost與heuristic值最小的節(jié)點(diǎn)。比如，在常見的機(jī)器人搜索路徑問題中，cost指的是從起點(diǎn)到該節(jié)點(diǎn)走過的距離，heuristic是指從該節(jié)點(diǎn)到達(dá)終點(diǎn)的距離。那么很好理解，每一步都能選取到一個(gè)最佳路徑點(diǎn)。

參考



  業(yè)務(wù)實(shí)施流程

需求調(diào)研 →

團(tuán)隊(duì)組建和動員 →

數(shù)據(jù)初始化 →

調(diào)試完善 →

解決方案和選型 →

硬件網(wǎng)絡(luò)部署 →

系統(tǒng)部署試運(yùn)行 →

系統(tǒng)正式上線 →

合作協(xié)議

系統(tǒng)開發(fā)/整合

制作文檔和員工培訓(xùn)

售后服務(wù)

馬上咨詢： 如果您有業(yè)務(wù)方面的問題或者需求，歡迎您咨詢！我們帶來的不僅僅是技術(shù)，還有行業(yè)經(jīng)驗(yàn)積累。
QQ: 39764417/308460098     Phone: 13 9800 1 9844 / 135 6887 9550     聯(lián)系人：石先生/雷先生