A* 算法

发表于 | 分类于
字数统计: 1.3k | 阅读时长 ≈ 5
A* 算法是一种高效的图搜索算法，专门用于寻找从起点到终点的最短路径。它通过结合实际代价和启发式估计代价来评估路径的总成本，其中启发式函数 h(n) 用于估计从当前节点到目标节点的代价，而 g(n) 表示从起点到当前节点的实际代价。A* 算法维护两个列表：Open 表用于存储待探索的节点，而 Close 表记录已探索的节点。算法流程包括从 Open 表中选择 f(n) 值最小的节点进行扩展，然后更新其邻居节点，并重复此过程直至找到目标或 Open 表为空。A* 算法的有效性依赖于启发式函数的设计，以及确保分支因子有限、边的代价为正且估计代价不大于真实代价。在 Golang 中，A* 算法可以通过定义点、节点和优先队列来实现，并使用启发式函数来评估节点之间的距离。

概述

A* 算法一种图搜索算法，用于寻找一条从起始点到目标点的最短路径。

A* 算法的核心思想是使用启发式方法来评估从当前节点到目标节点的代价，结合从起始点到当前节点的实际代价，来估算总路径代价。

代价函数表示方程

  • ：从起始点到节点 n 的实际代价
  • ：从节点 n 到目标点的估计代价
  • ：从起始点经过当前节点 n 到达目标点的估计代价

维护两个表：Open 表和 Close 表

Open 表

  • Open 表用来存放当前未扩展的节点，也就是还没有被探索的节点。
  • Open 表中的节点按照一定的规则排序，这里可以使用优先队列实现。对于 A* 算法，排序规则为 值越小的（估计代价越小）优先遍历。

Close 表

Close 表用来存放已扩展的节点，即已被探索的节点。

算法流程

  1. 将起始点加入 Open 表
  2. 从 Open 表中选择 值最小的节点进行扩展，并将选定节点从 Open 表移动到 Close 表。
  3. 如果选定节点的邻居节点不再 Close 表中（未扩展），则计算邻居节点的 值，并加入到 Open 表中。
  4. 重复执行步骤 2 到 3，直到目标节点被加入到 Close 表中，或者 Open 表为空。

不难看出，A* 算法的核心在于如何设计估计函数 。且估计函数 越接近真实值，算法的效果越好。

如何确保 A* 算法有效（可接纳性条件）

  1. 任何节点的分支因子 b 有限

有限的分支因子保证了在每一步搜索中，算法都只会考虑有限数量的后继节点，从而避免了无限搜索的问题

  1. 任何边（或动作）都有正的代价，即

要求每条边的代价是正的，意味着在搜索过程中，前进到任何节点都需要付出一定的成本，没有免费的移动。这保证了算法在评估路径时能够考虑到每一步的代价，从而找到成本最低的路径。

  1. 对代价的估计小于真实代价，即

这个条件保证了A*算法的优化性，即算法总是朝着目标前进，而不会因为错误的估计而走弯路

为什么 A* 算法要确保对代价的估计小于真实代价

如果启发式函数 大于真实代价 h，可能会导致次优解被优先考虑，从而增加了错过最短路径的风险。

假设起始节点是 start，目标节点是 end，最优解经过 ，次优解经过 ，可能会发生以下情况：

  • 但 不一定小于

Golang 实现

定义点

1
2
3
4
5
package astar

type Point struct {
	X, Y int
}

定义优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package astar

type Node struct {
	Point
	// F = G + H
	// G: 从起点到当前节点的实际代价
	// H: 从当前节点到目标节点的估计代价
	G, H float64
	// 父节点: 用于路径回溯
	Parent *Node
}

// PriorityQueue 用 heap 模拟优先队列
type PriorityQueue []*Node

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].G+pq[i].H < pq[j].G+pq[j].H
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(v any) {
	*pq = append(*pq, v.(*Node))
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

A* 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package astar

import (
	"container/heap"
	"math"
)

func heuristic(a, b Point) float64 {
	return math.Abs(float64(a.X-b.X)) + math.Abs(float64(a.Y-b.Y))
}

// 从终点回溯到起点  重建路径
func reconstructPath(endNode *Node) []*Node {
	path := []*Node{endNode}
	for endNode.Parent != nil {
		endNode = endNode.Parent
		path = append([]*Node{endNode}, path...)
	}
	return path
}

// 检查点是否在网格内且可通行
func isWalkable(point Point, grid [][]bool) bool {
	return point.X >= 0 && point.Y >= 0 && point.X < len(grid) && point.Y < len(grid[0]) && grid[point.X][point.Y]
}

func AStar(start, end Point, grid [][]bool) []*Node {
	// 使用优先队列存储待处理节点
	openList := PriorityQueue{}
	// 存储已经处理过的节点  避免重复处理
	closedSet := make(map[Point]bool)
	startNode := &Node{Point: start, G: 0, H: heuristic(start, end)}
	openList = append(openList, startNode)
	// 初始化为一个有效的小顶堆
	heap.Init(&openList)

	for openList.Len() > 0 {
		current := heap.Pop(&openList).(*Node)
		if current.Point == end {
			return reconstructPath(current)
		}
		closedSet[current.Point] = true

		directions := []Point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 4个方向
		for _, dir := range directions {
			neighbor := Point{current.Point.X + dir.X, current.Point.Y + dir.Y}
			// 对于bool类型的map  key不存在也将返回false
			if isWalkable(neighbor, grid) && !closedSet[neighbor] {
				// 假设每个格子的代价是1
				gScore := current.G + 1
				hScore := heuristic(neighbor, end)
				neighborNode := &Node{Point: neighbor, G: gScore, H: hScore, Parent: current}
				heap.Push(&openList, neighborNode)
				closedSet[neighbor] = true
			}
		}
	}
	return nil
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func main() {
	// 定义网格，true表示可通行，false表示障碍物
	grid := [][]bool{
		{true, true, false, true, true},
		{true, false, true, false, true},
		{true, true, true, true, true},
		{false, true, false, true, true},
		{true, true, true, true, true},
	}

	start := astar.Point{0, 0}
	end := astar.Point{4, 4}
	path := astar.AStar(start, end, grid)
	if path != nil {
		for _, node := range path {
			fmt.Printf("(%d, %d)\n", node.X, node.Y)
		}
	} else {
		fmt.Println("No path found")
	}
}
0%