Best-First-Search演算法- IT閱讀

Best-First-Search演算法 ... 縮寫起來是跟廣度優先搜尋一樣的BFS，實際上不同。

此BFS按照類似Dijkstra的流程執行，不同的是它能夠評估任意結點到目標點的 ... Best-First-Search演算法 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search Best-First-Search演算法 2018-12-25254 縮寫起來是跟廣度優先搜尋一樣的BFS，實際上不同。

此BFS按照類似Dijkstra的流程執行，不同的是它能夠評估任意結點到目標點的代價。

與選擇離初始結點最近的結點不同的是，它選擇離目標最近的結點。

BFS不能保證找到一條最短路徑。

然而，它比Dijkstra演算法快的多，因為它用了一個啟發式函式（heuristicfunction）快速地導向目標結點。

最佳優先搜尋是寬度優先搜尋的擴充套件，基本思想是將節點表按據目標的距離進行排序，再以節點的估計距離為標準選擇待擴充套件的節點。

演算法步驟： 1.用N表示已經排序的初始結點表(從小到大) 2.如果N為空集，則退出並給出失敗訊號 3.n取為N的首結點，並在N中刪除結點n，放入已訪問結點列表 4.如果n為目標結點，則退出並給出成功訊號 5.否則，將n的後繼結點加到N中，記為N’，對N’中的結點按距目標的估計距離排序，並返回第2步 在搜尋的過程中一般會用到評估函式f(n)，表示從初始節點S經過n到達目的節點t的最佳路徑代價f*(n)的估計： 從S到n的最佳代價g*(n)的估計g(n)，g(n)≥g*(n)，即區域性最小≥全域性最小 從n到t的最佳代價h*(n)的估計h(n)，若對所有結點n，都有h(n)≤h*(n)，則演算法A一定能找到一條到達目標結點的最佳路徑，此時演算法A稱為演算法A*。

f(n)=g(n)+h(n)作為f*(n)=g*(n)+h*(n)的估計,估計值越小的點希望越高，應該優先擴充套件，所以可以在此處維持一個優先佇列。

相關文章 Best-First-Search演算法 C++二分查詢（折半查詢、BinarySearch）演算法 SelectiveSearch演算法 UVA_10815Andy'sFirstDictionary演算法競賽入門經典 【DFS】不撞南牆不回頭—深度優先搜尋演算法[DeepFirstSearch] 九章演算法筆記4.寬度優先搜尋BreadthFirstSearch 九章演算法筆記5.深度優先搜尋DepthFirstSearch 【LeetCode-面試演算法經典-Java實現】【121-BestTimetoBuyandSellStock（最佳買賣股票的時間）】 演算法課作業系列7——BestTimetoBuyandSellStockwithTransactionFee 3069BestCowLine（貪心演算法） 禁忌搜尋演算法(TabuSearch) 第九周演算法分析與設計：SearchforaRange 字串演算法——旋轉陣列中查詢目標值(SearchinRotatedSortedArray) 演算法分析課每週練習FirstMissingPositive POJ1200CrazySearch（雜湊演算法）【模板】 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835