A算法搜索过程中设置两个表OPEN和CLOSED

《A算法搜索过程中设置两个表OPEN和CLOSED》由会员分享，可在线阅读，更多相关《A算法搜索过程中设置两个表OPEN和CLOSED（9页珍藏版）》请在金锄头文库上搜索。

1、A算法搜索过程中设置两个表OPEN和CLOSED。A*算法搜索过程中设置两个表：OPEN和CLOSED。 OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。 A*算法伪码描述如下： Copy to clipboard - CODE: Astar_Search Open = 起始节点; Closed = ; while (Open表非空) 从Open中取得一个节点X，并从OPEN表中删除。 if (X是目标节点) 求得路径PATH； 返回路径PATH； for (每一个X的

2、子节点Y) if (Y不在OPEN表和CLOSE表中) 求Y的估价值； 并将Y插入OPEN表中； /还没有排序 else if (Y在OPEN表中) if (Y的估价值小于OPEN表的估价值) 更新OPEN表中的估价值； else /Y在CLOSE表中 if (Y的估价值小于CLOSE表的估价值) 更新CLOSE表中的估价值； 从CLOSE表中移出节点，并放入OPEN表中； 将X节点插入CLOSE表中； 按照估价值将OPEN表中的节点排序； /end for /end while /end func 上面的伪码可以说是一个模板了呵呵偶用JAVA实现的A*算法也大概就是用这个模板做的 FLASH

3、 AS也差不多吧 下面是JAVA源码： Copy to clipboard - CODE: /一个很简单的迷宫问题算法 import java.util.*; class Node boolean attainability; /节点是否可达到 int x,y; /节点的位置信息 int direction = 1; int score; String id = ; /Node leftNode,rightNode,upNode,downNode; /Node fatherNode; public class Puzzle Node maze = null; /迷宫数组 Node startN

4、ode,endNode; /起始点，结束点 public Puzzle /初始化迷宫数组并指定起始点和结束点 maze = new Node79; for(int i=0;i7;i+) for(int j=0;j9;j+) mazeij = new Node; mazeij.attainability = true; mazeij.x = i; mazeij.y = j; startNode = maze32; startNode.id = &; endNode = maze36; endNode.id = ; for(int i=0;i7;i+) mazei0.attainability =

5、 false; mazei8.attainability = false; for(int j=0;j9;j+) maze0j.attainability = false; maze6j.attainability = false; maze43.attainability = false; maze24.attainability = false; maze34.attainability = false; maze44.attainability = false; private void printMaze for(int i=0;i7;i+) for(int j=0;j9;j+) if

6、(mazeij.attainability) if(mazeij = startNode) System.out.print(& ); else if(mazeij = endNode) System.out.print( ); else System.out.print(mazeij.id + ); else if(i=0 | i=6 | j=0 |j=8 | (i=4&j=3) |(i=2&j=4) |(i=3&j=4) |(i=4&j=4) System.out.print(# ); else System.out.print(mazeij.id + ); System.out.prin

7、tln; public void getPath Stack s = new Stack; Node curpos = startNode; /int curstep = 1; do if(curpos.attainability) curpos.attainability = false; if(curpos!=startNode & curpos!=endNode) curpos.id = %; s.push(curpos); if(curpos = endNode) printMaze; Node tmp = nextPos(curpos,1); curpos = mazetmp.xtm

8、p.y; / curpos.id+; / curstep+; else Node e = (Node)s.pop; while(e.direction = 4 & !s.empty) e.attainability = false; e = (Node)s.pop; if(e.direction 4) e.direction+; s.push(e); Node tmp = nextPos(e,e.direction); curpos = mazetmp.xtmp.y; while(!s.empty); private Node nextPos(Node pos, int i) /按东南西北的顺

9、序 Node tmp = new Node; tmp.direction = pos.direction; tmp.attainability = pos.attainability; int x = pos.x; int y = pos.y; if(i = 2 & xmaze.length-1) /南 x = x+1; tmp.y = pos.y; tmp.x = x; else if(i = 4 & x != 0) /北 x = x-1; tmp.y = pos.y; tmp.x = x; else if(i = 1 & ymaze0.length-1) /东 y = y+1; tmp.x = pos.x; tmp.y = y; else if(i = 3 & y != 0) /西 y = y - 1; tmp.x = pos.x; tmp.y = y; return tmp; public void Astar getScore; Stack open = new Stack; /初始开启列表 open.push(startNode); Stack close = new Stack; /初始关闭列表 while(op