问题归约及与或图搜索
问题归约
图片来自西安电子科技大学课件
定义
将问题通过分解和等价变换的化简，将之变为若干可解的子问题
分解
将复杂问题分解成若干简单可解决，可实现的步骤
- 一步一步成立，结果成立。故用逻辑与连接，是原命题的成立条件
- 与或树表达
等价变化
利用同构或者是同态，将原问题变为若干较为容易求解的原问题
- 只要有一种成立就成立，用逻辑或连接，彼此互为等价
- 与或树表达
归约例题
- 通过有序对的方式将问题进行有效的描述，确定问题的初始态（1，1，1），确定问题的目标态（3，3，3）
- 将三圆盘的移动问题，分解成两元盘的移动问题和一圆盘移动问题，即两元盘由（1，1，1）变为（1，2，2），单元盘由1移动到3.
- 进一步对问题进行分解，将两元盘问题分解成一圆盘问题。
- 生成对应的与或树，由初始态到目标态，分解成三个步骤。彼此之间必须要用与连接，互为分解条件。最后全部化为单元盘移动的本原问题。
与或图的结构
- 一般的，我们用与或图将问题归约为后继问题的替换集合
- 解决A问题可以分解成B，C，D若干个可实现步骤，则用与图连接
- 解决A问题可以用B问题，或者C问题来代替，即解答了B或C，相当于解答了A，则用或图连接
可解
- 可解条件
- 终叶节点是可解节点
- 所有或节点只要有一个可解，对应的父节点可解
- 所有与节点都可解，其对应的父节点才可解
- 可解标志：证明某个节点可解，必须通过递归可推出当前节点可解
不可解
- 不可解条件：
- 无后继节点的非叶子节点（对应的叶子节点不可解）
- 所有或节点全都不可解，对应的父节点不可解
- 所有的与节点只要有一个不可解，对应的父节点不可解
- 不可解标志：证明某个节点不可解，通过递归退出某个节点不可解
与或图搜索——宽度搜索
- 根本思路：在常见的宽度搜索的基础上，增加回溯，通过可解标志和不可解标志判定初始节点是否可解。
- 可解节点留下，作为解的一部分；不可解节点删除，不作为树的一部分
与或图搜索——深度搜索
- 在原先深度搜索的基础上不改变，每一次增加节点的同时都通过回溯判定根节点是否可解
- 深度优先，将扩展结点放在OPEN表前端，先访问
- OPEN表中承载着带访问的节点；CLOSE表中承载着可解节点，将作为最终解得的与或树的节点