alogical.txt

A*算法是最好优先算法的一种。只是有一些约束条件而已。我们先来看看最好优先算法是如何编写的吧。 实现深度算法的伪代码

----------------------------------------
搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。具体搜索过程如下：

1）初始状态：　　　　　　　　　　　　　　　　
　OPEN=[A5]；CLOSED=[]；
2）估算A5，取得搜有子节点，并放入OPEN表中；
　OPEN=[B4，C4，D6]；CLOSED=[A5]
3）估算B4，取得搜有子节点，并放入OPEN表中；
　OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]
4）估算C4；取得搜有子节点，并放入OPEN表中；
　OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]
5）估算H3，取得搜有子节点，并放入OPEN表中；
　OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=[H3，C4，B4，A5]
6）估算O2，取得搜有子节点，并放入OPEN表中；
　OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]
7）估算P3，已得到解；

伪代码：
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

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