Python - 深夜数据结构与算法之 Heuristic Search

目录

一.引言

二.启发式搜索简介

1.BFS 广度优先

2.A* Search

3.估价函数

三.经典算法实战

1.Binary-Shortest-Path [1091]

2.Sliding-Puzzle [773]

四.总结

---

一.引言

Heuristic Search 启发式搜索，又名 A* 搜索，其不基于广度、也不基于深度而是基于元素的优先级进行遍历搜索，不断优化搜索的方向提高搜索效率，下面我们看下启发式搜索的常用方式与算法例题。

二.启发式搜索简介

1.BFS 广度优先

2.A* Search

比起从 queue 里一个一个的顺序弹出，我们可以加入一些智能的元素，让弹出的元素使得搜索的方向更加优化，所以我们把 queue 替换成了 priotity_queue，而优先级的定义则需要我们根据实际问题构建一个估价函数 h(n)。

3.估价函数

上面的优先队列的评估标准需要基于 h(n)，这个就是一个启发式的方法，其返回一个非负实数，我们可以认为返回的值越大，当前的节点相对于最终的结果搜索方向更优，即 h(n) 越大，元素优先级越高，越先遍历该元素。

三.经典算法实战

1.Binary-Shortest-Path [1091]

二进制最短路径:?https://leetcode.cn/problems/shortest-path-in-binary-matrix

◆ 题目分析

根据 BFS 逐层遍历，当我们第一次到达终点时，也就是最短路径到达时。

◆ BFS

class Solution(object):
    def shortestPathBinaryMatrix(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        M = len(grid)
        if grid[0][0] == 1 or grid[M - 1][M - 1] == 1:
            return -1

        stack = [(0, 0, 1)]
        grid[0][0] = 1

        # 8联通
        direction = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

        while stack:
            row, col, step = stack.pop(0)
            # 终止条件
            if row == M - 1 and col == M - 1:
                return step

            # 8 连通图
            for dx, dy in direction:
                i, j = row + dx, col + dy

                if 0 <= i < M and 0 <= j < M and grid[i][j] == 0:
                    grid[i][j] = 1
                    stack.append((i, j, step + 1))

        return -1

这里有的同学可能有疑问，明明8个方向，为什么直接就返回 step 了，下面提供两种思路：

A.广度优先每一层的行走距离是一样的，如果当前层率先走到终点，则其一定是最短的

B.我们对每个走过的点标为了 1，如果一个点需要先到这个标 1 的点再去终点，那么它一定没有标 1 这个点近。这个找了个示例，大家更好理解下，对于 [0,1] 位置，其可以走到 [0, 2] 和 [1, 2]，如果先走 [0, 2] 再走 [1, 2] 到 [2, 2]，那么一定没有 [1, 2] 到 [2, 2] 近。而标记过后我们也可以看出，[0, 2] 位置已经无路可走了，而 [1, 2] 还能走。

    grid = [[0, 0, 0],  => grid = [[1, 1, 1],
            [1, 1, 0],             [1, 1, 1],
            [1, 1, 0]]             [1, 1, 0]]

◆ A* x BFS

import heapq


class Solution(object):

    def shortestPathBinaryMatrix(self, grid):

        # 边界条件
        n = len(grid)
        if not grid or grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1
        elif n <= 2:
            return n

        # 估价函数
        def heuristic(x, y):
            return max(abs(n - 1 - x), abs(n - 1 - y))

        h = []
        direction = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        # (val, (row, col, step))
        heapq.heappush(h, (0, (0, 0, 1)))

        while h:
            _, (row, col, step) = heapq.heappop(h)

            # 遍历点标记
            if grid[row][col] == 1:
                continue

            grid[row][col] = 1

            for dx, dy in direction:
                i, j = row + dx, col + dy

                if i == n - 1 and j == n - 1:
                    return step + 1

                if 0 <= i < n and 0 <= j < n and grid[i][j] == 0:
                    # 估价函数为 步数 + 距离 最小即最短路径
                    heapq.heappush(h, (step + heuristic(i, j), (i, j, step + 1)))

        return -1

heapq 是小根堆，所以我们的估价函数需要满足距离越近值越小，从而越先遍历近的点，上面的 L1 曼哈顿距离满足相距越近距离越小。

2.Sliding-Puzzle [773]

滑动谜题:?https://leetcode.cn/problems/sliding-puzzle/description/

◆ 题目分析

这个题可以将 2x3 网格转换一个 len = 6 的字符串，然后每次遍历 0 可以交换的位置，依次 BFS 直到达到 012345 的状态，所以本题就可以转换为一个字符接龙的问题，可以回看前面双向 BFS 的章节。

◆ BFS

class Solution(object):
    def slidingPuzzle(self, board):
        """
        :type board: List[List[int]]
        :rtype: int
        """
        # 记录下一次可走的位置
        moves = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }

        used = set()
        cnt = 0
        s = "".join(str(c) for row in board for c in row)

        # 格子以及0的位置
        q = [(s, s.index("0"))]

        while q:
            new = []
            for s, i in q:
                used.add(s)
                if s == "123450":
                    return cnt
                arr = [c for c in s]
                for move in moves[i]:
                    new_arr = arr[:]
                    new_arr[i], new_arr[move] = new_arr[move], new_arr[i]
                    new_s = "".join(new_arr)
                    if new_s not in used:
                        new.append((new_s, move))
            cnt += 1
            q = new

        return -1

