人工智能概论知识要点（二）_与或树

三、问题归约法与博弈

3.1 问题归约和与或图
对于一个复杂问题，直接求解往往比较困难。此时可通过下述方法进行简化：
分解：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解。重复此过程，直到不需要再分解或者不能再分解为止。
等价变换：利用同构或同态的等价变换，把原问题变换为若干个较为容易求解的新问题。
问题归约法
基本思想：从已知问题的描述出发，通过一系列变换把此问题最终变为一个子问题集合；这些子问题的解可以直接得到，从而解决了初始问题。
•问题归约的实质：从目标(要解决的问题)出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。
问题归约法可以用一个三元组（S, O, P）来表示， 其中： S：原始问题，即要解决的问题；P：本原问题集，其中的每一个问题是不用证明的或自然成立的，例如公理、已知事实等；O：操作算子集，用于将问题化为子问题。

原始问题归约（简化）为三个子问题
1、移动A，B盘至柱子2的双圆盘难题
2、移动圆盘C至柱子3的单圆盘问题
3、移动A，B盘至柱子3的双圆盘难题
对于梵塔问题，子问题［（111）→(122)］，［(122)→(322)］以及［(322)→(333)］规定了最后解答路径将要通过的脚踏石状态(122)和(322)。
问题归约法的基本思路是：应用一系列算符将原始问题的描述变换或分解成为子问题的描述问题的描述可以采用各种数据结构，如表、树、矢量、数组等。
与或图
对归约问题,可采用图的结构来表示把问题归约为子问题的替换集合.
表示问题归约的图称为与或图（归约图）

如果某条弧线从节点a指向节点b，那么节点a叫做节点b的父
辈节点；节点b叫做节点a的后继节点或后裔；
或节点，只要解决某个问题就可解决其父辈问题的节点集合；
与节点，只有解决所有子问题，才能解决其父辈问题的节点集合；
终叶节点，是对应于本原问题的节点

可解节点与不可解节点
• 可解节点：与或图中一个可解节点的一般定义可以归纳如下：
1、 终叶节点是可解节点(因为它们与本原问题相关连)。
2、如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点便是可解的。
3、如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。
不可解节点： 不可解节点的一般定义归纳于下：
1、没有后裔的非终叶节点为不可解节点。
2、如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。
3、如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点便是不可解的。

3.2 与或树的盲目式搜索
与或图搜索：在与或图上执行搜索的过程，其目的在于标明起始节点是可解的，即搜索不是去寻找到目标节点的一条路径，而是寻找一个解树。
与或树的一般搜索过程：
⑴ 把原始问题作为初始节点S0，并把它作为当前节点；
⑵ 应用分解或等价变换对当前节点进行扩展；
⑶ 为每个节点设置指向父节点的指针；
⑷ 选择适合的节点作为当前节点，反复执行第⑵步和第⑶步，在此其间要多次调用可解标志过程和不可解标志过程，直到初始节点被标为可解节点或不可解节点为止。
搜索目的：是证明起始节点是否可解，而可解节点是递归定义的，取决于后继节点是否可解，即搜索过程是能否找到终叶节点。
若初始节点被标志为可解，则搜索成功结束；若初始节点被标志为不可解，则搜索失败。

宽度优先搜索的过程
（1）把初始节点S0放入OPEN表中；
（2）把OPEN表中的第一个节点（记为节点n）取出，放入CLOSED表中；
（3）如果节点n可扩展，则做下列工作：
①扩展节点n，将其子节点放入OPEN表的尾部，并为每个子节点配置指向父节点的指针，以备标记过程使用；
②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点、祖父节点等先辈节点中的可解节点进行标记。如果初始节点S0也被标记为可解节点，就得到了解树，搜索成功；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。（一经扩展即考察）
③转不周（2）。
（4）如果节点n不可扩展，则：
①标记节点n为不可解节点
②应用不可解标记过程对节点n的先辈节点中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败。如果不能确定S0，则从OPEN表中删去具有不可解先辈的节点。
③转步骤（2）。

与或树的深度优先搜索

3.3博弈树搜索
Max-Min搜索
基本思想：
目的是为博弈的双方中的一方寻找一个最优行动方案；
要寻找这个最优方案，就要通过计算当前所有可能的方案来进行比较；
方案的比较是根据问题的特征来定义一个估价函数，用来估算当前博弈树端节点的得分；
当计算出端节点的估值后，再推算出父节点的得分（即计算倒推值）；
 对Max节点，选其子节点中一个最大得分作为父节点的得分
 对Min节点，选其子节点中一个最小得分作为父节点的得分
如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。
Max-Min搜索流程总结：
Step1：以 c(o) 为根，生成 k-步博弈树；
Step2：评估博弈树叶节点对应的博弈状态(棋局)；
Step3：进行极大极小运算 (Max-Min 运算)；
Step4：等待 Min 行棋，产生新的 c(o)，返回 step1.




α-β剪枝
首先分析极大极小法效率，上述的极大极小法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极大极小法效率较低。于是在极大极小法的基础上提出了α-β剪枝技术。
α-β剪枝技术的基本思想，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。

算法的剪枝规则
对于一个Min节点来说，它取当前子节点中的最小倒推值作为它倒推值的上界，称此为β值；
对于一个Max节点来说，它取当前子节点中的最大倒推值作为它倒推值的下界，称此为α值.
规则一 (α剪枝规则)：
任何Min节点x的值如果不能升高其父节点的α值，则对节点x以下的分支可停止搜索，并使x的倒推值为β
规则二 (β剪枝规则)：
任何Max节点x的值如果不能降低其父节点的β值，则对节点x以下的分支可停止搜索，并使x的倒推值为α。
由规则一形成的剪枝被称为 “剪枝”，而由规则二形成的剪枝被称为 “剪枝”。