国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

尋路之 A* 搜尋算法

banana_pi / 1270人閱讀

摘要：但再認真想想，其實這道題目就類似我們日常用的導航，尋找起點和終點可行的最短路線。越小時，那么起點到目標點的可行路徑越小。首先將起點放進中，然后搜尋起點附近可行方格放到中作記錄。

最近做到一道題，題目如下：

有 A、B 兩點，中間有一堆障礙物，求出A點到B的可行的路徑，寫出一個 DEMO 并可用任何語言實現（要求可以任意設置 A、B 點和障礙物的位置，需要做UI）。

首先，理解一下題意，需要求出 A、B 兩點的可行路線，要注意的是可以任意設置 A、B 兩點位置以及障礙物的位置且需要做 UI。題目需一句話帶過，但需要做不少的工作。嗯，很明顯，這是一道考算法邏輯還有 UI 的題目。

現在我們將主要工作放在如何去求出 A、B 兩點的可行的路徑呢？

估計看到題目，很多人都會無從下手。但再認真想想，其實這道題目就類似我們日常用的導航，尋找起點和終點可行的最短路線。那么，我們可以使用搜尋算法解決這一道題目。搜尋算法有很多種，如：最佳優先搜索算法 （Best-First Search）、戴克斯特拉算法（Dijkstra）、A 搜尋算法和迭代加深 A 算法（IDA* ）等等。

先來了解一下 A* 搜尋算法：

A* 算法綜合了 最佳優先搜索算法 （Best-First Search） 和 戴克斯特拉算法（Dijkstra）的優點：在進行啟發式搜索提高算法效率的同時，可以保證找到一條最優路徑（基于評估函數） 維基百科

A* 搜尋算法的估算函數：

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

g(n) 表示起點到任意點 n 的距離，h(n) 表示任意點 n 到目標點的距離，f(n) 則表示任意點 n 到起點以及目標點的和。f(n) 越小時，那么起點到目標點的可行路徑越小。

接下來我們使用圖文來說明一下我們該如何計算：

我們可以將所有格子看作一個二維數組，里面分為可行以及不可行（即障礙物）。我們將起始點標記為 A 以及目標點（終點）標記為 B，此處我們忽略可斜走的情況（因為需要做各種限制，略麻煩），本文 Open List 存放所有 A 附近可行的方格，Close List 存放已行的不需要再關注的方格。

（圖一）

可見圖一，起點 A 上下左右有四個方格，右邊格子為障礙物，再次我們則忽略它，那么起點 A 相鄰可行的格子有上左下這三個。我們設置一個 Open List 用于存放可行的方格，以及一個 Close List 用于記錄已行方格。首先將起點 A 放進 Open List 中，然后搜尋起點 A 附近可行方格放到 Open List 中作記錄。

從上面 A 搜尋算法的簡單了解，我們可知 A 搜尋算法的估算函數是：f(n) = g(n) + h(n)。

A 相鄰的長方形 f(n) 越小，則 A 到達 B 的可行路徑最短，因此我們需要選擇最小 f(n) 的長方形行走。接下來看看我們如何去計算 f(n) 的值。

為了方便計算，我們將方格的長寬設置為 1 ，如果可斜走那么每一個的斜線為 。當然為了方便計算可使用長寬為 10，斜線為 14 的比例來計算。

（圖二）

如圖二，起點 A 有三塊可行的方格，我們標記為粉紅色，那么首先我們計算這三個方格的 g 值。起點 A 的上左下的方格分別離 A 點距離 g(n) 為 1 ，所以標記粉紅色的上左下的方格 g(n) 值為 1。

那么接下來計算 h(n) 值，計算 h(n) 值時忽略障礙物，即所有方格可行的情況下計算（如果可行斜線情況下，那么在計算 h(n) 值的時候不計算斜走的情況，只計算任意點直行到終點距離）。那么可計算出起點 A 下方的方格 h(n) 等于 7，左方 h(n) 等于 9，上方 h(n) 等于 9。那么得出上左下三個方格的 f(n) 值：

起點 A 上方：f(n) = g(n) + h(n) = 1 + 9 = 10

起點 A 左方：f(n) = g(n) + h(n) = 1 + 9 = 10

起點 A 下方：f(n) = g(n) + h(n) = 1 + 7 = 8

