1.定义
    用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点,这种搜索方法叫做有序搜索(ordered search)或最佳优先搜索(best-first search)。
    尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数f是这样确定的:一个节点的希望程序越大,其f值就越小。被选为扩展的节点,是估价函数最小的节点。 自动控制网www.eadianqi.com版权所有

2.实质
    选择OPEN表上具有最小f值的节点作为下一个要扩展的节点,即总是选择最有希望的节点作为下一个要扩展的节点。 本文来自www.eadianqi.com

3.有序状态空间搜索算法
    (1) 把起始节点S放到OPEN表中,计算f(S)并把其值与节点S联系起来。
    (2) 如果OPEN是个空表,则失败退出,无解。
    (3) 从OPEN表中选择一个f值最小的节点i。若有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i。
    (4) 把节点i从OPEN表中移出,并把它放入CLOSED的扩展节点表中。
    (5) 如果i是个目标节点,则成功退出,求得一个解。
    (6) 扩展节点i,生成其全部后继节点。对于i的每一个后继节点j:
        (a) 计算f(j);
        (b) 若j既不在OPEN表,又不在CLOSED表中,则将其加入OPEN表,并按f值排序,提供指向i的指针;
        (c) 若j已在OPEN或CLOSED表中,则比较新的f(j)和以前计算过的值,若新值较小,用新值取代旧值,将j的父节点由原来的改为i,若j在CLOSED中将其移回OPEN表。 自动控制网www.eadianqi.com版权所有
    (7) 转向(2),即GO TO(2)。 本文来自www.eadianqi.com

4.有序搜索方法分析
    宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索,选择f(i)作为节点i的深度。对于等代价搜索,f(i)是从起始节点至节点i这段路径的代价。f的选择直接影响了有序搜索的效率,其选择涉及两个方面的内容:即时间和空间之间的折衷,以及能否保证有一个最优的解或任意解。 本文来自www.eadianqi.com

5.例
    采用了简单的估价函数
        f(n)=d(n)+W(n)。
    其中:d(n)是搜索树中节点n的深度;W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此,起始节点棋局的f值等于0+4=4。