A*算法
A*（念做：A Star）算法是一种很常用的路径查找和图形遍历算法，有较好的性能和准确度。
可参考这篇文章，详细的介绍了它与其他路径查找算法的区别。
A* 算法的重点在于计算节点的优先级函数f(n)=g(n)+h(n)。
f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。
g(n)是节点n距离起点的代价。
h(n)是节点n距离终点的预计代价，这也就是A* 算法的启发函数。
只要充分理解并掌握这一点，应用A* 算法也不在话下。
有向图实现
首先参考一下迷宫地图的A* 算法实现的详细代码，这套代码精练简洁，很适合初学者学习。
A* 算法能在网格中找到最短路径，同理也能应用在有向图上，寻找到代价最小的路径，话不多说，直接上代码。
定义有向图节点，每一个节点指向连接的节点作为该节点的子节点，每一个节点的位置以二维平面上的横纵坐标标识。
public class GNode {
private double x;
private double y;
private String value; //表示节点的值
private double FValue = 0; //F值
private double GValue = 0; //G值
private double HValue = 0; //H值
private List<GNode> CNode;//子节点
private GNode PNode; //父节点
public GNode(int x, int y, String value) {
super();
this.x = x;
this.y = y;
this.value = value;
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public double getFValue() {
return FValue;
}
public void setFValue(double FValue) {
this.FValue = FValue;
}
public double getGValue() {
return GValue;
}
public void setGValue(double GValue) {
this.GValue = GValue;
}
public double getHValue() {
return HValue;
}
public void setHValue(double HValue) {
this.HValue = HValue;
}
public List<GNode> getCNode() {
return CNode;
}
public void setCNode(List<GNode> CNode) {
this.CNode = CNode;
}
public GNode getPNode() {
return PNode;
}
public void setPNode(GNode PNode) {
this.PNode = PNode;
}
}
定义有向图数据结构。
public class DGraph {
private List<GNode> graph;//节点数组
private GNode startNode;//起点
private GNode endNode;//终点
public DGraph(List<GNode> graph, GNode startNode, GNode endNode) {
this.graph = graph;
this.startNode = startNode;
this.endNode = endNode;
}
//展示有向图
public void showGraph() {
int vertexNum = graph.size();
for (int i = 0; i < vertexNum; i++) {
GNode v = graph.get(i);
System.out.print(v.getValue() + "->");
if (v.getCNode() != null) {
for (int j = 0; j < v.getCNode().size(); j++) {
System.out.print(v.getCNode().get(j).getValue() + "->");
}
}
System.out.println("/");
}
}
public List<GNode> getGraph() {
return graph;
}
public void setGraph(List<GNode> graph) {
this.graph = graph;
}
public GNode getStartNode() {
return startNode;
}
public void setStartNode(GNode startNode) {
this.startNode = startNode;
}
public GNode getEndNode() {
return endNode;
}
public void setEndNode(GNode endNode) {
this.endNode = endNode;
}
}
在主函数中初始化有向图：
List<GNode> gNodes = new ArrayList<>();
GNode gNode1 = new GNode(1, 0, "A");
GNode gNode2 = new GNode(2, 1, "B");
GNode gNode3 = new GNode(3, 0, "C");
GNode gNode4 = new GNode(4, 1, "D");
GNode gNode5 = new GNode(5, 0, "E");
gNode1.setCNode(Arrays.asList(gNode2, gNode3));
gNode2.setCNode(Arrays.asList(gNode3));
gNode3.setCNode(Arrays.asList(gNode4, gNode5));
gNodes.add(gNode1);
gNodes.add(gNode2);
gNodes.add(gNode3);
gNodes.add(gNode4);
gNodes.add(gNode5);
DGraph dGraph = new DGraph(gNodes, gNode1, gNode4);
dGraph.showGraph();
运行，以邻接表格式展示有向图。
邻接表
A*算法实现，由于是在二维平面里寻找路径，所以两个节点的距离采用欧几里得距离，也就是直线距离，估价函数h(n)为当前节点和终点的直线距离，实际的距离一定是大于等于h值。
public class AStarGraph {
/**
* 使用ArrayList数组作为“开启列表”和“关闭列表”
*/
ArrayList<GNode> open = new ArrayList<>();
ArrayList<GNode> close = new ArrayList<>();
/**
* 获取两个节点的欧几里得距离
*/
public double getDistance(GNode node1, GNode node2) {
double dx = Math.abs(node1.getX() - node2.getX());
double dy = Math.abs(node1.getY() - node2.getY());
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 获取H值,采用欧几里得距离
*
* @param currentNode：当前节点
* @param endNode：终点
* @return
*/
public double getHValue(GNode currentNode, GNode endNode) {
return getDistance(currentNode, endNode);
}
/**
* 获取G值
*
* @param currentNode：当前节点
* @return
*/
public double getGValue(GNode currentNode) {
if (currentNode.getPNode() != null) {
return currentNode.getGValue() + getDistance(currentNode.getPNode(), currentNode);
}
return currentNode.getGValue();
}
/**
* 获取F值 ： G + H
*
* @param currentNode
* @return
*/
public double getFValue(GNode currentNode) {
return currentNode.getGValue() + currentNode.getHValue();
}
/**
* 将选中节点周围的节点添加进“开启列表”
*
* @param node
*/
public void inOpen(GNode node, DGraph graph) {
if (node.getCNode() != null) {
List<GNode> neighbours = node.getCNode();
for (int i = 0; i < neighbours.size(); i++) {
GNode m = neighbours.get(i);
if (!open.contains(m)) {
m.setPNode(node);
m.setHValue(getHValue(m, graph.getEndNode()));
m.setGValue(getGValue(m));
m.setFValue(getFValue(m));
open.add(m);
}
}
}
}
/**
* 将节点添加进”关闭列表“
*
* @param node
* @param open
*/
public void inClose(GNode node, ArrayList<GNode> open) {
if (open.contains(node)) {
open.remove(node);
close.add(node);
}
}
/**
* 使用冒泡排序将开启列表中的节点按F值从小到大排序
*
* @param arr
*/
public void sort(ArrayList<GNode> arr) {
for (int i = 0; i < arr.size() - 1; i++) {
for (int j = i + 1; j < arr.size(); j++) {
if (arr.get(i).getFValue() > arr.get(j).getFValue()) {
GNode tmp;
tmp = arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, tmp);
}
}
}
}
/**
* 将路径标记出来
*
* @param arr
* @param graph
*/
public void showPath(ArrayList<GNode> arr, DGraph graph) {
if (arr.size() > 0) {
GNode node = graph.getEndNode();
while (!(node.getX() == graph.getStartNode().getX() && node.getY() == graph.getStartNode().getY())) {
System.out.print(node.getValue() + "->");
node = node.getPNode();
}
}
System.out.println(graph.getStartNode().getValue());
}
public void search(DGraph graph) {
//对起点即起点周围的节点进行操作
inOpen(graph.getStartNode(), graph);
close.add(graph.getStartNode());
graph.getStartNode().setPNode(graph.getStartNode().getPNode());
sort(open);
//重复步骤
do {
inOpen(open.get(0), graph);
inClose(open.get(0), open);
sort(open);
}
while (!open.contains(graph.getEndNode()));
//知道开启列表中包含终点时，循环退出
inClose(graph.getEndNode(), open);
showPath(close, graph);
}
}
调用A*算法即可找到最短路径。
AStarGraph aStarGraph = new AStarGraph();
aStarGraph.search(dGraph);
展示路径
