一、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/n/244630.html
微信扫一扫 
支付宝扫一扫 