启发式搜索的实现,特性

admin 管理员组

文章数量: 887021

启发式搜索的实现,特性

启发式搜索Heuristic Search(A*算法)

基于BFS代码

def BFS(graph, start, end):queue =[]queue.append([start])while queue:node = queue.pop() # can we add more intelligence here?visited.add(node)process(node)nodes = generate_related_nodes(node)queue.push(nodes)

A* search模板

# Python
def AstarSearch(graph, start, end):pq = collections.priority_queue() # 优先级 —> 估价函数pq.append([start]) visited.add(start)while pq: node = pq.pop() # can we add more intelligence here ?visited.add(node)process(node) nodes = generate_related_nodes(node) unvisited = [node for node in nodes if node not in visited]pq.push(unvisited)

//Javapublic class AStar{public final static int BAR = 1; // 障碍值public final static int PATH = 2; // 路径public final static int DIRECT_VALUE = 10; // 横竖移动代价public final static int OBLIQUE_VALUE = 14; // 斜移动代价Queue<Node> openList = new PriorityQueue<Node>(); // 优先队列(升序)List<Node> closeList = new ArrayList<Node>();/*** 开始算法*/public void start(MapInfo mapInfo){if(mapInfo==null) return;// cleanopenList.clear();closeList.clear();// 开始搜索openList.add(mapInfo.start);moveNodes(mapInfo);}/*** 移动当前结点*/private void moveNodes(MapInfo mapInfo){while (!openList.isEmpty()){Node current = openList.poll();closeList.add(current);addNeighborNodeInOpen(mapInfo,current);if (isCoordInClose(mapInfo.end.coord)){drawPath(mapInfo.maps, mapInfo.end);break;}}}/*** 在二维数组中绘制路径*/private void drawPath(int[][] maps, Node end){if(end==null||maps==null) return;System.out.println("总代价：" + end.G);while (end != null){Coord c = end.coord;maps[c.y][c.x] = PATH;end = end.parent;}}/*** 添加所有邻结点到open表*/private void addNeighborNodeInOpen(MapInfo mapInfo,Node current){int x = current.coord.x;int y = current.coord.y;// 左addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);// 上addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);// 右addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);// 下addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);// 左上addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);// 右上addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);// 右下addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);// 左下addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);}/*** 添加一个邻结点到open表*/private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value){if (canAddNodeToOpen(mapInfo,x, y)){Node end=mapInfo.end;Coord coord = new Coord(x, y);int G = current.G + value; // 计算邻结点的G值Node child = findNodeInOpen(coord);if (child == null){int H=calcH(end.coord,coord); // 计算H值if(isEndNode(end.coord,coord)){child=end;child.parent=current;child.G=G;child.H=H;}else{child = new Node(coord, current, G, H);}openList.add(child);}else if (child.G > G){child.G = G;child.parent = current;openList.add(child);}}}/*** 从Open列表中查找结点*/private Node findNodeInOpen(Coord coord){if (coord == null || openList.isEmpty()) return null;for (Node node : openList){if (node.coord.equals(coord)){return node;}}return null;}/*** 计算H的估值：“曼哈顿”法，坐标分别取差值相加*/private int calcH(Coord end,Coord coord){return Math.abs(end.x - coord.x)+ Math.abs(end.y - coord.y);}/*** 判断结点是否是最终结点*/private boolean isEndNode(Coord end,Coord coord){return coord != null && end.equals(coord);}/*** 判断结点能否放入Open列表*/private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y){// 是否在地图中if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) return false;// 判断是否是不可通过的结点if (mapInfo.maps[y][x] == BAR) return false;// 判断结点是否存在close表if (isCoordInClose(x, y)) return false;return true;}/*** 判断坐标是否在close表中*/private boolean isCoordInClose(Coord coord){return coord!=null&&isCoordInClose(coord.x, coord.y);}/*** 判断坐标是否在close表中*/private boolean isCoordInClose(int x, int y){if (closeList.isEmpty()) return false;for (Node node : closeList){if (node.coord.x == x && node.coord.y == y){return true;}}return false;}}

估价函数

启发式函数:h(n),它用来评价哪些结点最有希望的是一个我们要找的结点.
h(n)会返回一个非负实数,也可以认为是从结点n的目标结点路径的估计成本
启发式函数是一种告知搜索方向的方法,它提供了一种明智的方法来猜测哪个邻居结点导向一个目标
优先级最高,最先找,到最后发现它会把所有可能的结点都找一遍,只不过找的顺序是优先级更高的结点
这个值越大越优秀越可能会导致最后的结果

1091. 二进制矩阵中的最短路径

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, …, C_k 组成：
相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。
示例 1：
输入：[[0,1],[1,0]]
输出：2
示例 2：
输入：[[0,0,0],[1,1,0],[1,1,0]]
输出：4
提示：
1 <= grid.length == grid[0].length <= 100
grid[i][j] 为 0 或 1

