当前位置:   article > 正文

问题归约及与或图搜索

与或图搜索

问题归约

图片来自西安电子科技大学课件

定义

将问题通过分解和等价变换的化简,将之变为若干可解的子问题

分解

将复杂问题分解成若干简单可解决,可实现的步骤

  • 一步一步成立,结果成立。故用逻辑与连接,是原命题的成立条件
  • 与或树表达
    在这里插入图片描述
等价变化

利用同构或者是同态,将原问题变为若干较为容易求解的原问题

  • 只要有一种成立就成立,用逻辑或连接,彼此互为等价
  • 与或树表达
    在这里插入图片描述
归约例题

在这里插入图片描述

  • 通过有序对的方式将问题进行有效的描述,确定问题的初始态(1,1,1),确定问题的目标态(3,3,3)

在这里插入图片描述

  • 将三圆盘的移动问题,分解成两元盘的移动问题和一圆盘移动问题,即两元盘由(1,1,1)变为(1,2,2),单元盘由1移动到3.

在这里插入图片描述

  • 进一步对问题进行分解,将两元盘问题分解成一圆盘问题。

在这里插入图片描述

  • 生成对应的与或树,由初始态到目标态,分解成三个步骤。彼此之间必须要用与连接,互为分解条件。最后全部化为单元盘移动的本原问题。
与或图的结构
  • 一般的,我们用与或图将问题归约为后继问题的替换集合
  • 解决A问题可以分解成B,C,D若干个可实现步骤,则用与图连接
    在这里插入图片描述
  • 解决A问题可以用B问题,或者C问题来代替,即解答了B或C,相当于解答了A,则用或图连接

在这里插入图片描述

可解
  1. 可解条件
    • 终叶节点是可解节点
    • 所有或节点只要有一个可解,对应的父节点可解
    • 所有与节点都可解,其对应的父节点才可解
  2. 可解标志:证明某个节点可解,必须通过递归可推出当前节点可解
不可解
  1. 不可解条件:
    • 无后继节点的非叶子节点(对应的叶子节点不可解)
    • 所有或节点全都不可解,对应的父节点不可解
    • 所有的与节点只要有一个不可解,对应的父节点不可解
  2. 不可解标志:证明某个节点不可解,通过递归退出某个节点不可解
与或图搜索——宽度搜索
  • 根本思路:在常见的宽度搜索的基础上,增加回溯,通过可解标志和不可解标志判定初始节点是否可解。
  • 可解节点留下,作为解的一部分;不可解节点删除,不作为树的一部分
    在这里插入图片描述
与或图搜索——深度搜索
  • 在原先深度搜索的基础上不改变,每一次增加节点的同时都通过回溯判定根节点是否可解
  • 深度优先,将扩展结点放在OPEN表前端,先访问
  • OPEN表中承载着带访问的节点;CLOSE表中承载着可解节点,将作为最终解得的与或树的节点

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/378571
推荐阅读
相关标签
  

闽ICP备14008679号