◆ 双向 BFS

class Solution(object):
    def slidingPuzzle(self, board):
        """
        :type board: List[List[int]]
        :rtype: int
        """
        moves = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }

        used = set()
        cnt = 0
        s = "".join(str(c) for row in board for c in row)

        # 格子以及0的位置
        front = [s]
        back = ["123450"]

        while front and back:
            new = []
            for s in front:
                used.add(s)
                index = s.index("0")

                # 相遇了
                if s in back:
                    return cnt

                arr = [c for c in s]
                for move in moves[index]:
                    new_arr = arr[:]
                    new_arr[index], new_arr[move] = new_arr[move], new_arr[index]
                    new_s = "".join(new_arr)
                    if new_s not in used:
                        new.append(new_s)
            cnt += 1

            if len(new) > len(back):
                front, back = back, new
            else:
                front = new

        return -1

套用单词接龙模版，直接双向 BFS 即可。?

◆ A* x BFS

import heapq
M, N = 2, 3

class Solution:
    def slidingPuzzle(self, board):
        
        def h(s):
            dist = 0
            s2 = "123450"
            i1 = s.index("0")
            i2 = s2.index("0")
            x1, y1 = i1 % N, i1 // N
            x2, y2 = i2 % N, i2 // N
            dist += abs(x1 - x2) + abs(y1 - y2)
            return dist
        
        end_state = "123450"
        
        board = board[0] + board[1]
        s = "".join(str(c) for c in board)
        moves = [(1, 3), (0, 2, 4), (1, 5), (0, 4), (1, 3, 5), (2, 4)]
        visited = set()
        q = [] 
        step = 0
        heapq.heappush(q, (h(s) + step, s, step))
        while q:
            sample = heapq.heappop(q)
            state, step = sample[1], sample[2]
            if state == end_state:
                return step
            now = state.index('0')
            for next0 in moves[now]:
                _state = list(state)
                _state[next0], _state[now] = _state[now], _state[next0]
                _state = "".join(_state)
                if _state not in visited: 
                    heapq.heappush(q, (h(_state) + step + 1, _state, step + 1))
            visited.add(state)
        return -1
            

和上面同理，把无脑 append + pop 改成使用 headq 进行 push 和 pop，距离采用曼哈顿距离计算，?这里由于网格?M/N 的大小比较小，所以 BFS 会比 A* 快一些，如果网格的增加，A* 会逐渐体现出其优势。

四.总结

根据场景的不同，我们可以选择 BFS -> 双向 BFS -> A* Search + h(n)??-> 双向 A* Search + h(n)，这里 A* 主要区别在于估价函数的选择，下面链接了给出了常用的五种距离函数，对于我们常见的二维网格 + 抵达终点的情况，我们一般使用曼哈顿距离即可。

A* 常用距离函数:?https://dataaspirant.com/five-most-popular-similarity/