整体来说的意思是N*N的图,0是空地,1是阻碍物,从左上走到右下,走过的点必须是空地,不能走1阻碍物
图是八联通,也可以走对角线,问从左上走到右下,最少需要走多少路
二进制矩阵中的最短路径的 A* 解法
8 puzzles 解法比较
BFS代码

class Solution:def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:q, n = [(0, 0, 2)], len(grid)  # [(0, 0, 2)]指的是起点,终点和步数if grid[0][0] or grid[-1][-1]: # 如果左上或右下为1,就说明被石头挡住了return -1elif n <= 2:return n#BFS starts 根据q中的初始值,不断的进行BFS	for i, j, d in q:#循环q取到当前的结点就是current node:i, j; distance = d#四联通就是上下左右, 八联通是上下左右斜上斜下斜左斜右for x, y in [(i - 1, j - 1), (i - 1, j), (i - 1, j + 1),(i, j - 1), (i, j + 1),(i + 1, j - 1), (i + 1, j),(i + 1, j + 1)];#判断新生成的x,y必须是在这个坐标系里面,不能凸出去,#同时的话要判断是不是已经到终点了if 0 <= x < n and 0 <= y < n and not grid[x][y]:if x == n - 1 and y == n - 1:return d#不然的话把下一个候选者放到q中q += [(x, y, d + 1)]#grid[x][y] = 1表示这个点已经被看过,就赋值为1,不要再走回来grid[x][y] = 1return -1

A *search
估计函数 当走到任何中间一个点,就是这个点距离你的终点坐标差的绝对值的和
也叫做曼哈顿距离,距离越近这个点越好,越先扩散距离右下角的点近的点

773. 滑动谜题

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：
输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入：board = [[3,2,4],[1,5,0]]
输出：14
提示：
board 是一个如上所述的 2 x 3 的数组.
board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

#方向变换向量 类似四联通或八联通图里面的向量
moves = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4],
4: [1, 3, 5],
5: [2, 4]
}
0: [1, 3], 表示当0在第0个位置的时候,它可以交换的位置就是第1个位置和第3个位置,
因为0这个位置是在左上角,左上角可以交换的位置就是它的右边就是index为1的位置
或者下面的位置就是4的位置,当把它放到1维字符串中,4的index是3,同理
1: [0, 2, 4]表示当1在第1个位置的时候,对应的就是左边是0,右边是2,下边是4,以此类推
如果不这么写,就要写6个if,这里的Index是指在字符串以为数组里面的下标,所以是012345这么一个范围
这里为了方便存储,最后会把整个数字放在一个字符里面
把所有数字变成字符,存成一个一维的字符数组,
胜利的状态就是123450

class Solution(object):def slidingPuzzle(self, board):#used指已经访问过的结点used = set()cnt = 0#将2*3的board换成是一维的字符数组 board = [[1,2,3],[5,4,0]]# s = "123540"s = "".join(str(c) for row in board for c in row)#一开始起点s就是board的初始状态,终点就是123450,q = [s]#只要q不为空,new等于下次新的要扩散的结点,#while q:  new = []for s in q:  # 从q中把所有的s取出来used.add(s) # 先把s加到used中去,if s == "123450"return cnt   #变成了目标状态,已经找到,cnt表示移了多少步arr = [c for c in s] # 将s进行进一步扩散,s中的每一个字符组成一个arr#开始移动0,因为只能把0和它上下左右相邻的元素进行交换zero_index = s.index('0')# 0的位置放在moves里面去之后,后面就是可以进行交换的坐标叫movefor move in moves[zero_index]:#首先复制了一份出来,然后将Move和zero_index进行交换new_arr = arr[:]new_arr[zero_index], new_arr[move] = new_arr[move], new_arr[zero_index]#交换完之后,将新数字组成字符串new_s = "".join(new_arr)if new_s not in used: #如果new_s没有被用就加到new中new.append(new_s)cnt += 1q = newreturn -1					

class Solution:def slidingPuzzle(self, board: List[List[int]]) -> int:board = board[0] + board[1] #把board连起来变一维#每个位置的0可以交换的位置moves = [(1, 3),(0, 2, 4),(1, 5),(0, 4),(1, 3, 5),(2, 4)]# bfs队列和已访问状态记录, tuple二元祖就是上面的,#把q中的元素,即放了board,也放了0的位置,这样就不用再后面取了,直接把0的位置放在q中#同时还把distance,最后0肯定是它挪动的步数也放在q里面了q, visited = [(tuple(board), board.index(0), 0)], set()while q: #BFS开始state, now, step = q.pop(0):# 分别代表当前状态,0的当前位置和当前步数if state == (1, 2, 3, 4, 5, 0): #找到了return stepfor next in moves[now]: #遍历所有可交换位置_state = list(state)_state[next], _state[now] = _state[now], _state[next] #交换位置_state = tuple(_state)if _state not in visited: #确认魏访问q.append((_state, next, step+1))visited.add(state)return -1

本文标签： 启发式搜索的实现 特性