α-β剪枝技术-机器人与智能技术实验室-合肥工业大学.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 合肥工业大学人工智能与数据挖掘研究室 */123 有信息的搜索—与/或树、搜索树及其解树 (a) 根节点可解 (b) 根节点不可解 与/或树及解树的标注　 t t t t t t t t * 合肥工业大学人工智能与数据挖掘研究室 */123 有信息的搜索—与/或树、搜索树及其解树 代价树及其表示：给与/或树的每一搜索路径及节点标注上所需耗费的代价值，就形成了与/或树的代价树。 求解的目标：即找出根节点可解的最小代价树及其代价值。 * 合肥工业大学人工智能与数据挖掘研究室 */123 有信息的搜索—与/或树、搜索树及其解树 与/或树代价计算：具体约定为 ① 通常可解的端节点t的代价值为0，可表示为：h(t)=0； ② 可解节点n的代价h(n)为有限值，对可解节点n的代价需要具体加以计算； ③ 不可解节点x的代价为无穷大或无定义，可表示为：h(x)=∞ 或无意义； ④ 如果节点x不可扩展，且又不是终止节点，则定义h(x)=∞。 * 合肥工业大学人工智能与数据挖掘研究室 */123 有信息的搜索—与/或树、搜索树及其解树 代价计算策略：设C(x,y)表示节点x到节点y的代价,具体代价的计算方法如下： （1）或节点计算：若x是或节点，y1,y2, …,yn是它的子节点，则x节点的代价计算式为： h(x)=min｛C(x,yi)+ h(yi)｝ (1≤i≤n) （2）与节点计算： ① 和代价法：若x是与节点，通常按照和代价法计算 　　 h(x)= ∑{C(x,yi)+ h(yi)}，其中，i由1累加到n. ② 最大代价法计算：与节点的最大代价法计算式为 　　 h(x)=max｛C(x,yi)+ h(yi)｝ (1≤i≤n) 具体问题可依照其性质取其一种计算之。求解根节点的代价可依照选择的解树，从端节点指向根节点，逐级计算,按照各部分代价累加得到根节点的代价值。 * 合肥工业大学人工智能与数据挖掘研究室 */123 有信息的搜索—与/或树、搜索树及其解树 例2-9 下图所示为一棵与/或树，它分别由左、右两棵解树以及A～G、H、K～L等各种节点组成。各节点的代价按照上述定义已有约定；每条边的代价值已在图中标注出来，图中没有标注代价的边其值为1。请分别按照或树的最小代价法、与节点的和代价法及最大代价法计算它们各自的代价值。 解：各个节点及解树的代价计算应该自下而上有序地进行。代价的计算过程如表所示: * 合肥工业大学人工智能与数据挖掘研究室 */123 有信息的搜索—与/或树、搜索树及其解树 S0 2 3 A 　　　 　　　　B 　2 　3 2 E F C D 4 3 5 H K L G 3 M N 左 节 点 N M H G D C A S0 和代价 0 0 4 0 11 ∝ 14 16 最大代价 0 0 3 0 6 ∝ 9 11 右 节 点 L K F E B S0 和代价 ∝ 0 5 0 8 11 最大代价 ∝ 0 5 0 7 1