人工智能入门课件第3章 图有哪些信誉好的足球投注网站策略.pptVIP

2．A*算法的性质 A*算法与一般的最佳优先比较，有其特有的性质：如果问题有解，即S0→Sg存在一条路径，A*算法一定能找到最优解。这一性质称为可采纳性(admissibility）。 （ 例3.4) . 野人传教士问题 作者 朱福喜 朱三元 3.2 与/或图有哪些信誉好的足球投注网站 3.2.1 问题归约求解方法与“与/或图” 在问题求解过程中, 将一个大的问题变换成若干子问题, 子问题又可分解成更小的子问题，这样一直分解到可以直接求解为止, 全部子问题的解即为大的问题的解,这样的过程称为问题的规约(Problem Reduction)。并称大的问题为初始问题，可直接求解的问题为本原问题。 一般说来，归约方法求解问题需要三大要素： 1．? 初试问题的描述。 2． 一组将问题变换成子问题的变换规则。 3．? 一组本原问题的描述。 例3.6 符号积分问题 分解时有三种可能: 1.?????? and 2.?????? or 3.?????? and, or 都有 从初始问题出发, 建立子问题以及子问题的子问题, 直至把初始问题规约为一个本原问题的集合, 这就是问题规约的实质。 3.2.2 “与/或图”的构造方法 将问题求解归约为与/或图的时，作如下规定： 1．根节点为原始问题描述; 本原问题的节点为叶节点。 2．可解节点为： 2.1 终叶节点是可解节点； 2.2 若n为一非终叶节点，且含有“或”后继节点，则只有当后继节点中至少有一个是可解节点时，n才可解； 2.3 若n为非终叶节点，且含“与”后继节点，则只有当后继节点全部可解时，n才可解。 3． 不可解节点 3.1 没有后继节点的非终叶节点为不可解； 3.2 若n为一非叶节点含有“或”后继节点，则仅当全部后继节点为不可解时，n不可解。 3.3 若n为一非叶节点含有“与”后继节点，则只要有一个后继节点为不可解时，n为不可解。 作者 朱福喜 朱三元 4．图中有哪些信誉好的足球投注网站费用的计算 设从当前节点n到目标集Sg费用估计为h(n). 4.1 若n∈Sg, 则h(n)=0; 4.2 若n有一组由“与”弧连接的后继节点{n1,n2,…ni} 则: h(n)=c1+c2…+ci+…+h(n1)+h(n2)+…+h(ni) 4.3 若n既有“与”又有“或”弧，则“与”弧算作一个“或”后继，再取各or弧后继中费用最小者为n的费用。 3.2.3 与/或图有哪些信誉好的足球投注网站的过程 1．与/或图有哪些信誉好的足球投注网站有哪些信誉好的足球投注网站费用的估计 对与/或图则不同，其费用计算的规则是： ? n未生成后继节点时，费用由n本身决定; n已生成后继节点时，费用由n的后继节点的费用决定。 因为后继节点代表分解的子问题, 子问题的难易程度决定原问题求解的难易程度，所以不再考虑n本身的难易程度。因此当决定了某个路径时，要将后继节点的估计值往回传送。 例3.7 图3-9为一个与/或图的有哪些信誉好的足球投注网站过程。 第一步，A是唯一节点； 第二步，扩展A后，得到节点B,C和D, 因为B，C的耗费为9，D的耗费为6，所以把列D的弧标志为出自A最有希望的弧； 第三步，选择对D的扩展，得到E和F的与弧，其耗费估计值为10。此时回退一步后，发现与弧BC比D更好，所以将弧BC标志为目前最佳路径； 第四步，在扩展B后,再回传值发现弧BC的耗费为12（6+4+2），所以D再次成为当前最佳路径。 最后求得的耗费为: f(A)=min(12,4+4+2+1)=11。 以上有哪些信誉好的足球投注网站过程由两大步组成： （1) 自顶向下，沿当前最优路产生后继节点。 （2）由底向下，作估计值修正，再重新选择最优路。 2. 与/或图有哪些信誉好的足球投注网站的限制 与/或图有哪些信誉好的足球投注网站仅对不含回路的图进行操作。 例如： 　x 　y ?表示求了x就可以求y.，求了y就可以求x，两者都不可能求解。 3.2.4 与/或图有哪些信誉好的足球投注网站算法AO* AO*算法： 1. 令G=Init,计算h’(Init)。 2. 在Init标志solved之前或h’(Init)变成大于Futility之前，执行以下步骤： 2.1沿始于Init的已带标志的弧，选出当前沿标志路上未扩展的节点之一扩展（即求后继节点），此节点称为node。 2.2 生成node的后继节点。 若无后继节点，则令h’(node)=Futility,说明该节点不可解； 若有后继节点，称为successor,对每个不是node祖先的后继节点（避免回路），执行下述步骤： 2.2.1 将successor加入G。 2.2.2 若successor∈Sg,则标志su