不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

A* 算法

A* 算法也称为启发式搜索算法,A* 算法通过下面的公式来确定下一个要选择的结点:
$$ f(n)=g(n)+h(n)$$

f(n) 表示选择该结点的代价
g(n) 表示是节点n距离起点的代价
h(n) 是节点n距离终点的预计代价,这也就是A* 算法的启发函数。
当每个结点的f(n)都想等时,变成广度优先算法;当h(n)为0时,变成了Dijkstra’s算法;当g(n)=0时变成了最佳优先搜索算法(每次朝着终点前进,但是有障碍的话就不是最佳答案)。

A* 算法在运算过程中,每次从优先队列中选取f(n)值最小(优先级最高)的节点作为下一个待遍历的节点。

启发式函数h(n)常见的选择:

  • 图是网格形式:
    • 如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离。
    • 如果图形中允许朝八个方向移动,则可以使用对角距离。
    • 如果图形中允许朝任何方向移动,则可以使用欧几里得距离。
# D是指两个相邻节点之间的移动代价,通常是一个固定的常数。
# 曼哈顿距离
function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy)

# 对角距离
# D2指的是两个斜着相邻节点之间的移动代价。如果所有节点都正方形,则其值就是$\sqrt{2}D$
function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

# 欧几里得距离
function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * sqrt(dx * dx + dy * dy)

实战

力扣752,打开转盘锁

/**
* 从字符串“0000” 到目标字符串“0202”, 
* 启发函数h(n)是从当前字符串到目标字符串的最小转动次数
* g(n) 为从字符“0000” 到当前字符所转动的次数。
**/
class Solution {
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }
		HashSet<String> visited=new HashSet<>();
		for(String de:deadends){
			visited.add(de);
		}
        if(visited.contains("0000")) return -1;

        // 优先队列,每次从优先队列中选取f(n)值最小的点
        PriorityQueue<AStar> queue = new PriorityQueue<AStar>((a, b) -> a.f - b.f);
        queue.offer(new AStar("0000", target, 0));

		while(!queue.isEmpty()){  
            AStar node = queue.poll();
            if(node.status.equals(target)) return node.g;
            //  依次转锁
            for(int ii=0;ii<4;ii++){
                String up=upLock(node.status,ii);// 向上转动
                if(!visited.contains(up)){
                    queue.offer(new AStar(up, target, node.g+1));
                    visited.add(up);
                }
                String down=downLock(node.status,ii);
                if(!visited.contains(down)){
                    queue.offer(new AStar(down, target, node.g+1));
                    visited.add(down);
                }
            }			
		}
		return -1;
	}
	public String upLock(String s, int j){
		char[] chars=s.toCharArray();
		if(chars[j]=='0'){
			chars[j]='9';
		}else{
			chars[j]-=1;
		}
		return new String(chars);
	}
	public String downLock(String s, int j){
		char[] chars=s.toCharArray();
		if(chars[j]=='9'){
			chars[j]='0';
		}else{
			chars[j]+=1;
		}
		return new String(chars);
	}
}

class AStar {
    String status;
    int f, g, h;
    // 开始的status,目标的target,g为开始结点到status的步数
    public AStar(String status, String target, int g) {
        this.status = status;
        this.g = g;
        this.h = getH(status, target);
        this.f = this.g + this.h;
    }

    // 计算启发函数h
    public static int getH(String status, String target) {
        int ret = 0;
        for (int i = 0; i < 4; ++i) {
            int dist = Math.abs(status.charAt(i) - target.charAt(i));
            ret += Math.min(dist, 10 - dist);
        }
        return ret;
    }
}

15数码问题

在一个4 * 4 的棋盘上面有15个数,一个空格,给定初始值和目标值,求移动多少次到达目标状态?
进阶:字节笔试最后一题:给定两个空格,求移动多少次。
一个空格的情况

//定义状态结点,并计算代价函数,用于优先队列里面进行排序
class StatusNode{
	int[][] status;// 存储状态的二维矩阵
	int zero_x,zero_y;// 0的坐标位置
	int n,m;// 表示行 和列的位置
	int f,g,h;// 分别表示代价函数,开始结点到当前结点的代价,当前结点到目标结点预估代价
    
	public StatusNode(int[][] status,int[][] target,int g,int zero_x,int zero_y){
		this.n=status.length;
		this.m=status[0].length;
		this.status=new int[n][m];
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				this.status[i][j]=status[i][j];
			}
		}
		this.g = g;
		this.h = getHWithMH(status, target);
		// this.h = getHWithDiff(status, target);
		this.f = this.g + this.h;
		this.zero_x=zero_x;
		this.zero_y=zero_y;

	}

	/**
	 * 曼哈顿距离
	 * @param status
	 * @param target
	 * @return
	 */
	public int getHWithMH(int[][] status, int[][] target){
		int ans=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				//跳过0 和想等的元素
				if(status[i][j] != 0 && status[i][j]!=target[i][j]){
					//需要两个元素的位置,其实也就是需要 目标状态target中,当前元素应该所处的位置
					int pos=getPosition(target,status[i][j]);
					int dx = Math.abs(pos/n -i);
					int dy = Math.abs(pos%n -j);
					ans+=dx+dy;
				}
			}
		}
		return ans;
	}

	/**
	 * 不再位的元素数量
	 * @param status
	 * @param target
	 * @return
	 */
	public int getHWithDiff(int[][] status, int[][] target){
		int ans=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				//跳过0 和想等的元素
				if( status[i][j]!=target[i][j]){
					ans++;
				}
			}
		}
		return ans;
	}
    // 获取target中num的位置
	public int getPosition(int[][] target,int num){
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(target[i][j]==num) return i*n+j;
			}
		}
		return -1;
	}
    public String toString() {
		return Arrays.deepToString(status);
	}
}

