首页
登录 | 注册

问题规约---漫谈人工智能

问题规约(Problem reduction): 是另一种基于状态空间的问题描述与求解方法。已知问题的描述,通过一系列变换把此问题最终变成另一个本原问题(事实,定理)集合;这些本原问题的解可以直接得到,从而解决了初始问题。

问题规约表示可以由下列三部分组成: 
(1)一个初始问题描述; 
(2)一套把问题变换为子问题的操作符; 
(3)一套本原问题描述。

先把问题分解为子问题和子-子问题,然后解决较小的问题。对该问题的某个具体子集的解答就意味着对原始问题的一个解答。问题归约表示的组成部分:一个初始问题描述;一套把问题变换为子问题的操作符;一套本原问题描述。问题归约的实质:从目标(要解决的问题)出发逆向推理,建立子问题以及子问题的子问题,直至最后把初始问题归约为一个平凡的本原问题集合。

变换可区分为以下三种情况: (1)状态变迁:导致问题从上一状态变迁到下一状态,这就是一般图搜索技术中操作算子的作用。 (2)问题分解:分解问题为需同时处理的子问题,但不改变问题状态。 (3)基于状态变迁的问题分解:先导致状态变迁,再实现问题分解,实际上就是前两个操作的联合执行。


例如:

梵塔难题:

  有3个柱子(1,2和3)和3个不同尺寸的圆盘(A,B和C)。在每个圆盘的中心有一个孔,所以圆盘可以堆叠在柱子上。最初,3个圆盘都堆在柱子1上:最大的圆盘C在底部,最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上,每次只许移动一个,而且只能先搬动柱子顶部的圆盘,还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。
问题规约---漫谈人工智能

 

解题过程:

  将原始问题归约为一个较简单问题集合,要把所有圆盘都移至柱子3,我们必须首先把圆盘C移至柱子3;而且在移动圆盘C至柱子3之前,要求柱子3必须是空的。只有在移开圆盘A和B之后,才能移动圆盘C;而且圆盘A和B最好不要移至柱子3就不能把圆盘C移至柱子3。因此,首先应该把圆盘A和B移到柱子2上。然后才能够进行关键的一步,把圆盘C从柱子1移至柱子3,并继续解决难题的其余部分。
  梵塔问题归约图:子问题2可作为本原问题考虑,因为它的解只包含一步移动(最原始的状态)。应用一系列相似的推理,子问题1和子问题3也可被归约为本原问题。

 

  问题规约---漫谈人工智能

 


相关文章

  • 机器学习web服务化实战:一次吐血的服务化之路
    背景 在公司内部,我负责帮助研究院的小伙伴搭建机器学习web服务,研究院的小伙伴提供一个机器学习本地接口,我负责提供一个对外服务的HTTP接口. 说起人工智能和机器学习,python是最擅长的,其以开发速度快,第三方库多而广受欢迎,以至于现 ...
  • 汝之蜜糖,吾之砒霜——聊聊软件开发中的最佳实践
        "描述一个事物,唯有一个名词定义它的概念,唯有一个动词揭露它的行为,唯有一个形容词表现它的特征.要做的,就是用心去寻找那个名词.那个动词.那个形容词--" -- 福楼拜 (Gustave Flaubert)   ...
  • Python是什么? Python 是一种面向对象的解释型计算机程序设计语言,由荷兰人Guido van Rossum于1989年发明,第一个公开发行版发行于1991年. Python是纯粹的自由软件, 源代码和解释器CPython遵循 G ...
  • 最近在网上看到一部美剧<西部世界>(国内版有删减),感觉拍得不错,里面探讨的话题也正和如今科技和社会的发展主题相吻合,在我看来算是一部佳作吧.         可以一起来探讨一下剧情和人物以及科技与人性相关的未来社会话题.可以看 ...
  • 一. 前言 这里记录了我Blog的所有目录结构,有的项是随笔分类项,有的是具体文章,先把目录写好,以后不断往里面装内容,以后方便整理查阅.当然,主页导航栏可以快速索引到下面的具体项目内容.但是,目前有很多板块还没具体内容更新,待后续接触到相 ...
  • (1) 国际会议 通常,国际上计算机视觉方面的三大国际会议是ICCV, CVPR和ECCV,统称之为ICE. ICCV,International Comference on Computer Vision,国际计算机视觉会议,是公认的三个 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.078 s.
京ICP备10005923号