与或树有哪些信誉好的足球投注网站与或树.pptVIP

举例(三阶梵塔) 举例(三阶梵塔) 与 分解 问题n为n1 …. nk个子问题。 只有解决所有子问题，才能解决其父辈问题的子问题集合。 问题分解过程用图表示： 图中节点代表问题。与关系集合中，各个结点之间用一段小圆弧连接标记。 或 变换 问题n为n1 …. nk个新问题。 只要解决某个问题就可解决其父辈问题的节点集合。 可解性判别 一个节点是可解，则节点须满足下列 条件之一： 1 终止节点是可解节点; 2一个与节点可解，当且仅当其子节点全都可解； 3一个或节点可解，只要其子节点至少有一个可解； 一个节点是不可解，则节点须满足下列条件之一： 1 非终止节点的端节点是不可解节点； 2 一个与节点不可解，只要其子节点至少有一个不可解； 3 一个或节点不可解，当且仅当其子节点全都不可解。 * 6.1 与或树 6.2 与或树有哪些信誉好的足球投注网站 6.3 启发式与或树有哪些信誉好的足球投注网站 6 与或树有哪些信誉好的足球投注网站 6.1 与或树  三阶梵塔 （1,1,1） （3,3,3） CBA 三元组 (i, j, k) i 代表金盘A所在的杆号；j代表金盘B所在的杆号；k代表金盘C所在的标号。 (ABC) （1,1,1）（1,2,2） （1,2,2）（3,2,2） （3,2,2）（3,3,3） （1,1,1） CBA (1,2,2) （3,3,3） （3,3,3） （1,1,1） 3,2,2 （1,2,2） （3,2,2） (1,1,1)=(3,3,3) (1,1,1)=(1,2,2) (1,2,2)=(3,2,2) (3,2,2)=(3,3,3) (1,2,3)=(1,2,2) (3,2,2)=(3,2,1) (3,2,1)=(3,3,1) (3,3,1)=(3,3,3) (1,1,1)=(1,1,3) (1,1,3)=(1,2,3) 与或树表示 (1)把B、C盘从1号杆移到2号杆； (2)把A盘从1号杆移到3号杆； (3)把B、C盘从2号杆移到3号杆； (1,1,1)=(3,3,3) (1,1,1)=(1,2,2) (1,2,3)=(1,2,2) (1,1,1)=(1,1,3) (1,1,3)=(1,2,3) CBA 在三阶梵塔问题中，从左至右的顺序排列，得问题的解： (1,1,1)=(1,1,3) (1,1,3)=(1,2,3) (1,2,3)=(1,2,2) (1,2,2)=(3,2,2) (3,2,2)=(3,2,1) (3,2,1)=(3,3,1) (3,3,1)=(3,3,3) 对于复杂的问题，直接求解往往比较困难。 从原问题出发，通过运用某些规则不断进行问题分解，重复进行，直到不能在分解或不需要分解为止。 从原问题出发，通过运用某些规则不断进行问题变换，把原问题变换为若干较容易求的新问题。 复杂问题简化 与或树用来描述一类问题的求解过程：把待解的原问题作为初始节点，把由原问题经一系列分解或变换而得到的可解的简单问题作为目标节点。——与或树。 节点：对应问题 子节点：对应子问题（由节点分解或变换） 问题的与或树表示 与或树的节点代表问题，其中既有与关系又有或关系，整个树表示问题空间。 与节点 D A B E F I G 或节点 Q13 Q21 Q11’ Q12’ Q22 Q23 Q21’ Q22’ Q23’ Q12 Q11 Q13’ Q Q1 Q2 思考： 问题Q解决方案：？ 概念与术语 本原问题：直接可解的简单问题（不能再分解或变换）。 终止结点：本原问题对应的节点。(可解节点) 端节点: 在与或树中无子节点的节点。 与节点： 一个节点的子节点如果是“与”关系，称~ 或节点： 一个节点的子节点如果是“或”关系，称~ 思考: 终止节点是端节点吗? 注意： 终止节点一定是端节点，但端节点不一定是终止节点。 问题求解过程就是在一个与或树中寻找一个从初始节点（原始问题）到目标节点（可解的简单问题）的路径问题。