由上面的計算可得出起點 A 下方的 f(n) 值為最小，那么我們第一步走到起點 A 下方的方格。那么將起點 A 下方的方格存到 Close List，且同時從 Open List 中移除。

（圖三）

如圖三，我們走了第一步后 A 點去到了起點的下方一個，那個繼續去計算，由于上面起點已經存在于 Close List 以及已存在于 Open List 的格子我們不需要再關注，那么圖上可看到 A 點接著可行點只有左右兩點，那么計算 A 點到左邊格子 g(n) 為 2，h(n) 為 8，右邊格子 g(n) 為 2，h(n) 為 6。那么 A 點左邊格子 f(n) 等于 10，右邊格子 f(n) 等于 8，因此我們第二步走 A 點右邊格子，將格子從 Open List 移除，存進 Close List（如圖四）。

（圖四）

以此類推，我們最終可得出的路徑（如圖五）。

（圖五）

如圖五，綠色路徑為可行的最短路徑，紅色標志的則是已存在于 Open List 的方格。

基本原理就是如此，代碼我就不一一列出來，我會放到 Github 或者看看 Jsfiddle 上面，有興趣的可以看一下，對應方法也有對應的注釋。可以看一下最終實現的 效果

動畫演示各種算法地址：http://www.webhek.com/post/pathfinding.html

新手一枚，如果有什么寫錯的或者不好的地方，請各位大大指點探討一下，我會不斷優化提升。

哦，最近本人在找工作，期待工作地區廣州、深圳、佛山，如有好工作或者內推等可以私聊一下我。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/83662.html

相關文章

  • A星算法JavaScript版本

    摘要：星算法介紹實現星尋路算法在游戲中常有需要主角敵人去移動到某個物品或者追尋敵人的時候，這個時候，可以使用尋路算法為了實現游戲，需要尋路算法，于是便自己用實現了一下原理思路簡化搜索區域為了減少資源消耗，首先需要我們將地圖分割為區塊，如下圖建立起 A星算法 介紹 javascript實現A星尋路算法 在游戲中常有需要主角/敵人去移動到某個物品或者追尋敵人的時候，這個時候，可以使用尋路算法 ...

    AWang 評論0 收藏0

  • 用 js 寫個自動尋路的貪吃蛇

    摘要：前言偶爾看到兩年前寫的貪吃蛇，當時沒把自動尋路的算法寫好，蛇容易掛，周末找了個時間把當年的坑填上，寫了個不會掛的貪吃蛇。 前言 偶爾看到兩年前寫的貪吃蛇，當時沒把自動尋路的算法寫好，蛇容易掛，周末找了個時間把當年的坑填上，寫了個不會掛的貪吃蛇。 兩年前的版本_點擊查看 這次更新的版本_點擊查看 代碼比較簡單,使用 canvas 完成游戲的畫圖，拋開 A* 算法的實現，整個 html 代...

    gaara 評論0 收藏0

  • 掃地機器人的模擬程序 (3)

    摘要：話說我的地圖就是柵格形式用點坐標來表示格子模板模型法很容易理解，就是有幾種走法，按情況調用。 尋路模塊 (1) 終于要挑戰尋路模塊，雖然我是在重復造輪子，但看一下別人的輪子怎么造也是很重要的，所以在這之前首先搜索下，看看有什么現成的思路和代碼，收獲如下: 兩種尋路邏輯 有兩種尋路邏輯, 隨機碰撞和路徑規劃，考慮到： a. 隨機碰撞似乎需要不少經驗/實驗數據才能達到不錯的效果，我缺經驗/...

    ccj659 評論0 收藏0

  • 掃地機器人的模擬程序 (4)

    摘要：尋路模塊通過一番尋找，發現這系列文章，其不僅包含算法，連尋路算法中的一些基礎知識也一并介紹了，不愧是斯坦福出品，也很感謝譯者要實現點到點最短路徑，還需要做一些微小的工作，下面逐個說明計算曼哈頓距離的函數目的是尋路，肯定需要一個方法來估算兩點 尋路模塊 (2) 通過一番尋找，發現這系列文章，其不僅包含A*算法，連尋路算法中的一些基礎知識也一并介紹了，不愧是斯坦福出品，也很感謝譯者要實現點...

    thekingisalwaysluc 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<