网站开发的基础知识,网站设计哪里公司好,网站建设实施方案,千阳做网站目录
一.引言
二.启发式搜索简介
1.BFS 广度优先
2.A* Search
3.估价函数
三.经典算法实战
1.Binary-Shortest-Path [1091]
2.Sliding-Puzzle [773]
四.总结 一.引言
Heuristic Search 启发式搜索#xff0c;又名 A* 搜索#xff0c;其不基于广度、也不基于深度而是…
目录
一.引言
二.启发式搜索简介
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: intM len(grid)if grid[0][0] 1 or grid[M - 1][M - 1] 1:return -1stack [(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 dyif 0 i M and 0 j M and grid[i][j] 0:grid[i][j] 1stack.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 heapqclass 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 -1elif 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:continuegrid[row][col] 1for dx, dy in direction:i, j row dx, col dyif i n - 1 and j n - 1:return step 1if 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 0s .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 cntarr [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 1q newreturn -1 ◆ 双向 BFS
class Solution(object):def slidingPuzzle(self, board)::type board: List[List[int]]:rtype: intmoves {0: [1, 3],1: [0, 2, 4],2: [1, 5],3: [0, 4],4: [1, 3, 5],5: [2, 4]}used set()cnt 0s .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 cntarr [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 1if len(new) len(back):front, back back, newelse:front newreturn -1
套用单词接龙模版直接双向 BFS 即可。 ◆ A* x BFS
import heapq
M, N 2, 3class Solution:def slidingPuzzle(self, board):def h(s):dist 0s2 123450i1 s.index(0)i2 s2.index(0)x1, y1 i1 % N, i1 // Nx2, y2 i2 % N, i2 // Ndist abs(x1 - x2) abs(y1 - y2)return distend_state 123450board 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 0heapq.heappush(q, (h(s) step, s, step))while q:sample heapq.heappop(q)state, step sample[1], sample[2]if state end_state:return stepnow 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/
