0。Lc检索(结点成本的两个标 准) o一:在生成一个答案结点之前,子树X需要 生成的结点数。 o二:在子树X中离X最近的那个答案结点到X 的路径长度。以图91为例 节点1、18和34、29和35、30和38的代价分 别是4,3,2,1 其他2,3,4级上的点代价应分别大于3,2, 生成结点(1>2183450>192429>30 32>31)
LC-检索（结点成本的两个标 准） 一：在生成一个答案结点之前，子树X需要 生成的结点数。 二：在子树X中离X最近的那个答案结点到X 的路径长度。以图9.1为例 ⚫ 节点1、18和34、29和35、30和38的代价分 别是4，3，2，1 ⚫ 其他2，3，4级上的点代价应分别大于3，2， 1 ⚫ 生成结点（1>2 18 34 50>19 24 29>30 32>31）
●●● 0 B BB 565660): 20 B B 12324 2526 B 272 29 BB B B B B 39 B 答案结点
39
●·。Lc检索(结点成本函数) oc()定义 o如果X是答案结点,则c(X)是由状态空 间树的根结点到X的成本(即花费的代 价,可以是级数、计算复杂度等) o如果X不是答案结点且子树X不包含任 何答案结点,则c(X)= o如果X不是答案结点但子树X包含答案 结点,则c(X)等于子树X中具有最小成 本的答案结点的成本
LC-检索（结点成本函数） C(·)定义 如果X是答案结点，则C(X)是由状态空 间树的根结点到X的成本（即花费的代 价，可以是级数、计算复杂度等） 如果X不是答案结点且子树X不包含任 何答案结点，则C(X)＝∞ 如果X不是答案结点但子树X包含答案 结点，则C(X)等于子树X中具有最小成 本的答案结点的成本
·Lc检索(成本估计函数) o从前面的两个成本度量标准看,计算c()的工 作量与原问题的解具有相同复杂度。这是因为 计算一个结点的代价通常要检索包含一个答案 结点的子树才能确定,而这正是解决此问题所 要作的检索工作,因此要得到精确的成本函数 般是不现实的 o因此需要成本估计函数g^(X) o出现的新问题 ●仅利用9^(X)会导致算法偏向纵深检查,无法 有效处理下面这种情况:即g^(W<g^(Z),但Z 比W更接近答案结点
LC-检索（成本估计函数） 从前面的两个成本度量标准看，计算C(·)的工 作量与原问题的解具有相同复杂度。这是因为 计算一个结点的代价通常要检索包含一个答案 结点的子树才能确定，而这正是解决此问题所 要作的检索工作，因此要得到精确的成本函数 一般是不现实的 因此需要成本估计函数g^(X) 出现的新问题 ⚫ 仅利用g^(X) 会导致算法偏向纵深检查，无法 有效处理下面这种情况：即g^(W)<g^(Z)，但Z 比W更接近答案结点
●·Lc分枝限界检索 o为使算法不过分偏向于纵深检查,需改进成本 估计函数,便其不只考虑结点X到 案结 点的估计成本,还应考虑根节点到结点X的成 本 o CA(X=f(h())+g(X) oh(X)为根结点到结点X的成本 X)是由X到达一个答案结点所需做的附加 作的估计函数 oLc-限界检索:选择c^()值最小的活结点作为 下一个E结点 ●BFS:g^(X=0;f(h(X)=X的级数 D- Search:f(h(X)=0;每当Y是X的一个儿 子时,总有g^(X)>=g^(Y, oLc分枝限界检索:伴之有限界函数的LC-检索
LC分枝-限界检索 为使算法不过分偏向于纵深检查，需改进成本 估计函数，使其不只考虑结点X到一个答案结 点的估计成本，还应考虑根节点到结点X的成 本 c^(X) ＝f (h(X)) + g^(X) h(X)为根结点到结点X的成本 g^(X)是由X到达一个答案结点所需做的附加 工作的估计函数 LC-限界检索：选择c^(·)值最小的活结点作为 下一个E-结点 ⚫ BFS： g^(X)＝0； f (h(X)) ＝X的级数 ⚫ D-Search：f (h(X)) ＝0；每当Y是X的一个儿 子时，总有g^(X)>=g^(Y)， LC分枝-限界检索：伴之有限界函数的LC-检索