A*算法詳解

A*算法詳解

    • 一、A*算法基礎概念
      • 1.1 算法定位
      • 1.2 核心評估函數
      • 1.3 關鍵數據結構
    • 二、A*算法的核心步驟
    • 三、啟發函數設計
      • 3.1 網格地圖中的啟發函數
      • 3.2 啟發函數的選擇原則
    • 三、Java代碼實現
    • 四、啟發函數的設計與優化
      • 4.1 啟發函數的可采納性
      • 4.2 啟發函數的效率影響
      • 4.3 常見啟發函數對比
    • 五、A*算法的應用場景與拓展
      • 5.1 典型應用
      • 5.2 算法拓展
    • 六、A*算法的優缺點
      • 優點
      • 缺點

從游戲中的角色尋路到機器人導航,從地圖軟件的路線規劃到無人機路徑優化,A算法都發揮著核心作用,本文我將深入解析A算法的核心原理、實現步驟、啟發函數設計及實際應用,并結合Java代碼示例,帶你全面掌握這一路徑搜索算法。

一、A*算法基礎概念

1.1 算法定位

A*算法是一種啟發式搜索算法,它結合了Dijkstra算法的完備性(保證找到解)和貪婪最佳優先搜索的高效性(基于啟發信息快速導向目標),通過引入評估函數引導搜索方向,能在復雜網格或圖中快速找到從起點到目標的最優路徑。

1.2 核心評估函數

A*算法的核心是評估函數f(n),用于判斷節點n的"優先級":

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

  • g(n):從起點到當前節點n實際代價(已走過的路徑長度)。
  • h(n):從當前節點n到目標節點的估計代價(啟發函數),這是A*算法的"智能"所在。

1.3 關鍵數據結構

  • 開放列表(Open List):存儲待探索的節點,按f(n)值升序排列(通常用優先隊列實現)。
  • 關閉列表(Closed List):存儲已探索的節點,避免重復訪問(通常用哈希表或集合實現)。
  • 節點(Node):包含坐標、g(n)h(n)f(n)及父節點指針(用于回溯路徑)。

二、A*算法的核心步驟

A*算法的執行流程可概括為以下步驟:

  1. 初始化

    • 將起點加入開放列表,計算其g(n)=0h(n)(根據啟發函數),f(n)=g(n)+h(n)
    • 關閉列表初始為空。
  2. 循環搜索

    • 從開放列表中取出f(n)最小的節點current,移至關閉列表。
    • current是目標節點,回溯路徑并結束。
    • 遍歷current的所有相鄰節點neighbor
      • neighbor在關閉列表中,跳過。
      • 計算neighborg(n)current.g + 相鄰節點距離)。
      • neighbor不在開放列表,或新g(n)更小:
        • 更新neighborg(n)h(n)f(n),設置父節點為current
        • 若不在開放列表,加入開放列表。
  3. 路徑回溯

    • 從目標節點開始,通過父節點指針反向追溯至起點,得到最優路徑。

三、啟發函數設計

啟發函數h(n)的設計直接影響A*算法的效率和最優性,需滿足可采納性h(n) ≤ 實際代價),以保證找到最優解。常見的啟發函數如下:

3.1 網格地圖中的啟發函數

  • 曼哈頓距離(Manhattan Distance):適用于只能上下左右移動的網格(如方格地圖):

h(n) = |x? - x?| + |y? - y?|

(x?,y?)為當前節點坐標,(x?,y?)為目標節點坐標)

  • 歐幾里得距離(Euclidean Distance):適用于允許斜向移動的網格:

h(n) = √[(x? - x?)2 + (y? - y?)2]

  • 切比雪夫距離(Chebyshev Distance):適用于允許8方向移動(包括對角線)的網格:

h(n) = max(|x? - x?|, |y? - y?|)

3.2 啟發函數的選擇原則

  • 最優性優先:選擇可采納的啟發函數(如曼哈頓距離),確保找到最短路徑。
  • 效率優先:在不要求嚴格最優時,可使用略高估的啟發函數加速搜索(如加權曼哈頓距離)。

三、Java代碼實現

以下是基于網格地圖的A*算法實現,使用曼哈頓距離作為啟發函數,支持4方向移動:

