A星算法实现

A星算法的实现 以平面坐标突来表示迷宫的通路时，问题的状态以所处的坐标位置来表示，即综合数据库定义为（x，y），1≤x，y≤N（N为迷宫问题的最大坐标数），则迷宫问题归结为求（1,1）到（4,4）的最短路径问题

package com.yan.astar;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class AStar
{
	public final static int BAR = 1; // 障碍值
	public final static int PATH = 8; // 路径
	public final static int DIRECT_VALUE = 1; // 横竖移动代价G
	
	Queue openList = new PriorityQueue（）; // open表，优先队列（升序）
	List closeList = new ArrayList（）;	// close表
	
	/**
	 * 开始算法
	 */
	public void start（MapInfo mapInfo）
	{
		if（mapInfo==null） return;
		// 清表clear
		openList.clear（）;
		closeList.clear（）;
		// 开始搜索
		openList.add（mapInfo.start）;
		moveNodes（mapInfo）;
	}

	/**
	 * 移动当前结点
	 */
	private void moveNodes（MapInfo mapInfo）
	{
		while （!openList.isEmpty（））
		{
			if （isCoordInClose（mapInfo.end.coord））
			{
				drawPath（mapInfo.maps mapInfo.end）;
				break;
			}
			Node current = openList.poll（）;
			closeList.add（current）;
			addNeighborNodeInOpen（mapInfocurrent）;
		}
	}
	
	/**
	 * 在二维数组中绘制路径（回溯法），并求得总代价，输出逆向路径
	 */
	private void drawPath（int[][] maps Node end）
	{
		if（end==null||maps==null） return;
		System.out.println（“总代价：“ + end.G）;
		System.out.print（“路径逆序为:“）;
		while （end != null）
		{
			Coord c = end.coord;
			maps[c.y][c.x] = PATH;
			end = end.parent;
			System.out.print（“（“+c.y+““+c.x+“）“+“<-“）; 
		}
		System.out.println（）;
	}

	/**
	 * 添加所有邻结点到open表
	 */
	private void addNeighborNodeInOpen（MapInfo mapInfoNode current）
	{
		int x = current.coord.x;
		int y = current.coord.y;
		// 左
		addNeighborNodeInOpen（mapInfocurrent x - 1 y DIRECT_VALUE）;
		// 上
		addNeighborNodeInOpen（mapInfocurrent x y - 1 DIRECT_VALUE）;
		// 右
		addNeighborNodeInOpen（mapInfocurrent x + 1 y DIRECT_VALUE）;
		// 下
		addNeighborNodeInOpen（mapInfocurrent x y + 1 DIRECT_VALUE）;
	}

	/**
	 * 添加一个邻结点到open表
	 */
	private void addNeighborNodeInOpen（MapInfo mapInfoNode current int x int y int value）
	{
		if （canAddNodeToOpen（mapInfox y））
		{
			Node end=mapInfo.end;
			Coord coord = new Coord（x y）;
			int G = current.G + value; // 计算邻结点的G值
			Node child = findNodeInOpen（coord）;
			if （child == null）
			{
				int H = calcH（end.coordcoord）; // 计算H值
				if（isEndNode（end.coordcoord））
				{
					child=end;
					child.parent=current;
					child.G=G;
					child.H=H;
				}
				else
				{
					child = new Node（coord current G H）;
				}
				openList.add（child）;
			}
			else if （child.G > G）
			{
				child.G = G;
				child.parent = current;
				openList.add（child）;
			}
		}
	}

	/**
	 * 从Open列表中查找结点
	 */
	private Node findNodeInOpen（Coord coord）
	{
		if （coord == null || openList.isEmpty（）） return null;
		for （Node node : openList）
		{
			if （node.coord.equals（coord））
			{
				return node;
			}
		}
		return null;
	}


	/**
	 * 计算H的估值：“曼哈顿”法，坐标分别取差值相加
	 */
	private int calcH（Coord endCoord coord）
	{
		return Math.abs（end.x - coord.x）
				+ Math.abs（end.y - c

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        303  2017-10-17 00:42  A-star\A-star\.classpath

     文件        382  2017-10-17 00:42  A-star\A-star\.project

     文件        598  2017-10-17 00:42  A-star\A-star\.settings\org.eclipse.jdt.core.prefs

     文件       4638  2017-10-18 13:17  A-star\A-star\bin\com\yan\astar\AStar.class

     文件        602  2017-10-17 15:49  A-star\A-star\bin\com\yan\astar\Coord.class

     文件        586  2017-10-17 15:49  A-star\A-star\bin\com\yan\astar\MapInfo.class

     文件       1088  2017-10-17 15:49  A-star\A-star\bin\com\yan\astar\Node.class

     文件       1655  2017-10-24 18:11  A-star\A-star\bin\com\yan\astar\Test.class

     文件       4114  2017-10-18 13:17  A-star\A-star\src\com\yan\astar\AStar.java

     文件        361  2017-10-17 15:49  A-star\A-star\src\com\yan\astar\Coord.java

     文件        418  2017-10-17 15:49  A-star\A-star\src\com\yan\astar\MapInfo.java

     文件        664  2017-10-17 15:49  A-star\A-star\src\com\yan\astar\Node.java

     文件        899  2017-10-24 18:11  A-star\A-star\src\com\yan\astar\Test.java

     文件       4114  2017-10-18 13:17  A-star\AStar.java

     文件        361  2017-10-17 15:49  A-star\Coord.java

     文件        418  2017-10-17 15:49  A-star\MapInfo.java

     文件        664  2017-10-17 15:49  A-star\Node.java

     文件        899  2017-10-24 18:11  A-star\Test.java

     目录          0  2017-12-22 11:44  A-star\A-star\bin\com\yan\astar

     目录          0  2017-12-22 11:44  A-star\A-star\src\com\yan\astar

     目录          0  2017-12-22 11:44  A-star\A-star\bin\com\yan

     目录          0  2017-12-22 11:44  A-star\A-star\src\com\yan

     目录          0  2017-12-22 11:44  A-star\A-star\bin\com

     目录          0  2017-12-22 11:44  A-star\A-star\src\com

     目录          0  2017-12-22 11:44  A-star\A-star\.settings

     目录          0  2017-12-22 11:44  A-star\A-star\bin

     目录          0  2017-12-22 11:44  A-star\A-star\src

     目录          0  2017-12-22 11:44  A-star\A-star

     目录          0  2017-12-22 11:44  A-star

----------- ---------  ---------- -----  ----

............此处省略2个文件信息