启发式搜索 - 有趣而神奇的 A* 算法

发表于   |     |   阅读次数

前言

在课堂上听老师讲了一个人工智能的基础小算法，感觉神奇而有趣，便自行研究一下。研究了几个小时，总算实现了。想写一篇博文来记录一下今天的学习经历，那么，就请有兴趣的各位跟我一起从零实现一个简单的A星寻路算法啦。

概述

  • 首先，需要有个基本概念：A*搜寻算法俗称“A星算法”。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。（启发式搜索）

几个要素

  • 是否相通的标记（标记有许多种方式，例如：0为通畅、1为障碍；或者把两两结点的线路保存下来，再去查该线路是否存在）
  • 一个父亲结点指针（处理结点时候，需要知道该结点的父节点）
  • OPEN 表（待检查的点，认为当前点为父亲结点，父亲结点也要保存，）
  • CLOSE 表（不再检查的点）
  • 一条公式：F = H + G
    F 为到终点的总耗费
    H 为网格上当前方格移动到终点的预估耗费（预估算法有很多种，例如：“曼哈顿法”：H = |行数| + |列数|、另外也可利用直线距离…）；
    G 为父亲结点移动到当前结点的预估移动耗费；

  • 现在，再来举个栗子，下面的步骤解析也会与之相结合：

    A*小栗子

    简单解释：

    - 图中有 A、B、C、D、E、F、G、H 8个结点（ A 为起点、E 为终点）
- 括号为当前结点到终点的预估值（由于预估算法的选择有许多，使用时需要根据实际情况选择，而我们现在优先学习A星算法的思路，因此这里直接给出预估值 - 即 H 值）
- 结点间的连线为相同直线，上面的数字代表线路的移动耗费值（即 G 值）
- 任务：利用A星算法计算出路线

算法步骤

  1. 设起点 A ，将 A 加入 OPEN 表
  2. 寻找相邻可达点，计算出其 F 值，并加入 OPEN 表；若相邻点已经在 Open 表中，则判断其是否需要更新 F 值；若相邻点已经在 Close 表中，则跳过该点
  3. 将原父亲结点（A 结点）从 OPEN 表中删除，把它加入到 CLOSE 表中
  4. 从 OPEN 表中选择一个 F值最小的，然后将它作为父亲结点，继续处理其相邻结点
  5. 只要 Open 表不为空，则循环执行上述2、3、4步骤，发现相邻点是终点，则跳出循环。
  6. 当 Open 表为空，还没有找到终点，则说明起点不可达到终点

Just show me the code ！

讲了那么多，理论知识总该要实践才行，建议大家先参考伪代码，理解好算法思路，自行尝试实现一番，再去看我那些半桶水的实现代码，一定会有更多收获的。

一段核心思路伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
while(OPEN!=NULL)
{
    从OPEN表中取f(n)最小的节点n;
    if(n节点==目标节点)
        break;
    for(当前节点n的每个子节点X)
    {
        计算f(X);
        if(XinOPEN)
            if(新的f(X)<OPEN中的f(X))
            {
                把n设置为X的父亲;
                更新OPEN表中的f(n);
            }
        if(XinCLOSE)
            continue;
        if(Xnotinboth)
        {
            把n设置为X的父亲;
            求f(X);
            并将X插入OPEN表中;//还没有排序
        }
    }//endfor
    将n节点插入CLOSE表中;
    按照f(n)将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}//endwhile(OPEN!=NULL)

我的 Java 实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package com.goo.astart;
/**
 *路径实体类
 * 
 * @author Goo
 * 
 */
