A*算法java实现

代码实现(Java)

1. 输入

(1) 代表地图二值二维数组(0表示可通路，1表示路障)

int[][] maps = {

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },

{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }

}123456789123456789

(2) 按皮猛照二维数组的特点，坐标原点在左上角，所以y是高，x是宽，y向下递增，x向右递增，我们将x和y封装成一个燃首桥类，好传参，重写equals方法比较坐标(x,y)是不是同一芹运个。

public class Coord

{

public int x

public int y

public Coord(int x, int y)

{

this.x = x

this.y = y

}

@Override

public boolean equals(Object obj)

{

if (obj == null) return false

if (obj instanceof Coord)

{

Coord c = (Coord) obj

return x == c.x &&y == c.y

}

return false

}

}12345678910111213141516171819202122231234567891011121314151617181920212223

(3) 封装路径结点类，字段包括：坐标、G值、F值、父结点，实现Comparable接口，方便优先队列排序。

public class Node implements Comparable

{

public Coord coord// 坐标

public Node parent// 父结点

public int G// G：是个准确的值，是起点到当前结点的代价

public int H// H：是个估值，当前结点到目的结点的估计代价

public Node(int x, int y)

{

this.coord = new Coord(x, y)

}

public Node(Coord coord, Node parent, int g, int h)

{

this.coord = coord

this.parent = parent

G = g

H = h

}

@Override

public int compareTo(Node o)

{

if (o == null) return -1

if (G + H >o.G + o.H)

return 1

else if (G + H <o.G + o.H) return -1

return 0

}

}1234567891011121314151617181920212223242526272829303112345678910111213141516171819202122232425262728293031

(4) 最后一个数据结构是A星算法输入的所有数据，封装在一起，传参方便。:grin:

public class MapInfo

{

public int[][] maps// 二维数组的地图

public int width// 地图的宽

public int hight// 地图的高

public Node start// 起始结点

public Node end// 最终结点

public MapInfo(int[][] maps, int width, int hight, Node start, Node end)

{

this.maps = maps

this.width = width

this.hight = hight

this.start = start

this.end = end

}

}12345678910111213141516171234567891011121314151617

2. 处理

(1) 在算法里需要定义几个常量来确定：二维数组中哪个值表示障碍物、二维数组中绘制路径的代表值、计算G值需要的横纵移动代价和斜移动代价。

public final static int BAR = 1// 障碍值

public final static int PATH = 2// 路径

public final static int DIRECT_VALUE = 10// 横竖移动代价

public final static int OBLIQUE_VALUE = 14// 斜移动代价12341234

(2) 定义两个辅助表：Open表和Close表。Open表的使用是需要取最小值，在这里我们使用Java工具包中的优先队列PriorityQueue，Close只是用来保存结点，没其他特殊用途，就用ArrayList。

Queue openList = new PriorityQueue()// 优先队列(升序)

List closeList = new ArrayList()1212

(3) 定义几个布尔判断方法：最终结点的判断、结点能否加入open表的判断、结点是否在Close表中的判断。

/**

* 判断结点是否是最终结点

*/

private boolean isEndNode(Coord end,Coord coord)

{

return coord != null &&end.equals(coord)

}

/**

* 判断结点能否放入Open列表

*/

private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y)

{

// 是否在地图中

if (x 0 || x >= mapInfo.width || y 0 || y >= mapInfo.hight) return false

// 判断是否是不可通过的结点

if (mapInfo.maps[y][x] == BAR) return false

// 判断结点是否存在close表

if (isCoordInClose(x, y)) return false

return true

}

/**

* 判断坐标是否在close表中

*/

private boolean isCoordInClose(Coord coord)

{

return coord!=null&&isCoordInClose(coord.x, coord.y)

}

/**

* 判断坐标是否在close表中

*/

private boolean isCoordInClose(int x, int y)

{

if (closeList.isEmpty()) return false

for (Node node : closeList)

{

if (node.coord.x == x &&node.coord.y == y)

{

return true

}

}

return false

}1234567891011121314151617181920212223242526272829303132333435363738394041424344454612345678910111213141516171819202122232425262728293031323334353637383940414243444546

(4) 计算H值，“曼哈顿” 法，坐标分别取差值相加

private int calcH(Coord end,Coord coord)

{

return Math.abs(end.x - coord.x) + Math.abs(end.y - coord.y)

}12341234

(5) 从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

}123456789101112123456789101112

(6) 添加邻结点到Open表

/**

* 添加所有邻结点到open表

*/

private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)

{

int x = current.coord.x

int y = current.coord.y

// 左

addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE)

// 上

addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE)

// 右

addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE)

// 下

addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE)

// 左上

addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE)

// 右上

addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE)

// 右下

addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE)

// 左下

addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE)

}

/**

* 添加一个邻结点到open表

*/

private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)

{

if (canAddNodeToOpen(mapInfo,x, 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.coord,coord)// 计算H值

if(isEndNode(end.coord,coord))

{

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)

}

}

}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606112345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061

(7) 回溯法绘制路径

private void drawPath(int[][] maps, Node end)

{

if(end==null||maps==null) return

System.out.println("总代价：" + end.G)

while (end != null)

{

Coord c = end.coord

maps[c.y][c.x] = PATH

end = end.parent

}

}12345678910111234567891011

(8) 开始算法，循环移动结点寻找路径，设定循环结束条件，Open表为空或者最终结点在Close表

public void start(MapInfo mapInfo)

{

if(mapInfo==null) return

// clean

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(mapInfo,current)

}

}

单元和区域和数值，，，中的最大

1#include <iostream>

2#include <queue>

3usingnamespace std

4

5struct knight{

6int x,y,step

7int g,h,f

8booloperator<(const knight &k) const{ //重载比较运算符

9return f >k.f

10}

11}k

12bool visited[8][8] //已访问标记正御蔽(关闭列表)

13int x1,y1,x2,y2,ans //举州起点(x1,y1),终点(x2,y2),最少移动次数ans

14int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}}//8个移动方向

15priority_queue<knight>que //最小优先级队列(开启列表)

16

17boolin(const knight &a){ //判断knight是否在棋盘内

18if(a.x<0|| a.y<0|| a.x>=8|| a.y>=8)

19returnfalse

20returntrue

21}

22int Heuristic(const knight &a){/拆粗/manhattan估价函数

23return (abs(a.x-x2)+abs(a.y-y2))*10

24}

25void Astar(){ //A*算法

26knight t,s

27while(!que.empty()){

28t=que.top(),que.pop(),visited[t.x][t.y]=true

29if(t.x==x2 &&t.y==y2){

30ans=t.step

31break

32}

33for(int i=0i<8i++){

34s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1]

35if(in(s) &&!visited[s.x][s.y]){

36s.g = t.g +23//23表示根号5乘以10再取其ceil

37s.h = Heuristic(s)

38s.f = s.g + s.h

39s.step = t.step +1

40que.push(s)

41}

42}

43}

44}

45int main(){

46char line[5]

47while(gets(line)){

48x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1'

49memset(visited,false,sizeof(visited))

50k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h

51while(!que.empty()) que.pop()

52que.push(k)

53Astar()

54printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans)

55}

56return0

57}

58

---