人工智能 第四章.pptVIP

第四章 与或图有哪些信誉好的足球投注网站 4.1问题归约法 当问题复杂时，可把初始问题分解成若干简单的子问题，若子问题仍复杂，可再进一步分解，直到这些子问题的解可直接得到。这种问题的描述和求解方法，称为问题归约法。 可直接解答的问题称为本原问题。 归约法的问题表示可由下列三部分组成： 1）?????? 一个初始问题的描述 2）?????? 一组把问题变成子问题的算符 3）?????? 一组本原问题的描述 4.2 与或图 对问题归约的描述可以很方便地用一个与或图的结构来表示它。 与节点：一个归约算符能够把单个问题变为几个子问题组成的集合，这时所有子问题都有解，该父辈节点才有解。这种关系称为“与”关系，对应的节点成为与节点。 或节点：几个算符适用于同一个问题，从而产生不同的后继问题集合。这时只要有一个后继集合有解，则意味该父辈问题有解，此时关系是“或”关系，对应节点为或节点。 * 在图4.1中N，M，H是或节点，B，C，D，E，F分别是与节点。 A ? N M H ?  B C D E F 图4.1 与节点和或节点 * 与或节点是针对与或树而言，对于一般的与或图有歧义 ? n0 n1? n2 ? ? n4 n3? ? n5 ? n6? ? n8 ? n7? 图4.2 与或图 * K—连接符： 假设节点N被某个算符归约为一个包含K个子问题的替换集合，K ? 1，我们用一个叫做K—连接符的超弧线把它们和节点N连接起来。每个K—连接符从一个父节点指向一个含有K个后继节点的集合，并说N有一个外向连接符K。这种图称为超图，但我们仍把这种结构叫与或图。 问题归约描述对应的结构就是一个与或图，原始问题描述对应于起始节点（或根节点），本原问题所对应的节点叫做叶节点。在某些特殊情况下，不出现任何与节点，此时的图成了普通图，问题归约描述也就成为状态空间描述。 * 4.3 与或图有哪些信誉好的足球投注网站 在与或图上执行有哪些信誉好的足球投注网站的过程，其目的在于表明起始节点是有解的，也就是说，有哪些信誉好的足球投注网站不是去寻找目标节点，而是寻找一个解图。 定义： 一个与或图G中，从节点 n到节点集 N的解图记为 G?， G?是 G的子图。 1．若 n是 N的一个元素，则 G?由一节点组成； 2．若 n有一个指向节点 {n1…,nk}的外向连接符 K，使得从每一个 ni到 N有一个解图 (i=1,…,k)，则 G?由节点 n，连接符K，及 {n1 ,…,nk}中的每一个节点到 N的解图所组成； 3．否则 n 到N不存在解图。 * 在有哪些信誉好的足球投注网站解图的过程中，还需要进行耗散值的计算。设连接符的耗散值规定为：k-连接符的耗散值=k，若解图的耗散值记为k(n, N)，则可递归计算如下： 1．???????? 若n是N的一个元素，则k(n, N)=0； 2．???????? 若n有一个外向连接符指向后继节点(n1…,ni)，并设该连接符的耗散值为Cn，则 k(n, N)=Cn+k(n1, N)+…+k(ni, N) 具有最小耗散值的解图称为最佳解图，其值也用h*(n)标记。 * 有哪些信誉好的足球投注网站过程还要标记能解节点(SOLVED)，为此给出如下定义： 能解节点(SOLVED): 1．终结点是能解节点； 2．若非终结点 有“或”子节点时，当且仅当其子节点至少有一能解 ，该非终结点才能解； 3．若非终结点有“与”子节点时，当且仅当其子节点均能解，该非终结点才能解。 不能解节点(UNSOLVED): 1．没有后裔的非终结点是不能解节点； 2．若非终结点有“或”子节点时，当且仅当所有子节点均不能解时，该非终结点才不能解； 3．若非终结点有“与”子节点时，当至少有一子节点不能解时，该非终结点才不能解。 * 不过与或图有哪些信誉好的足球投注网站与状态空间图有哪些信誉好的足球投注网站有几点不同，说明如下： 1）有哪些信誉好的足球投注网站目的是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即有哪些信誉好的足球投注网站是否找到叶节点。因此，有哪些信誉好的足球投注网站有可解标示过程和不可解标示过程。初始节点被标示为可解，则有哪些信誉好的足球投注网站成功结束，初始节点被标示为不可解，则有哪些信誉好的足球投注网站失败。 2）一旦发现不可解节点，应把该节点从图中删去。 * 下面我们讨论一般与或图的启发式有哪些信誉好的足球投注网站算法——AO*算法。与A*算法不同，其评价函数f(n)=h(n)，只考虑h(n)这个分量，h(n)作为h* (n)的一个估计。 过程AO*: 1 建立一个有哪些信誉好的足球投注网站图G，G:=s，计算q(s)=h(s)，IF GO