a).如果X是答案结点,则c(X)是解空间树中,由根结点到X的 成本(即所用的代价,如级数、计算复杂度等); b).如果X不是答案结点,而且以X为根的子树中不含答案结点 则c(X)定义为∞; c).如果X不是答案结点,但是以X为根的子树中含答案结点,则 c(X)是具有最小成本的答案结点的成本。 如果能够获得这样的优先级函数,则优先队列式分支限界法将以 最少的搜索时间找到问题的解。然而,这样的优先级函数的计算工作 量不亚于解原问题。实际问题中都是采用一个估计函数e,它由两部 分决定:解空间树的根结点到Ⅹ的成本f(X)和X到答案结点的估计 成本g(X),即(X)=f(X)+g(X).称为成本估计函数。根据成本估 计函数选择下一个扩展结点的策略总是选取(·)值最小的活结点作 为下一个扩展结点。这种搜索策略称为最小成本检索( Least cost search),简称LC-检索。如果取g=0,f(X)等于X在解空间树中的级, 则LC-检索即是宽度优先搜索(BFS);如果f=0,且g满足: Y是X的儿子→g(Y≤g(X (8.2.1) 则LC-检索即是深度优先搜索(ODFS).在以后所提到的成本函数ε中, 函数g都满足(8.2.1)式。 例子15迷问题 在一个分成4×4的棋盘上排列15块号牌,如图(a)。其中会出 现一个空格。棋盘上号牌的一次合法移动是指将位于空格上、下、左、 右的一块号牌移入空格。要求通过一系列合法移动,将号牌的初始排a).如果 X 是答案结点，则 c(X)是解空间树中，由根结点到 X 的 成本(即所用的代价，如级数、计算复杂度等)； b).如果 X 不是答案结点，而且以 X 为根的子树中不含答案结点， 则 c(X)定义为∞； c).如果 X 不是答案结点，但是以 X 为根的子树中含答案结点，则 c(X)是具有最小成本的答案结点的成本。 如果能够获得这样的优先级函数，则优先队列式分支限界法将以 最少的搜索时间找到问题的解。然而，这样的优先级函数的计算工作 量不亚于解原问题。实际问题中都是采用一个估计函数 ĉ，它由两部 分决定：解空间树的根结点到 X 的成本 f(X)和 X 到答案结点的估计 成本 g(X)，即 ĉ(X)= f(X)+g(X). ĉ 称为成本估计函数。根据成本估 计函数选择下一个扩展结点的策略总是选取 ĉ(·)值最小的活结点作 为下一个扩展结点。这种搜索策略称为最小成本检索（Least Cost search），简称 LC-检索。如果取 g=0,f(X)等于 X 在解空间树中的级， 则 LC-检索即是宽度优先搜索(BFS)；如果 f=0，且 g 满足： Y 是 X 的儿子 ⇒ g(Y)≤ g(X) (8.2.1) 则 LC-检索即是深度优先搜索(DFS).在以后所提到的成本函数 ĉ 中， 函数 g 都满足(8.2.1)式。 例子 15 迷问题 在一个分成 4×4 的棋盘上排列 15 块号牌，如图(a)。其中会出 现一个空格。棋盘上号牌的一次合法移动是指将位于空格上、下、左、 右的一块号牌移入空格。要求通过一系列合法移动，将号牌的初始排