每日算法 二进制矩阵中的最短路径

例题：https://leetcode.cn/problems/shortest-path-in-binary-matrix/

BFS 解法

func shortestPathBinaryMatrix(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    if grid[0][0] == 1 || grid[m-1][n-1] == 1 {
        return -1
    }

    q := make([][2]int, 0)
    walked := make([][]bool, m)
    for i := range walked {
        walked[i] = make([]bool, n)
    }

    q = append(q, [2]int{0,0})
    walked[0][0] = true
    pathLen := 1

    dirs := [8][2]int{
        {1,0}, {1,1}, {0,1}, {-1,1},
        {-1,0}, {-1,-1}, {0,-1}, {1,-1},
    }

    for len(q) > 0 {
        size := len(q)
        for i := 0; i < size; i++ {
            cur := q[0]
            q = q[1:]
            x, y := cur[0], cur[1]
            if x == m-1 && y == n-1 {
                return pathLen
            }

            for j := 0; j < 8; j++ {
                nextX := x + dirs[j][0]
                nextY := y + dirs[j][1]
                if nextX >= 0 && nextX < m && nextY >= 0 && nextY < n &&
                    grid[nextX][nextY] == 0 && !walked[nextX][nextY] {
                    q = append(q, [2]int{nextX, nextY})
                    walked[nextX][nextY] = true
                }
            }
        }
        pathLen += 1
    }
    
    return -1
}

运算过程：

pathLen=1: (0,0)
pathLen=2: (0,0)→(0,1)
pathLen=3: (0,1)→(0,2)  和  (0,1)→(1,2)    ← 同一层同时被发现
pathLen=4: (0,2)→(1,2)  已访问，跳过（死路）
           (1,2)→(2,2)  到达终点，返回 4

这就是 BFS 的最短路径解法。注意代码里的 walked 数组：一旦某个坐标被入队，就会被标记为 true，后续无论从哪个方向再次走到这里，都会直接跳过。

所有汇聚到同一个节点的路径会被合并，算法不会枚举"1→2→3→6"和"1→2→6"两条分支，而是只保留先到达 6 的那条最优路径。节点总数是有限的，循环次数也有明确上限，不会出现指数级爆炸。

但我们拓展一下思路：如果矩阵不是 5x5，而是 1000x1000，且大部分区域都是空地呢？

BFS 会像水波一样从起点向四周均匀扩散，探索大量与终点无关的节点。明明终点在右下角，它却认真地检查左上角每一个能走的格子。

如果能让算法"猜"一下终点在哪个方向，优先往那边走，岂不是快很多？A* 算法就是这个思路。

A* 算法

A* 是一种启发式搜索算法，在 Dijkstra 的基础上增加了一个启发函数 h(n)，用估价函数 f(n) = g(n) + h(n) 来指导搜索方向。

• g(n)：从起点到当前节点的实际代价
• h(n)：从当前节点到终点的估计代价（如切比雪夫距离）

type Point struct{ x, y int }

type Node struct {
    p      Point
    g      float64 // 从起点到当前节点的实际步数
    h      float64 // 从当前节点到终点的估计步数（启发值）
    f      float64 // g + h，综合优先级
    parent *Node   // 父节点指针，用于回溯路径
}

// 优先队列（最小堆），按 f 值升序排列
type PQ []*Node

func (q PQ) Len() int           { return len(q) }
func (q PQ) Less(i, j int) bool  { return q[i].f < q[j].f }
func (q PQ) Swap(i, j int)       { q[i], q[j] = q[j], q[i] }

func (q *PQ) Push(v any)  { *q = append(*q, v.(*Node)) }
func (q *PQ) Pop() any {
    n := len(*q)
    v := (*q)[n-1]
    *q = (*q)[:n-1]
    return v
}

func astar(grid [][]int, start, end Point) []Point {
    // 启发函数：切比雪夫距离
    // 八方向可以斜着走，一步能同时减少 x 和 y 的差距
    h := func(a, b Point) float64 {
        dx := abs(a.x - b.x)
        dy := abs(a.y - b.y)
        if dx > dy {
            return float64(dx)
        }
        return float64(dy)
    }

    open := &PQ{}
    heap.Push(open, &Node{p: start, g: 0, h: h(start, end), f: h(start, end)})

    // best 记录到达每个坐标的最小实际代价 g
    best := map[Point]float64{start: 0}

    dirs := []Point{
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},           {0, 1},
        {1, -1},  {1, 0},  {1, 1},
    }

    for open.Len() > 0 {
        cur := heap.Pop(open).(*Node)
        if cur.p == end {
            var path []Point
            for n := cur; n != nil; n = n.parent {
                path = append([]Point{n.p}, path...)
            }
            return path
        }

        for _, d := range dirs {
            nb := Point{cur.p.x + d.x, cur.p.y + d.y}
            if nb.x < 0 || nb.x >= len(grid) || nb.y < 0 || nb.y >= len(grid[0]) || grid[nb.x][nb.y] == 1 {
                continue
            }

            g := cur.g + 1

            // 如果 nb 之前被访问过，且之前的路径更短，跳过
            if v, ok := best[nb]; ok && g >= v {
                continue
            }

            best[nb] = g
            heap.Push(open, &Node{
                p:      nb,
                g:      g,
                h:      h(nb, end),
                f:      g + h(nb, end),
                parent: cur,
            })
        }
    }
    return nil
}

两个算法的核心对比

BFS 的 walked 和 A* 的 best，本质上做的是同一件事：避免重复处理已经找到最优解的节点。这是寻路算法不会指数级爆炸的根本原因。

而 A* 额外引入的 h(n)，则是在"保证正确"的前提下，给搜索加了一个"方向感"——让算法优先探索那些"看起来离终点更近"的节点。在开放地图上，这能显著减少搜索空间；在狭窄迷宫里，它退化为有序的 BFS，但至少不会更差。

思路：定义 f = g + h，用优先队列每次取 f 最小的节点探索，通过 best 剪枝避免回路，找到终点后通过 parent 指针回溯路径。

补充

启发函数怎么选

A* 要求启发函数不能高估实际代价（h(n) ≤ 实际代价），选错会导致路径不是最短。

// 启发函数 1：曼哈顿距离 —— 四方向移动（只能上下左右）
func manhattan(a, b Point) float64 {
    return math.Abs(float64(a.X-b.X)) + math.Abs(float64(a.Y-b.Y))
}

// 启发函数 2：切比雪夫距离 —— 八方向移动（含对角线，每步代价相同）
// 斜走一步能同时减少 x 和 y，所以取 max(|dx|, |dy|)
func chebyshev(a, b Point) float64 {
    dx := math.Abs(float64(a.X - b.X))
    dy := math.Abs(float64(a.Y - b.Y))
    if dx > dy {
        return dx
    }
    return dy
}

// 启发函数 3：欧几里得距离 —— 连续空间/任意角度移动
func euclidean(a, b Point) float64 {
    dx := float64(a.X - b.X)
    dy := float64(a.Y - b.Y)
    return math.Sqrt(dx*dx + dy*dy)
}

核心原则：h 是"乐观估计"——假设没有障碍时的最少步数。只要满足这一点，A* 就保证找到最短路径。