// 主函数
public class AStarAlgorithm {
	/**
	 * 15数码游戏里面,只有一个空白,使用A*算法:
	 * 启发式函数为:不在位数码个数 / 不在位数码与其目标位置之间距离的总和
	 * g(n) :空格走的步数(结点深度)
	 * @return
	 */
	public static int withOneNULL(int[][] source,int[][] target){
		int zeroX=0,zeroY=0;// 定义0开始的位置
		int n=source.length,m=source[0].length;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(source[i][j]==0){
					zeroX=i;zeroY=j;break;
				}
			}
		}
        HashMap<String, LinkedList<String>> map=new HashMap<>();// 存放访问过的路径
		int[][] directs=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};// 定义上下左右

		// open 表存储需要访问的结点,close存放已经访问过的结点
		PriorityQueue<StatusNode> open = new PriorityQueue<StatusNode>((a, b) -> a.f - b.f);
		HashSet<StatusNode> close=new HashSet<>();
		StatusNode startNode = new StatusNode(source, target, 0, zeroX, zeroY);
		open.offer(startNode);
		LinkedList<String> objects = new LinkedList<>();
		objects.add(startNode.toString());
		map.put(startNode.toString(),objects);

		while(!open.isEmpty()){
			StatusNode node = open.poll();
			close.add(node);
           
            zeroX=node.zero_x;
			zeroY=node.zero_y;
			for(int[] direct:directs){// 上下左右方向
				// 方向不合法
				if(zeroX+direct[0]>=n || zeroX+direct[0]<0 || zeroY+direct[1]>=m || zeroY+direct[1]<0) continue;
				
                int[][] temp=deepCopy(node.status);// 获取到深克隆状态的结构,

				// 开始移动
				int newZeroX=zeroX+direct[0];
				int newZeroY=zeroY+direct[1];
				int t=temp[zeroX][zeroY];
				temp[zeroX][zeroY]=temp[newZeroX][newZeroY];
				temp[newZeroX][newZeroY]=t;

				StatusNode newNode=new StatusNode(temp,target,node.g+1,newZeroX,newZeroY);
				if(close.contains(newNode)) continue;
				open.offer(newNode);
                // 保存访问过的路径
                LinkedList<String> link = new LinkedList<>(map.get(node.toString()));
				link.addFirst(newNode.toString());
				map.put(newNode.toString(),link);
				if(isEqual(newNode.status,target)){
					String s = link.stream().reduce((a, b) -> b + "; ---->" + a).toString();
					System.out.println("走的路径是"+s);
					return newNode.g;
				}
			}

		}
		return 0;
	}
	public static boolean isEqual(int[][] source,int[][] target){
		for(int i=0;i<source.length;i++){
			if(!Arrays.equals(source[i],target[i])) return  false;
		}
		return true;
	}
	public static int[][]  deepCopy(int[][] source){
		int[][] target=new int[source.length][source[0].length];
		for(int i=0;i<source.length;i++){
			target[i]=source[i].clone();
		}
		return target;
	}
	public static void main(String[] args) {
		// 16数码
		int[][] target= {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 0}}; // 目标状态(二维数组表示)
		int[][] source= {{5, 1, 2, 4}, {9,6,3,8}, {13,15,10,11}, {14,0,7,12}}; // 初始状态
		System.out.println("16数码花费的时间是"+withOneNULL(source,target));
		// 8数码
		int[][] goalMatrix1= {{2,8,3}, {1,6,4}, {7,0,5}}; // 目标状态(二维数组表示)
		int[][] init1 = {{1,2,3}, {8,0,4}, {7, 6,5}}; // 初始状态
		System.out.println("8数码花费的时间是"+withOneNULL(goalMatrix1,init1));

	}
}

进阶:两个空格的情况

Reference

寻址算法介绍

推荐阅读,介绍了从广度优先 到 Dijkstra’s 到 A* 的改进。并给出了算法的可视化展示

你应该用哪种算法在游戏地图上寻找路径?

  • 如果你想找到所有地点之间的路径,可以使用广度优先搜索或Dijkstra算法。
    • 如果移动成本相同,则使用广度优先搜索;
    • 如果移动成本不同,使用Dijkstra算法。
  • 如果您想找到一个位置的路径,或几个目标中最近的路径,请使用贪婪的最佳优先搜索或A*。大多数情况下喜欢A*。当你想使用贪婪的最佳优先搜索时,可以考虑使用带有“不可接受”启发式的* 搜索。

阿里技术:路径规划之 A* 算法


目录