?????? 歡迎來到我的博客。希望您能在這里找到既有價(jià)值又有趣的內(nèi)容，和我一起探索、學(xué)習(xí)和成長。歡迎評(píng)論區(qū)暢所欲言、享受知識(shí)的樂趣！

• 推薦：數(shù)據(jù)分析螺絲釘?shù)氖醉?格物致知 終身學(xué)習(xí) 期待您的關(guān)注
  

• 導(dǎo)航：

  • LeetCode解鎖1000題: 打怪升級(jí)之旅：每題都包括3-5種算法，以及詳細(xì)的代碼實(shí)現(xiàn)，刷題面試跳槽必備
  • 漫畫版算法詳解：通過漫畫的形式和動(dòng)態(tài)GIF圖片把復(fù)雜的算法每一步進(jìn)行詳細(xì)可視解讀，看一遍就掌握
  • python源碼解讀：解讀python的源代碼與調(diào)用關(guān)系，快速提升代碼質(zhì)量
  • python數(shù)據(jù)分析可視化：企業(yè)實(shí)戰(zhàn)案例：企業(yè)級(jí)數(shù)據(jù)分析案例與可視化，提升數(shù)據(jù)分析思維和可視化能力
  • 程序員必備的數(shù)學(xué)知識(shí)與應(yīng)用：全面詳細(xì)的介紹了工程師都必備的數(shù)學(xué)知識(shí)

期待與您一起探索技術(shù)、持續(xù)學(xué)習(xí)、一步步打怪升級(jí) 歡迎訂閱本專欄????

引言

在近期臺(tái)灣附近的軍事演習(xí)中，部隊(duì)的調(diào)動(dòng)和戰(zhàn)術(shù)安排需要精確的路徑規(guī)劃，以確保各單位能夠迅速、高效地到達(dá)指定位置。類似地，在計(jì)算機(jī)科學(xué)中，路徑規(guī)劃算法被廣泛應(yīng)用于導(dǎo)航、機(jī)器人控制和游戲開發(fā)等領(lǐng)域。今天，我們將通過軍事演習(xí)的視角，解析一種經(jīng)典的路徑規(guī)劃算法——A*算法。

軍演背景

在一次模擬軍演中，指揮官需要安排部隊(duì)從多個(gè)起點(diǎn)移動(dòng)到指定的戰(zhàn)略位置。這些位置可能位于島嶼的不同角落，途中還有各種障礙物，如山地、河流和敵方防御工事。為了在復(fù)雜地形中找到最優(yōu)路徑，指揮官?zèng)Q定使用A*算法。

A*算法的原理

A算法是一種啟發(fā)式搜索算法，它結(jié)合了廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）的優(yōu)點(diǎn)，通過評(píng)估當(dāng)前路徑的代價(jià)和預(yù)估的剩余路徑代價(jià)來找到最優(yōu)路徑。A算法使用一個(gè)優(yōu)先級(jí)隊(duì)列來選擇下一步移動(dòng)的節(jié)點(diǎn)。

關(guān)鍵概念

1. 起點(diǎn)（Start）：部隊(duì)的出發(fā)位置。
2. 終點(diǎn)（Goal）：部隊(duì)的目標(biāo)位置。
3. 開放列表（Open List）：包含待評(píng)估的節(jié)點(diǎn)。
4. 關(guān)閉列表（Closed List）：包含已評(píng)估的節(jié)點(diǎn)。
5. 代價(jià)函數(shù)（f(n)）：用于評(píng)估節(jié)點(diǎn)的優(yōu)先級(jí)，計(jì)算公式為 f(n) = g(n) + h(n)，其中：
   • g(n)：從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)。
   • h(n)：從當(dāng)前節(jié)點(diǎn)到終點(diǎn)的預(yù)估代價(jià)（啟發(fā)式函數(shù)）。

軍事演習(xí)中的A*算法應(yīng)用

步驟

1. 初始化：

   • 將起點(diǎn)添加到開放列表，設(shè)定 g(start) = 0，h(start) 為起點(diǎn)到終點(diǎn)的預(yù)估代價(jià)。

2. 選擇節(jié)點(diǎn)：

   • 從開放列表中選擇 f(n) 最小的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。

3. 生成后繼節(jié)點(diǎn)：

   • 為當(dāng)前節(jié)點(diǎn)生成所有可能的后繼節(jié)點(diǎn)，并計(jì)算它們的 g 值和 h 值。
   • 如果某個(gè)后繼節(jié)點(diǎn)已經(jīng)在關(guān)閉列表中，跳過它。
   • 如果某個(gè)后繼節(jié)點(diǎn)不在開放列表中或新的 g 值更低，更新它的 g 值和 f 值，并將其父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)。