public class Road {
	public String name;
	public int length;
	public Road(String name, int length) {
		this.name = name;
		this.length = length;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package com.goo.astart;
/**
 * 结点实体类
 * 
 * @author Goo
 * 
 */
public class NodeStruct {
	public NodeStruct(String nodeName, int estimate) {
		this.nodeName = nodeName;
		this.estimate = estimate;
	}
	/**
	 * 结点名称
	 */
	public String nodeName;
	/**
	 * 父亲结点
	 */
	public NodeStruct fatherNode = null;
	/**
	 * 总耗费
	 */
	public int weight = 0;
	/**
	 * 当前结点到终点的预估耗费
	 */
	public int estimate = 0;
	/**
	 * 父亲结点到当前结点的实际耗费
	 */
	public int practical = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
//Main.java
package com.goo.astart;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import javax.management.openmbean.OpenDataException;
import javax.xml.soap.Node;
/**
 * 含有主方法的主逻辑类
 * 
 * @author Goo
 * 
 */
public class Main {
	private static ArrayList<NodeStruct> dataList = new ArrayList<NodeStruct>();
	private static ArrayList<Road> roadList = new ArrayList<Road>();
	private static ArrayList<NodeStruct> openList = new ArrayList<NodeStruct>();
	private static ArrayList<NodeStruct> closeList = new ArrayList<NodeStruct>();
	private static NodeStruct startNode;
	private static NodeStruct endNode;
	private static final int HASFOUND = 10000;
	private static final int NOTFOUND = 20000;
	private static int stepCount = 0;
	public static void main(String[] args) {
		loadData();
		// 1、将起点加入Open表
		addToOpenList(startNode);
		// 2、搜索相邻路径？
		if (search() == HASFOUND) {
			System.out.println("路径搜索完成，成功找到最短路径");
		} else {
			System.out.println("路径搜索完成，没有可达路径");
		}
	}
	/**
	 * A星核心算法
	 * 
	 * @return
	 */
	private static int search() {
		// Open表不为空
		while (openList.size() != 0) {
			// 按照总耗费从小到大排序
			Collections.sort(openList, new Comparator<NodeStruct>() {
				public int compare(NodeStruct node1, NodeStruct node2) {
					return node1.weight - node2.weight;
				};
			});
			// 取最小结点作为父亲结点
			NodeStruct fatherNode = openList.get(0);
			stepCount++;
			System.out.println("步骤" + stepCount + ":" + fatherNode.nodeName
					+ " - 结点F值：" + fatherNode.weight);
			// 结点已找到
			if (fatherNode.equals(endNode)) {
				return HASFOUND;
			}
			// 寻找相邻路径
			for (int i = 0; i < dataList.size(); i++) {
				NodeStruct neighNode = dataList.get(i);
				String roadName = neighNode.nodeName + fatherNode.nodeName;
				String roadNameRev = fatherNode.nodeName + neighNode.nodeName;
				for (int j = 0; j < roadList.size(); j++) {
					Road tempRoad = roadList.get(j);
					// 找到相邻点
					if (roadName.equals(tempRoad.name)
							|| roadNameRev.equals(tempRoad.name)) {
						// 如果在Close表中，忽略
						if (closeList.contains(neighNode)) {
							continue;
						}
						else if (openList.contains(neighNode)) {
							// 如果在Open表中
							// 如果父亲结点到该结点耗费值更小，则更新耗费值
							if (tempRoad.length + neighNode.estimate < neighNode.weight) {
								neighNode.weight = tempRoad.length
										+ neighNode.estimate;
							}
						} else {
							// 两个表都没有（空白点）
							// 计算该点总耗费
							neighNode.weight = neighNode.estimate
									+ tempRoad.length;
							// 成功搜索路径，认为是相邻点，加入到Open表
							addToOpenList(neighNode);
						}
					}
				}
			}
			// 最后将父结点移除Open表，放入Close表
			removeFromOpen(fatherNode);
			addToCloseList(fatherNode);
		}
		return NOTFOUND;
	}
	/**
	 * 加载数据
	 */
	private static void loadData() {
		startNode = new NodeStruct("A", 15);
		startNode.weight = 15;
		endNode = new NodeStruct("E", 0);
		dataList.add(startNode);
		dataList.add(endNode);
		dataList.add(new NodeStruct("B", 14));
		dataList.add(new NodeStruct("C", 10));
		dataList.add(new NodeStruct("D", 2));
		dataList.add(new NodeStruct("F", 5));
		dataList.add(new NodeStruct("G", 9));
		dataList.add(new NodeStruct("H", 11));
		roadList.add(new Road("AB", 3));
		roadList.add(new Road("AH", 4));
		roadList.add(new Road("BH", 5));
		roadList.add(new Road("CG", 3));
		roadList.add(new Road("CD", 8));
		roadList.add(new Road("CB", 4));
		roadList.add(new Road("DG", 8));
		roadList.add(new Road("DF", 3));
		roadList.add(new Road("DE", 2));
		roadList.add(new Road("FG", 4));
		roadList.add(new Road("GH", 2));
	}
	/**
	 * 添加到 Open 表
	 * 
	 * @param node
	 */
	private static void addToOpenList(NodeStruct node) {
		openList.add(node);
	}
	/**
	 * 添加到 Close 表
	 * 
	 * @param node
	 */
	private static void addToCloseList(NodeStruct node) {
		closeList.add(node);
	}
	/**
	 * 从 Open 表移除
	 * 
	 * @param node
	 */
	private static void removeFromOpen(NodeStruct node) {
		openList.remove(node);
	}
	/**
	 * 从 Close 表移除
	 * 
	 * @param node
	 */
	private static void removeFromClose(NodeStruct node) {
		closeList.remove(node);
	}
}

总结

相信大家动手实现后，就会对A*算法有个基本的认识啦，以上代码通过了几个简单的样例，但不排除会隐藏着奇怪的 Bug 噢，或者是一段有待改进的代码，欢迎大家指点指点。

感谢您的阅读，希望文章对您有所帮助