アルゴリズムスタートのA星アルゴリズム
9263 ワード
原文:
アルゴリズムスタートのA星アルゴリズム
用途:
最短経路を探して、bfsとdfsより優れています
説明:
基本的な記述は,深さ優先探索に基づいて,ノードを選択する過程で盲目的に選択するのではなく,目的のある選択を行う啓発アルゴリズムを追加し,F=G+H,f(n)=g(n)+h(n)
g(n)は、現在のノードから開始ノードまでの費用h(n)は、現在のノードから終了ノードまでの費用f(n)であり、測定基準である
最も核心的なのはh(n)の推定であり,ここでは啓発アルゴリズムが用いられ,h(n)=資料:
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.htm java版コード
コード:
アルゴリズムスタートのA星アルゴリズム
用途:
最短経路を探して、bfsとdfsより優れています
説明:
基本的な記述は,深さ優先探索に基づいて,ノードを選択する過程で盲目的に選択するのではなく,目的のある選択を行う啓発アルゴリズムを追加し,F=G+H,f(n)=g(n)+h(n)
g(n)は、現在のノードから開始ノードまでの費用h(n)は、現在のノードから終了ノードまでの費用f(n)であり、測定基準である
最も核心的なのはh(n)の推定であり,ここでは啓発アルゴリズムが用いられ,h(n)=
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.htm java版コード
コード:
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();
}
}