4. 終止條件：

   • 如果當(dāng)前節(jié)點(diǎn)是終點(diǎn)，算法結(jié)束，并通過回溯父節(jié)點(diǎn)鏈得到最優(yōu)路徑。
   • 如果開放列表為空，表示沒有找到路徑。

示例

假設(shè)部隊(duì)需要從A點(diǎn)福州移動(dòng)到B點(diǎn)臺(tái)州，地圖如下：

A . . X . . . . . .
X X . X . X X X . .
. . . X . . . X . .
. X . . . X . . . .
. X X X . X X X X B

其中，. 表示可通行區(qū)域，X 表示障礙物。

1. 初始化：

   開放列表：[(A, f(A))]
   關(guān)閉列表：[]
   

2. 選擇節(jié)點(diǎn)：
   • 選擇A作為當(dāng)前節(jié)點(diǎn)。
   • 生成A的后繼節(jié)點(diǎn)。
3. 更新列表：

   開放列表：[(A1, f(A1)), (A2, f(A2)), ...]
   關(guān)閉列表：[A]
   

4. 重復(fù)：
   • 持續(xù)選擇開放列表中 f(n) 最小的節(jié)點(diǎn)，生成后繼節(jié)點(diǎn)，更新開放和關(guān)閉列表，直到找到B或開放列表為空。

A*算法的代碼實(shí)現(xiàn)

import heapqdef heuristic(a, b):"""啟發(fā)式函數(shù)，計(jì)算從節(jié)點(diǎn)a到節(jié)點(diǎn)b的曼哈頓距離"""return abs(a[0] - b[0]) + abs(a[1] - b[1])def a_star_search(start, goal, grid):"""使用A*算法在給定的網(wǎng)格(grid)中查找從start到goal的最優(yōu)路徑"""# 初始化開放列表并將起點(diǎn)添加到其中open_list = []heapq.heappush(open_list, (0, start))# 初始化記錄路徑的字典came_from = {}# 初始化g_score和f_score字典g_score = {start: 0}f_score = {start: heuristic(start, goal)}while open_list:# 從開放列表中取出f值最小的節(jié)點(diǎn)current = heapq.heappop(open_list)[1]# 如果當(dāng)前節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，回溯路徑并返回if current == goal:path = []while current in came_from:path.append(current)current = came_from[current]path.append(start)path.reverse()return path# 生成當(dāng)前節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:neighbor = (current[0] + dx, current[1] + dy)# 檢查鄰居節(jié)點(diǎn)是否在網(wǎng)格范圍內(nèi)且不是障礙物if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] == '.':tentative_g_score = g_score[current] + 1# 如果鄰居節(jié)點(diǎn)不在g_score中或新的g值更低，更新路徑和分?jǐn)?shù)if neighbor not in g_score or tentative_g_score < g_score[neighbor]:came_from[neighbor] = currentg_score[neighbor] = tentative_g_scoref_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)heapq.heappush(open_list, (f_score[neighbor], neighbor))# 如果開放列表為空且未找到目標(biāo)節(jié)點(diǎn)，返回Nonereturn None# 示例地圖
grid = [['A', '.', '.', 'X', '.', '.', '.', '.', '.', '.'],['X', 'X', '.', 'X', '.', 'X', 'X', 'X', '.', '.'],['.', '.', '.', 'X', '.', '.', '.', 'X', '.', '.'],['.', 'X', '.', '.', '.', 'X', '.', '.', '.', '.'],['.', 'X', 'X', 'X', '.', 'X', 'X', 'X', 'X', 'B']
]start = (0, 0)  # A點(diǎn)的位置（福州）
goal = (4, 9)   # B點(diǎn)的位置（臺(tái)州）# 執(zhí)行A*搜索算法并打印找到的路徑
path = a_star_search(start, goal, grid)
print("找到的路徑:", path)

總結(jié)

通過軍事演習(xí)的視角，我們了解了A算法在路徑規(guī)劃中的應(yīng)用。A算法通過結(jié)合實(shí)際代價(jià)和預(yù)估代價(jià)，能夠高效地找到最優(yōu)路徑，適用于復(fù)雜的地形和障礙物環(huán)境。希望這個(gè)故事和示例能夠幫助你更好地理解A*算法的工作原理及其在實(shí)際中的應(yīng)用。

🌹🌹如果覺得這篇文對你有幫助的話，記得一鍵三連關(guān)注、贊👍🏻、收藏是對作者最大的鼓勵(lì)，非常感謝 ?(^_-)

????關(guān)注公眾號(hào) 數(shù)據(jù)分析螺絲釘 回復(fù) 學(xué)習(xí)資料 領(lǐng)取高價(jià)值免費(fèi)學(xué)習(xí)資料?(^_-)