import java.util.*;// 節點類
class Node implements Comparable<Node> {int x, y; // 坐標int g; // 起點到當前節點的實際代價int h; // 到目標的估計代價int f; // f = g + hNode parent; // 父節點public Node(int x, int y) {this.x = x;this.y = y;}// 按f值升序排序,f相同則按h值@Overridepublic int compareTo(Node other) {if (this.f != other.f) {return Integer.compare(this.f, other.f);}return Integer.compare(this.h, other.h);}// 重寫equals和hashCode,用于關閉列表去重@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Node node = (Node) o;return x == node.x && y == node.y;}@Overridepublic int hashCode() {return Objects.hash(x, y);}
}public class AStarAlgorithm {// 網格地圖:0為可通行,1為障礙物private int[][] grid;// 方向數組:上下左右private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public AStarAlgorithm(int[][] grid) {this.grid = grid;}// 啟發函數:曼哈頓距離private int calculateH(Node node, Node target) {return Math.abs(node.x - target.x) + Math.abs(node.y - target.y);}// 搜索路徑public List<Node> findPath(Node start, Node target) {PriorityQueue<Node> openList = new PriorityQueue<>();Set<Node> closedList = new HashSet<>();// 初始化起點start.g = 0;start.h = calculateH(start, target);start.f = start.g + start.h;openList.add(start);while (!openList.isEmpty()) {Node current = openList.poll();// 找到目標,回溯路徑if (current.equals(target)) {return reconstructPath(current);}closedList.add(current);// 遍歷相鄰節點for (int[] dir : directions) {int nx = current.x + dir[0];int ny = current.y + dir[1];// 檢查是否越界或為障礙物if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length || grid[nx][ny] == 1) {continue;}Node neighbor = new Node(nx, ny);if (closedList.contains(neighbor)) {continue;}// 計算相鄰節點的g值(假設相鄰節點距離為1)int newG = current.g + 1;// 若鄰居不在開放列表,或新g值更小if (!openList.contains(neighbor) || newG < neighbor.g) {neighbor.g = newG;neighbor.h = calculateH(neighbor, target);neighbor.f = neighbor.g + neighbor.h;neighbor.parent = current;if (!openList.contains(neighbor)) {openList.add(neighbor);}}}}// 未找到路徑return null;}// 回溯路徑(從目標到起點)private List<Node> reconstructPath(Node target) {List<Node> path = new ArrayList<>();Node current = target;while (current != null) {path.add(current);current = current.parent;}Collections.reverse(path); // 反轉路徑,從起點到目標return path;}// 測試public static void main(String[] args) {// 5x5網格,1為障礙物int[][] grid = {{0, 0, 0, 0, 0},{0, 1, 1, 1, 0},{0, 0, 0, 1, 0},{0, 1, 0, 1, 0},{0, 0, 0, 0, 0}};AStarAlgorithm aStar = new AStarAlgorithm(grid);Node start = new Node(0, 0);Node target = new Node(4, 4);List<Node> path = aStar.findPath(start, target);if (path != null) {System.out.println("找到路徑:");for (Node node : path) {System.out.println("(" + node.x + "," + node.y + ")");}} else {System.out.println("未找到路徑");}}
}

四、啟發函數的設計與優化

4.1 啟發函數的可采納性

啟發函數h(n)必須滿足不高估實際代價h(n) ≤ 實際從n到目標的代價),才能保證A*算法找到最優路徑。例如:

  • 網格中,曼哈頓距離對于4方向移動是可采納的,歐幾里得距離對于任意方向移動是可采納的。
  • h(n)=0,A*算法退化為Dijkstra算法,雖能找到最優路徑但效率低。

4.2 啟發函數的效率影響

  • h(n)越接近實際代價,A*算法搜索的節點越少,效率越高。
  • h(n)完全等于實際代價,A*算法會直接沿最優路徑搜索,效率最高。
  • h(n)高估實際代價(不可采納),算法可能找不到最優路徑,但速度更快(適用于對效率要求高、可接受近似解的場景)。

4.3 常見啟發函數對比

啟發函數適用場景可采納性效率
曼哈頓距離4方向網格移動
歐幾里得距離任意方向移動(如無人機)
切比雪夫距離8方向網格移動
加權曼哈頓距離允許近似解的場景極高

五、A*算法的應用場景與拓展

5.1 典型應用

  • 游戲開發:角色尋路(如RPG游戲中NPC的移動路徑)。
  • 機器人導航:自主移動機器人在室內或室外環境中的路徑規劃。
  • 地圖軟件:駕車/步行路線規劃(結合道路權重、交通狀況)。
  • 路徑規劃:無人機、無人車的避障路徑計算。

