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 的子节点 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 表中的节点排序;