一、Astar演算法c
Astar演算法（A*）是一種常用的尋路演算法，因為它可以在一張地圖中找到最短路徑，並且計算量不大，所以被廣泛應用於自動化尋路系統，遊戲中的NPC移動等方面。A*演算法的思路是在搜索過程中維護一個開放列表和一個封閉列表，搜索過程中通過啟發式函數預測此路徑的長度，來選擇最優的路徑。使用C語言實現A*演算法如下：
void Astar()
{
while(!openList.empty())
{
AstarPt* present = openList.top();
openList.pop();
if (present->row == endPt->row && present->col == endPt->col)
{
endPt->pre = present->pre;
return;
}
closeList.push_back(present);
getSuccessors(present);
}
}
二、Astar演算法與Dijkstra演算法
Astar演算法與Dijkstra演算法都是用於尋路問題的經典演算法。Dijkstra演算法是一種基於圖論的貪心演算法，在某些特殊情況下可能會陷入死循環，而Astar演算法不會。Astar演算法在計算過程中預測剩餘距離，因此總是朝著目標方向前進，相比於Dijkstra演算法，它更加高效。而Dijkstra演算法要求每個路徑權值都為正數，因為它在計算時會擴展所有相鄰節點，網格地圖中代價計算比較困難。因此，對於需要在網格地圖上搜索路徑的問題，Astar演算法是更好的選擇。
三、Astar演算法原理
Astar演算法維護兩個列表：開放列表和封閉列表。初始時，將起點放入開放列表中。在每次循環中，從開放列表中選取預估代價最小的節點出隊，並將其放入封閉列表中。接下來，通過計算預估剩餘距離將當前節點的鄰居入隊到開放列表中。在路徑被找到之前，重複執行此過程。當路徑被找到時，從終點開始遍歷每個節點的pre指針，直到回到起始節點，即可得到這條路徑。
四、Astar演算法Python
Python語言實現Astar演算法非常方便，以下是一個簡單的實現例子：
def Astar(start, end, graph):
openList = PriorityQueue()
openList.put(start, 0)
cameFrom = {}
gScore = defaultdict(lambda: float('inf'))
gScore[start] = 0
fScore = defaultdict(lambda: float('inf'))
fScore[start] = heuristic(start, end)
while not openList.empty():
current = openList.get()
if current == end:
return construct_path(cameFrom, start, end)
for neighbor in graph[current]:
tentative_gScore = gScore[current] + graph[current][neighbor]
if tentative_gScore < gScore[neighbor]:
cameFrom[neighbor] = current
gScore[neighbor] = tentative_gScore
fScore[neighbor] = tentative_gScore + heuristic(neighbor, end)
if neighbor not in openList.queue:
openList.put(neighbor, fScore[neighbor])
return "No path"
五、Astar演算法代碼
以下是一個簡單的偽代碼實現：
function A* (start,goal)
closedList := {}; //已被評估過的點
openList := {}; //待評估的點
visitedFrom := {}; //記錄每個點來自於哪個點
gScore := {}; //從起始點到此點已經花費的代價
fScore := {}; //總代價 = 已花費的代價 + 剩餘代價
push start into openList
gScore[start] := 0
fScore[start] := gScore[start] + heuristic_cost_estimate(start, goal)
while openList is not empty
current := the node in openList having the lowest fScore[] value
if current = goal
return reconstruct_path(visitedFrom,goal)
remove current from openList
push current into closedList
for each neighbor in neighbor_nodes(current)
if neighbor in closedList
continue
tentative_gScore := gScore[current] + distance_between(current,neighbor)
if neighbor not in openList or tentative_gScore < gScore[neighbor]
visitedFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
if neighbor not in openList
push neighbor into openList
return failure
六、Astar演算法例子
以下是一個基於地圖的Astar演算法例子：
def heuristic_cost_estimate(current, goal):
return abs(current.x - goal.x) + abs(current.y - goal.y)
def reconstruct_path(visitedFrom, current):
total_path = [current]
while current in visitedFrom:
current = visitedFrom[current]
total_path.append(current)
return total_path
def Astar(start, goal, graph):
closedList = []
openList = [start]
visitedFrom = {}
gScore = {start: 0}
fScore = {start: heuristic_cost_estimate(start, goal)}
while openList:
current = min(openList, key=lambda x:fScore[x])
if current == goal:
return reconstruct_path(visitedFrom, current)
openList.remove(current)
closedList.append(current)
for neighbor in graph[current]:
if neighbor in closedList:
continue
tentative_gScore = gScore[current] + graph[current][neighbor]
if neighbor not in openList or tentative_gScore < gScore[neighbor]:
visitedFrom[neighbor] = current
gScore[neighbor] = tentative_gScore
fScore[neighbor] = gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
if neighbor not in openList:
openList.append(neighbor)
return "No path"
七、Astar演算法尋路
在遊戲開發中，Astar演算法可以被用於尋路，以下是一個簡單的尋路實現例子：
public class AstarPathfinding : MonoBehaviour {
Node startNode;
Node endNode;
public List FindPath(Node start, Node end)
{
startNode = start;
endNode = end;
List openSet = new List();
HashSet closedSet = new HashSet();
openSet.Add(startNode);
while (openSet.Count > 0)
{
Node currentNode = openSet[0];
for (int i = 1; i < openSet.Count; i++)
{
if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
{
currentNode = openSet[i];
}
}
openSet.Remove(currentNode);
closedSet.Add(currentNode);
if (currentNode == endNode)
{
return RetracePath(startNode, endNode);
}
foreach (Node neighbor in currentNode.neighbors)
{
if (!neighbor.walkable || closedSet.Contains(neighbor))
{
continue;
}
int newCostToNeighbor = currentNode.gCost + GetDistance(currentNode, neighbor);
if (newCostToNeighbor < neighbor.gCost || !openSet.Contains(neighbor))
{
neighbor.gCost = newCostToNeighbor;
neighbor.hCost = GetDistance(neighbor, endNode);
neighbor.parent = currentNode;
if (!openSet.Contains(neighbor))
{
openSet.Add(neighbor);
}
}
}
}
return null;
}
//...
}
八、Astar演算法和貪心演算法
貪心演算法和Astar演算法有著類似的思路，都是在計算過程中維護一個開放列表和一個封閉列表，且都使用啟發式函數來決定哪個節點應該被擴展。但貪心演算法只考慮當前擴展節點，而Astar演算法還要考慮目標節點的距離，這使它變得更符合現實情況。Astar演算法相對於貪心演算法來說，能夠找到更優的路徑。
九、Astar演算法優化
Astar演算法的運行效率取決於啟發函數的選擇和數據結構的優化。設計一個好的啟發函數非常重要，它決定了演算法的速度和精度。另外，在實際的應用過程中可以採用一些優化策略來加速運算，如減少存儲空間、預處理數據等。
十、Astar演算法的優缺點
Astar演算法的優點：
- 可以找到最短路徑
- 啟發式搜索可以減少搜索的時間和空間
- 應用廣泛，特別是在遊戲AI、數據挖掘等領域
Astar演算法的缺點：
- 對數據結構要求較高
- 啟發函數的設計非常重要，不好的啟發函數可能導致演算法性能下降
- 有可能陷入局部最優解
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/244630.html
微信掃一掃 
支付寶掃一掃 