原文:算法起步之A星算法
用途：
寻找最短路径，优于bfs跟dfs
描述：
基本描述是，在深度优先搜索的基础上，增加了一个启发式算法，在选择节点的过程中，不是盲目选择，而是有目的的选的，F=G+H,f(n)=g(n)+h(n)
g(n)是当前节点到开始节点的花费h(n)是当前节点到结束节点的花费f(n)是衡量一个衡量标准
最核心的是h(n)的估算，这里用到了启发式算法，且h(n)=<h*(n) （h*(n)为实际问题的代价值）。曼哈顿（manhattan）估价函数曼哈顿方法，它计算从当前格到目的格之间水平和垂直的方格的数量总和，忽略对角线方向，然后把结果乘以10。在选择节点时，根据节点的f(n)的大小进行选择，总是选择最小的。这样会有两个队列，一个open队列用来存储所预备选择节点，close队列用来存储已经走过的节点，open队列是一个优先队列，每次从open队列中取f值最小的节点，检查后将节点放到close里。并把关联节点放到open队列中，这样一直循环到终点节点加入到open列表中时。
资料：
http://www.java3z.com/cwbwebhome/article/article2/2825.html的flash做的很形象
http://www.cppblog.com/mythit/archive/2009/04/19/80492.aspx讲的很详细
http://developer.51cto.com/art/201112/307973.htmjava版代码
代码：
package com.langsin.gsc.acm.astar;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* A*寻路算法
* 地图中1表示可以通过，0表示不能通过
* 当结束点加到open队列中时查找结束
* gh值的设定问题。
*/
public classAstar {
// 地图
private int[][] map;
// 行
private int row;
// 列
private int colum;
// 水平或竖直方向的花费
private int COST_ZHI=10;
// 对角线方向的花费
private int COSR_XIE=14;
// open列表
private List<Node> open;
// close列表
private List<Node> close;
// 开始节点
private Node beginNode;
// 结束节点
private Node endNode;
// 结构节点
private Node resultNode=null;
/**
* 测试方法
* @param args
*/
public static void main(String[] args) {
int[][] map = new int[][] {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{1, 1, 1, 1, 0, 1, 1, 1, 1, 1 },
{1, 1, 1, 1, 0, 1, 1, 1, 1, 1 }
};
Astarastar=newAstar(map, 6, 10);
astar.search(0,0, 5, 9);
Noderesult=astar.getResultNode();
while(result.getParentnode()!=null){
map[result.getX()][result.getY()]=2;
result=result.getParentnode();
}
map[result.getX()][result.getY()]=2; for (int i = 0; i <6; i++) {
for (int j = 0; j < 10; j++){
System.out.print(" "+map[i][j]);
}
System.out.println();
}
}
/**
* 初始化地图长宽还有open跟close队列
* @param map
* @param row
* @param colum
*/
public Astar(int[][] map,int row,int colum){
this.map=map;
this.row=row;
this.colum=colum;
open=newArrayList<Node>();
close=newArrayList<Node>();
}
/**
* 开始节点的坐标跟终点节点的坐标
* @param x1
* @param y1
* @param x2
* @param y2
*/
public void search(int x1,int y1,int x2,int y2) {
// 如果在节点外直接返回
if (x1<0||x1>=row||y1<0||y1>colum||x2<0||x2>=row||y2<0||y2>colum) {
return;
}
// 如果无法通过直接返回
if (map[x1][y1]==0||map[x2][y2]==0) {
return;
}
beginNode=new Node(x1, y1, null);
endNode=new Node(x2, y2, null);
// 开始按方向搜索
searchnode(beginNode, endNode);
}
/**
* 分八个方向开始检查结点
* @param bNode
* @param eNode
*/
private void searchnode(NodebNode,Node eNode){
// 将开始节点加入到open中
open.add(bNode);
// 当open列表中有节点时就循环
while (open.size()>0) {
// 取出第一个节点设置成当前节点开始检查他的八个方向
Nodenownode=open.get(0);
// 如果是终点则推出循环
if (nownode.getX()==endNode.getX()&&nownode.getY()==endNode.getY()) {
// 将这个节点设置成结果节点
resultNode=nownode;
break;
}
// 向上
if(nownode.getX()-1>=0) {
checkNode(nownode.getX()-1,nownode.getY(), nownode,COST_ZHI);
}
// 向下
if (nownode.getX()+1<row) {
checkNode(nownode.getX()+1,nownode.getY(), nownode, COST_ZHI);
}
// 向左
if(nownode.getY()-1>=0) {
checkNode(nownode.getX(),nownode.getY()-1, nownode, COST_ZHI);
}
// 向右
if (nownode.getY()+1<colum) {
checkNode(nownode.getX(), nownode.getY()+1,nownode, COST_ZHI);
}
// 左上
if(nownode.getX()-1>=0&&nownode.getY()-1>=0) {
checkNode(nownode.getX()-1,nownode.getY()-1, nownode, COSR_XIE);
}
// 右上
if(nownode.getX()-1>=0&&nownode.getY()+1<colum) {
checkNode(nownode.getX()-1,nownode.getY()+1, nownode, COSR_XIE);
}
// 左下
if (nownode.getX()+1<row&&nownode.getY()-1>=0){
checkNode(nownode.getX()+1,nownode.getY()-1, nownode, COSR_XIE);
}
// 右下
if (nownode.getX()+1<row&&nownode.getY()+1<colum) {
checkNode(nownode.getX()+1,nownode.getY()+1, nownode, COSR_XIE);
}
// 将open列表中的第一个取出放入到close列表中
close.add(open.remove(0));
// 对open列表进行排序
Collections.sort(open, new nodecompare());
} }
/**
* 检查每一个结点
* @param x
* @param y
* @param parentNode
* @param cost
*/
private void checkNode(int x,int y,Node parentNode,int cost){
// 如果无法通过则返回
if (map[x][y]==0) {
return ;
}
// 如果在close中有则返回
if (checklist(close, x, y)!=-1) {
return;
}
// 建立这个结点
Nodenode=newNode(x, y, parentNode);
// 计算他的fgh值
setFGH(node,cost, endNode);
int index=-1;
// 如果open中有,若f值小则更新他否则不添加.没有的话则添加这个结点
if ((index=checklist(open, x, y))!=-1) {
if (node.getF()<open.get(index).getF()) {
open.set(index, node);
}
}else {
open.add(node);
}
} /**
* 计算FGH值
* @param node
*/
private void setFGH(Node node,int cost,Node eNode){ if (node.getParentnode()!=null) {
node.setG(node.getParentnode().getG()+cost);
}else {
node.setG(cost);
}
// H值的一种计算方法，也可以采用其他方法 曼哈顿（manhattan）估价函数
node.setH((Math.abs(node.getX()-eNode.getX())+Math.abs(node.getY()-eNode.getY()))*10);
node.setF(node.getG()+node.getH()); }
/**
* 检查列表中是否已经有该结点
* @param list
* @param x
* @param y
* @return
*/
private intchecklist(List<Node> list,int x,inty){
int key=-1;
for (int i = 0; i <list.size(); i++) {
if(list.get(i).getX()==x&&list.get(i).getY()==y) {
key=i;
break;
}
}
return key;
}
/**
* 放回结果路径（链表）
* @return
*/
public Node getResultNode(){
return resultNode;
}
} /**
* 节点类。主要包括xy坐标父节点 f=g+h
*
*/
class Node{
// 坐标xy
private int x;
private int y;
// 父节点
private Node parentnode;
// F=G+H
private int g;
private int h;
private int f;
// 构造函数
public Node(int x, int y, Node parentnode) {
super();
this.x = x;
this.y = y;
this.parentnode = parentnode;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public Node getParentnode() {
return parentnode;
}
public void setParentnode(Nodeparentnode) {
this.parentnode = parentnode;
}
public int getG() {
return g;
}
public void setG(int g) {
this.g = g;
}
public int getH() {
return h;
}
public void setH(int h) {
this.h = h;
}
public int getF() {
return f;
}
public void setF(int f) {
this.f = f;
}
}
/**
* 比较器用来给open队列排序
*/
class nodecompare implements Comparator<Node>{
@Override
public int compare(Node o1, Nodeo2) {
return o1.getF()-o2.getF();
}
}