5.2 算法拓展

  • 雙向A*算法:同時從起點和目標開始搜索,相遇時終止,減少搜索范圍。
  • 分層A*算法:在大規模地圖中,先規劃高層粗略路徑,再細化低層路徑。
  • 動態A算法(D:適用于環境動態變化的場景(如突然出現障礙物),能快速重新規劃路徑。

六、A*算法的優缺點

優點

  • 高效性:通過啟發函數引導搜索,比Dijkstra算法搜索更少節點。
  • 最優性:在啟發函數可采納時,能找到最優路徑。
  • 靈活性:可通過調整啟發函數適應不同場景(精度與效率的權衡)。

缺點

  • 依賴啟發函數:啟發函數設計不當會導致效率低下或找不到最優路徑。
  • 內存消耗:開放列表和關閉列表需存儲大量節點,不適用于超大地圖。
  • 靜態環境:默認適用于靜態環境,動態環境需結合D*等變體算法。

總結
A*算法作為一種高效的路徑搜索算法,通過評估函數f(n)=g(n)+h(n)平衡了搜索的完備性和效率,在游戲開發、機器人導航等領域有著廣泛應用,掌握A※算法的核心在于理解啟發函數的設計原則——可采納性與效率的權衡,以及節點的擴展和路徑回溯機制。

That’s all, thanks for reading~~
覺得有用就點個贊、收進收藏夾吧!關注我,獲取更多干貨~

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/89116.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/89116.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/89116.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

.net winfrom 獲取上傳的Excel文件 單元格的背景色

需求&#xff1a;根據Excel某行標注了黃色高亮顏色&#xff0c;說明該行數據已被用戶選中(Excel文件中并沒有“已選中”這一列&#xff0c;純粹用顏色表示)&#xff0c;導入數據到數據庫時標注此行已選中直接上代碼&#xff1a;//選擇Excel文件private void btnBrowse_Click(ob…

OpenAI GPT-4o技術詳解:全能多模態模型的架構革新與生態影響

本文由「大千AI助手」原創發布&#xff0c;專注用真話講AI&#xff0c;回歸技術本質。拒絕神話或妖魔化。搜索「大千AI助手」關注我&#xff0c;一起撕掉過度包裝&#xff0c;學習真實的AI技術&#xff01; ?? 一、核心定義與發布背景 官方定位 GPT-4o&#xff08;“o”代表“…

? 構建真正的高性能即時通訊服務:基于 Netty 集群的架構設計與實現

引子 在前面的文章中&#xff0c;我們基于 Netty 構建了一套單體架構的即時通訊服務。雖然單體架構在開發初期簡單高效&#xff0c;但隨著用戶量的增長和業務規模的擴大&#xff0c;其局限性逐漸顯現。當面對高并發場景時&#xff0c;單體 Netty 服務很容易觸及性能天花板&…

原來時間序列挖掘這么簡單

先搞懂&#xff1a;啥是時間序列&#xff1f;簡單說&#xff0c;時間序列就是按時間順序記下來的數據。比如&#xff1a;你每天早上 8 點測的體重&#xff0c;連起來就是 “體重時間序列”&#xff1b;超市每天的銷售額&#xff0c;連起來就是 “銷售時間序列”&#xff1b;城市…

基于Python的豆瓣圖書數據分析與可視化系統【自動采集、海量數據集、多維度分析、機器學習】

文章目錄有需要本項目的代碼或文檔以及全部資源&#xff0c;或者部署調試可以私信博主項目介紹每文一語有需要本項目的代碼或文檔以及全部資源&#xff0c;或者部署調試可以私信博主 項目介紹 豆瓣圖書數據智能分析系統是一個集數據采集、清洗、分析與可視化于一體的綜合性項…

2.3 數組與字符串

學習目標&#xff1a; 理解數組和字符串的概念&#xff08;存儲多個數據的“盒子”&#xff09;。掌握數組的聲明、初始化和遍歷方法。能用字符串處理簡單文本問題&#xff08;如字符計數、回文判斷&#xff09;。1 一維數組 基本概念 比喻&#xff1a; 數組就像“儲物柜”&…

C# 網口demo

bool _testStatus false; private void btnOpsStart_Click(object sender, EventArgs e) {int delay Convert.ToInt32(txtdelay.Text.Trim());txtView.Clear();txtView.AppendText("******************************************開始烤機*******************************…

MATLAB 安裝 ACADO 的完整步驟

? MATLAB 安裝 ACADO 的完整步驟 &#x1f4e6; 一、準備工作 1. 下載 ACADO Toolkit 官方地址&#xff1a;https://github.com/acado/acado 2. 解壓 ACADO 到你指定的路徑&#xff0c;例如&#xff1a; D:\user\acado-master建議路徑中 不要包含中文或空格。 &#x1f9f…

[逆向工程]160個CrackMe入門實戰之Afkayas.1.Exe解析(二)

[逆向工程]160個CrackMe入門實戰之Afkayas.1.Exe解析&#xff08;二&#xff09; 一、前言 在逆向工程的學習路徑上&#xff0c;CrackMe程序是初學者最好的練手材料。今天我們要分析的是160個CrackMe系列的第二題——Afkayas.1.Exe。這個程序由Afkayas編寫&#xff0c;難度為★…

本地電腦安裝Dify|內網穿透到公網

1.安裝Docker Docker: Accelerated Container Application Development 2.添加 PATH 3.安裝Dify https://github.com/langgenius/dify.git 把.env.example文件名改為.env 4.更換鏡像源 {"builder": {"gc": {"defaultKeepStorage": "20G…

數據結構自學Day6 棧與隊列

1. 棧其實棧與隊列仍然屬于線性表&#xff08;有n個元素構成的集合&#xff0c;邏輯結構呈現線形&#xff09;線形表&#xff1a;順序表&#xff0c;鏈表&#xff0c;棧&#xff0c;隊列&#xff0c;串&#xff08;字符串&#xff09;棧&#xff08;Stack&#xff09;是一種線性…

Java 異常處理詳解:從基礎語法到最佳實踐,打造健壯的 Java 應用

作為一名 Java 開發工程師&#xff0c;你一定遇到過運行時錯誤、空指針異常、文件找不到等問題。Java 提供了強大的異常處理機制&#xff0c;幫助我們優雅地捕獲和處理這些錯誤。本文將帶你全面掌握&#xff1a;Java 異常體系結構try-catch-finally 的使用throw 與 throws 的區…

Fiddler弱網測試實戰指南

Fiddler是一個常用的網絡抓包工具&#xff0c;它也可以用來模擬弱網環境進行測試。 在測試時需要用到弱網測試&#xff0c;也就是在信號差、網絡慢的情況下進行測試。比如&#xff0c;用戶在地鐵、電梯、地下車庫等場景經常會遇到會話中斷、超時等情況&#xff0c;這種就屬于弱…

解決Vue頁面黑底紅字遮罩層報錯:Unknown promise rejection reason (webpack-internal)

vue前端頁面彈出黑底紅色報錯遮罩層報錯&#xff1a;具體報錯信息&#xff1a;Uncaught runtime errors: ERROR Unknown promise rejection reasonat handleError (webpack-internal:///./node_modules/webpack-dev-server/client/overlay.js:299:58)at eval (webpack-internal…

構建 Go 可執行文件鏡像 | 探索輕量級 Docker 基礎鏡像(我應該選擇哪個 Docker 鏡像?)

文章目錄構建 Go 可執行文件鏡像典型用途探索輕量級 Docker 基礎鏡像構建 Go 可執行文件鏡像 golang:1.23.0-bullseye 是官方 Go 鏡像的一個 “build-stage” 版,用來構建 Go 可執行文件&#xff0c;而不是把它當成最終運行鏡像。 dockerhub官方&#xff1a;https://hub.dock…

鏈表算法之【回文鏈表】

目錄 LeetCode-234題 LeetCode-234題 給定一個單鏈表的頭節點head&#xff0c;判斷該鏈表是否為回文鏈表&#xff0c;是返回true&#xff0c;否則返回false class Solution {/*** 這里的解題思路為&#xff1a;* (1)、找中間節點* (2)、反轉鏈表* (3)、遍歷比較節點值是否相…

Playwright Python 教程:網頁自動化

1. 常用工具簡介及對比主流網頁自動化工具對比工具支持語言瀏覽器支持特點適用場景PlaywrightPython, JS, .NETChromium, Firefox, WebKit跨瀏覽器、速度快、API簡潔自動化測試、爬蟲、網頁操作Selenium多語言所有主流瀏覽器歷史悠久、社區大傳統自動化測試、兼容性測試Puppete…

動態數組:ArrayList的實現原理

動態數組&#xff1a;ArrayList的實現原理 大家好&#xff01;今天我們來聊聊Java集合框架中一個非常重要的數據結構——ArrayList。就像我們日常生活中使用的伸縮收納盒一樣&#xff0c;ArrayList可以根據需要自動調整大小&#xff0c;既方便又高效。那么它是如何實現這種&quo…

MIPI DSI(五) DBI 和 DPI 格式

關于 DBI 和 DPI 這兩種格式的詳細協議內容&#xff0c;請參考《MIPI Alliance Standard for Display Bus Interface&#xff08;V2.0&#xff09; .pdf》和《MIPI Alliance Standard for Display Pixel Interface&#xff08;DPI- 2&#xff09; .pdf》這兩份文檔。首先先了解…

FRP Ubuntu 服務端 + MacOS 客戶端配置

一、服務端配置 1、下載frp并解壓 # 創建目錄并進入 mkdir -p /opt/frp && cd /opt/frp # 下載最新版&#xff08;替換URL為GitHub發布頁最新版本&#xff09; wget https://github.com/fatedier/frp/releases/download/v0.59.0/frp_0.59.0_linux_amd64.tar.gz # 解壓 …