关于A*算法 伪代码解决方法
关于A*算法 伪代码
Best_First_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表中的节点排序;
}//end for
}//end while
}//end func
请问何谓open表及close表的估价值 是中最小的一个吗
------解决方案--------------------
http://www.cppblog.com/christanxw/archive/2006/04/07/5126.aspx
这个专栏里面有详细介绍,我在学人工智能的时候有关注。
在游戏编程里面应用很广。
Best_First_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表中的节点排序;
}//end for
}//end while
}//end func
请问何谓open表及close表的估价值 是中最小的一个吗
------解决方案--------------------
http://www.cppblog.com/christanxw/archive/2006/04/07/5126.aspx
这个专栏里面有详细介绍,我在学人工智能的时候有关注。
在游戏编程里面应用很广。