中,每个结点X旁有两个数:上面的是最下成本c(X),下面的是成本 估价ε(X)。整个解空间树中有两个答案结点。如果按照估价函数进 行搜索,根结点1首先成为扩展结点,然后是结点2,在扩展结点2 时,得到一个答案结点4,它时结点2的一个儿子。这个答案结点的 成本是20,比另一个答案结点6的成本大 10 10 定理8.1在有限的解空间树中,如果对每对结点X和Y,成本函 数c与成本估价函数e均满足:“c(X)<c(Y”=〉“e(X)<e(Y 则按照成本估价函数搜索能够达到最小成本答案结点。 般情况下,不易找到定理8.1中要求的成本估价函数。对于成 本估价函数,一般有一个基本要求 e(X)≤c(X),对任意结点X 8.2.4) e(X)=c(X),当X是答案结点时。 (8.2.5) 在以下给出的算法中,要求搜索一直继续到一个答案结点变成扩 展结点为止 搜索最小成本答案结点LC一检索 Leastcost(T,)//T是问题的解空间树 1E=T;//第一个扩展结点 2置活结点表为空中，每个结点 X 旁有两个数：上面的是最下成本 c(X),下面的是成本 估价 ĉ(X)。整个解空间树中有两个答案结点。如果按照估价函数进 行搜索，根结点 1 首先成为扩展结点，然后是结点 2，在扩展结点 2 时，得到一个答案结点 4，它时结点 2 的一个儿子。这个答案结点的 成本是 20，比另一个答案结点 6 的成本大。 10 0 20 10 2 4 20 ∞ ∞ 10 20 ∞ ∞ 10 定理 8.1 在有限的解空间树中，如果对每对结点 X 和 Y，成本函 数 c 与成本估价函数 ĉ 均满足：“c(X) < c(Y)” ＝> “ĉ(X) < ĉ(Y)” , 则按照成本估价函数搜索能够达到最小成本答案结点。 一般情况下，不易找到定理 8.1 中要求的成本估价函数。对于成 本估价函数，一般有一个基本要求： ĉ(X)≤ c(X), 对任意结点 X； (8.2.4) ĉ(X)＝c(X)，当 X 是答案结点时。 (8.2.5) 在以下给出的算法中，要求搜索一直继续到一个答案结点变成扩 展结点为止。 搜索最小成本答案结点 LC－检索 LeastCost(T, ĉ)//T 是问题的解空间树 1 E=T; //第一个扩展结点 2 置活结点表为空; 1 2 3 4 5 6 7