A星アルゴリズム

以前に作ったプロジェクトは、今になって記録されました.プロジェクトには、ユーザーが地図の上で起点、終点を選択する機能があり、地図の上で最も短いパスを探して地図に表示する必要があります.
ルックアップには2つの比較的一般的なアルゴリズムがあり、1つのディジェスト(Dijkstra)アルゴリズム、ディジェストラ(Dijkstra)アルゴリズムは典型的な最短経路アルゴリズムであり、1つのノードから他のノードへの最短経路を計算するために使用される.その主な特徴は,開始点を中心として外側に階層的に拡張(広さ優先探索思想)し,終点まで拡張することである.広さ優先のアルゴリズムなので、効率が低くなります.もう1つはA星アルゴリズムで、それは啓発的な代価関数に基づいて、啓発的な関数は応用とゲームの中でとても役に立ちます.速度と精度の間で折りたたみを取ると、プログラムがより速く実行されます.
次に、私が実装したコードを示します.

package com.heng.test.map;

import java.util.*;

/**
 * A*  
 * @author    
 *
 */
public class AStar {
	
	private int[][] map;//   (0    1    )
	private List<Node> openList;//     
	private List<Node> closeList;//     
	private final int COST_STRAIGHT = 10;//                 
	private final int COST_DIAGONAL = 14;//           
	private int row;//  
	private int column;//  
	
	public AStar(int[][] map, int row, int column) {
		this.map = map;
		this.row = row;// 
		this.column = column;// 
		openList = new ArrayList<Node>();//       
		closeList = new ArrayList<Node>();//       
	}

	/**
	 *      
	 * @param x1	  x   
	 * @param y1	  y   
	 * @param x2	  x   
	 * @param y2	  y   
	 * @return （-1：  ，0：   ，1：   ）
	 */
	public int search(int x1, int y1, int x2, int y2) {
		//      
		if (x1 < 0 || x1 >= row || x2 < 0 || x2 >= row || y1 < 0
				|| y1 >= column || y2 < 0 || y2 >= column) {
			return -1;
		}
		//      
		if (map[x1][y1] == 1 || map[x2][y2] == 1) {
			return -1;
		}

		Node sNode = new Node(x1, y1, null);//  
		Node eNode = new Node(x2, y2, null);//  
		openList.add(sNode);
		List<Node> resultList = search(sNode, eNode);
		if (resultList.size() == 0) {
			return 0;
		}
		for (Node node : resultList) {
			map[node.getX()][node.getY()] = 2;
		}
		return 1;
	}

	/**
	 *       
	 * @param sNode    
	 * @param eNode    
	 * @return               
	 */
	private List<Node> search(Node sNode, Node eNode) {
		List<Node> resultList = new ArrayList<Node>();
		boolean isFind = false;
		Node node = null;
		while (openList.size() > 0) {
			// System.out.println(openList);
			//          F ，         F    
			node = openList.get(0);
			//          
			if (node.getX() == eNode.getX() && node.getY() == eNode.getY()) {
				isFind = true;
				System.out.println("------    ------");
				break;
			}
			//  
			if ((node.getY() - 1) >= 0) {
				checkPath(node.getX(), node.getY() - 1, node, eNode,
						COST_STRAIGHT);
			}
			//  
			if ((node.getY() + 1) < column) {
				checkPath(node.getX(), node.getY() + 1, node, eNode,
						COST_STRAIGHT);
			}
			//  
			if ((node.getX() - 1) >= 0) {
				checkPath(node.getX() - 1, node.getY(), node, eNode,
						COST_STRAIGHT);
			}
			//  
			if ((node.getX() + 1) < row) {
				checkPath(node.getX() + 1, node.getY(), node, eNode,
						COST_STRAIGHT);
			}
			//   
			if ((node.getX() - 1) >= 0 && (node.getY() - 1) >= 0) {
				checkPath(node.getX() - 1, node.getY() - 1, node, eNode,
						COST_DIAGONAL);
			}
			//   
			if ((node.getX() - 1) >= 0 && (node.getY() + 1) < column) {
				checkPath(node.getX() - 1, node.getY() + 1, node, eNode,
						COST_DIAGONAL);
			}
			//   
			if ((node.getX() + 1) < row && (node.getY() - 1) >= 0) {
				checkPath(node.getX() + 1, node.getY() - 1, node, eNode,
						COST_DIAGONAL);
			}
			//   
			if ((node.getX() + 1) < row && (node.getY() + 1) < column) {
				checkPath(node.getX() + 1, node.getY() + 1, node, eNode,
						COST_DIAGONAL);
			}
			//         
			//         
			closeList.add(openList.remove(0));
			//        ， F         
			Collections.sort(openList, new NodeFComparator());
			// System.out.println(openList);
		}
		if (isFind) {
			System.out.println("node = "+node.getParentNode());
			getPath(resultList, node);
		}
		return resultList;
	}

	/**
	 *          
	 * @param x
	 * @param y
	 * @param parentNode
	 * @param eNode
	 * @param cost
	 * @return
	 */
	private boolean checkPath(int x, int y, Node parentNode, Node eNode,
			int cost) {
		//System.out.println("--------checkPath-------");
		Node node = new Node(x, y, parentNode);
		//           ,               
		if (map[x][y] == 1) {
			closeList.add(node);
			return false;
		}
		//            
		if (isListContains(closeList, x, y) != -1) {
			return false;
		}
		//            
		int index = -1;
		if ((index = isListContains(openList, x, y)) != -1) {
			// G     ，     G，F 
			if ((parentNode.getG() + cost) < openList.get(index).getG()) {
				node.setParentNode(parentNode);
				countG(node, eNode, cost);
				countF(node);
				openList.set(index, node);
			}
		} else {
			//         
			node.setParentNode(parentNode);
			count(node, eNode, cost);
			openList.add(node);
		}
		return true;
	}

	//            (-1：    ，         )
	private int isListContains(List<Node> list, int x, int y) {
		//System.out.println("----------   -------");
		for (int i = 0; i < list.size(); i++) {
			Node node = list.get(i);
			if (node.getX() == x && node.getY() == y) {
				return i;
			}
		}
		return -1;
	}

	//          
	private void getPath(List<Node> resultList, Node node) {
		System.out.println("node = "+node);
		if (node.getParentNode() != null) {
			getPath(resultList, node.getParentNode());
		}
		resultList.add(node);
	}
	
	//   G,H,F 
	private void count(Node node, Node eNode, int cost) {
		countG(node, eNode, cost);
		countH(node, eNode);
		countF(node);
	}

	//   G 
	private void countG(Node node, Node eNode, int cost) {
		if (node.getParentNode() == null) {
			node.setG(cost);
		} else {
			node.setG(node.getParentNode().getG() + cost);
		}
	}

	//   H 
	private void countH(Node node, Node eNode) {
		node.setF((Math.abs(node.getX() - eNode.getX()) + Math.abs(node.getY()
				- eNode.getY())) * 10);
	}

	//   F 
	private void countF(Node node) {
		node.setF(node.getG() + node.getH());
	}
}

//      
class NodeFComparator implements Comparator<Node> {
	@Override
	public int compare(Node o1, Node o2) {
		return o1.getF() - o2.getF();
	}

}

ケースコードのダウンロード:http://download.csdn.net/detail/u013043346/9327155