《【新编】高级人工智能之约束推理》由会员分享，可在线阅读，更多相关《【新编】高级人工智能之约束推理（65页珍藏版）》请在金锄头文库上搜索。
1、高级人工智能 第三章 约束推理 史忠植 中国科学院计算技术所 Date1史忠植 高级人工智能 第三章 约束推理 3 1 概述 3 2 回溯法 3 3 约束传播 3 4 回跳法 3 5 约束推理系统COPS 3 6 ILOG SOLVER Date2史忠植 高级人工智能 3 1 概述 最优化问题 经济学所推崇的帕累托最优 几个人拎着水桶在一个水龙头前面排队打水 水 桶有大有小 他们怎样排队 才能使得总的排队 时间最短 这是一个寻求 最优化 的题目 目标 是节省总的排队时间 达到最优 Date3史忠植 高级人工智能 3 1 概述 优化问题 运筹学 遗传算法 神经网络 约束推理 Date4史忠植 高
2、级人工智能 运筹学的工作步骤 v1 提出和形成问题 v2 建立模型 v3 求解 v4 解的检验 v5 解的控制 v6 解的实施 Date5史忠植 高级人工智能 线性规划问题 例1 广告方式的选择 中华家电公司推销 一种新型洗衣机 有关数据见下表 销售部第 一月的广告预算为20000元 要求至少有8电 视商业节目 15家报纸广告 电视广告费不得 超过12000元 电台广播至少隔日有一次 现 问该公司销售部应当采用怎样的广告宣传 计划 才能取得最好的效果 Date6史忠植 高级人工智能 表1 广告方式广告费 用 元 次 可用最 高次数 月 期望的宣 传效果 单位 电视台a 白天 1 分 钟 500
3、1650 电视台b 晚上 30 钞 10001080 每日晨报 半版 1002430 星期日报 半版 300440 广播电台 1分钟 802515 Date7史忠植 高级人工智能 Date8史忠植 高级人工智能 Date9史忠植 高级人工智能 Date10史忠植 高级人工智能 求解 单纯形法 将所给问题化为标准形 找出一个初始可行基 建立初始单纯形表 检查所有检验数 若全为非负 则已得到最 优解 计算停止 否则继续下一步 考察是否无解 若是 计算停止 否则继续 下一步 确定入基变量 出基变量 对初始单纯形表进行单纯形变换 Date11史忠植 高级人工智能 3 1 概述 一个约束满足问题 Con
4、straint Satisfaction Problem 简称CSP 包含一组变量与一组变量间的约束 变量表示领域参数 每个变量都有一个固定的值域 一个变量的值域可能是有限的 例如一个布尔变量的值 域包含两个值 也可能是离散无限的 如整数域 也可 能是连续的 如实数域 x1 x2 xn D1 D2 Dn 4 5 6 7 red green blue Date12史忠植 高级人工智能 3 1 概述 约束可用于描述领域对象的性质 相互关系 任务 要求 目标等 约束 满足问题 的目标就是找到所有 变量的一个 或多个 赋值 使所有约束都得到满足 一元谓词 序关系语言 只包含偏序关系或实变量上的大小关系
5、 形如 x y c 的方程 单位系数的线性方程与不等式 即所有的系数为 1 0 1 任意系数的线性方程与不等式 约束的布尔组合 代数与三角方程 Date13史忠植 高级人工智能 3 1 概述 约束表示易于理解 编码及有效实现 它具有以下优点 约束表示允许以说明性的方式来表达领域知识 表达 能力较强 应用程序只需指定问题的目标条件及数据间 的相互关系 因而具有逻辑表示的类似性质 约束表示允许变量的域包含任意多个值 而不像命题 只取真假二值 所以它保存了问题的一些结构信息 如 变量域的大小 变量间的相关性等 从而为问题求解提供 启发式信息 易于并行实现 因为约束网络上的信息传播可以认为是 同时的
6、适合于递增型系统 约束可以递增式地加入到约束网络 易于与领域相关的问题求解模型相衔接 各种数学规划技 术 方程求解技术等 都可以自然地嵌入约束系统 Date14史忠植 高级人工智能 3 1 约束推理 约束搜索 约束搜索主要研究有限域上的约束满足 对有限域而言 约束满足问题一般情况下 是 一个 NP 问题 约束语言 Date15史忠植 高级人工智能 3 1 约束搜索 回溯法 约束传播 智能回溯与真值维护 可变次序例示 局部修正法 Date16史忠植 高级人工智能 约束语言 CONSTRAINTS CHIP COPS ILOG Date17史忠植 高级人工智能 CONSTRAINTS约束语言 CO
7、NSTRAINTS是一个面向电路描述的约束表示语言 作为一个约束表示语言 它使用了符号处理技术来求解数学方程 在CONSTRAITS中 物理部件的功能及器件的结构都用约束表示 这些约束一般是线性方程与不等式 也包括条件表达式 约束变量 一般是表示物理量的实变量 也有一些取离散值的变量 如开关的状 态 三极管的工作状态等 系统采用表达式推理与值推理 并实现 相关制导的回溯 Date18史忠植 高级人工智能 CONSTRAINTS约束语言 CONSTRAINTS 的一个优点是在类型层次中表示约束 用约束 来表示物理对象的功能与结构 其缺点是该语言缺乏类似于面向 对象语言中的方法那样的成分 不能定义
8、特定于某个类的概念 同时 约束传播方法比较单一 既缺乏实域上的区间传播机制 也缺乏有限域上的 域传播机制 Date19史忠植 高级人工智能 约束逻辑程序设计语言CHIP CHIP Constraint handling in Prolog 就是这样较有影响 一个约束逻辑程序设计语言 其目的是简便 灵活而有效地解决 一大类组合问题 它通过提供几种新的计算域而增强逻辑程序设 计的能力 有限域 布尔项及有理项 对于每个计算域 都提供 有效的约束求解技术 即有限域上的一致性技术 布尔域的布尔 合一技术及有理数域上的单纯型法 除此以外 CHIP还包含一个 一般的延迟计算机制 CHIP 主要应用于两个领域
9、 运筹学与硬件设计 CHIP 缺乏类型机制 而这种机制对于表达领域概念是极其重 要的 Date20史忠植 高级人工智能 面向对象约束语言COPS COPS系统利用面向对象技术 将说明性约束表达与类型层次 结合起来 在形式上吸收了常规语言 主要是面向对象的程序设 计语言的基本形式 内部求解时采用约束推理机制 使说明性约 束表达式与类型层次相结合 实现知识的结构化封装 充分发挥 两者的优点 力图实现一个具有较强表达能力和较高求解效率的 约束满足系统 Date21史忠植 高级人工智能 面向对象约束语言COPS COPS的设计考虑了软件工程的应用要求 尽量将一个不确定问 题确定化 它允许条件语句与循环
10、语句 而不是单 纯以递归的形式来实现迭代计算 通过类方法的重栽实现同一 约束的不同实现 提高了程序的执行效率 COPS系统同时是一个 渐增式的开放系统 用户能通过类型层次定义 实现新的数据类 型和新的约束关系 约束语言COPS具有许多人工智能程序设计语 言的特点 如约束传播 面向目标和数据驱动的问题求解 有限 步的回溯 对象分层中的继承等 Date22史忠植 高级人工智能 在实际应用中 算法的表现形式千变万化 但是算法的情况也和数据结构类似 许多算法 的设计思想具有相似之处 我们可以对它们分 类进行学习和研究 常用的算法大致有如下一些 贪心法 分治法 如二分法检索 回溯法 动态规划法 局部搜索
11、法 分支限界法 Date23史忠植 高级人工智能 算法分析 评价一个程序优劣的重要依据是看这个程序 的执行需要占用多少机器资源 人们最关心的就 是程序所用算法运行时所要花费的时间代价和程 序中使用的数据结构占有的空间代价 算法的空间代价 或称空间复杂性 当被解决 问题的规模 以某种单位计算 由1增至n时 解该 问题的算法所需占用的空间也以某种单位由f 1 增至f n 这时我们称该算法的空间代价是f n 算法的时间代价 或称时间复杂性 当问题规 模以某种单位由1增至n时 对应算法所耗费的时 间也以某种单位由g 1 增至g n 这时我们称算 法的时间代价是g n Date24 史忠植 高级人工智能
12、 穷尽搜索方法 穷尽搜索方法 即产生所有可能的树 然后根据评价标 准选择一棵最优的树 Exhaustive Search Top P where P is a CSP of the form V D C 1 f the null assignment 2 return Exhaustive Search f P Date25史忠植 高级人工智能 穷尽搜索方法 Exhaustive Search f P 1 if f is a total assignment of the variables in P 2 if f satisfies the constraints in P 3 answer
13、 f 4 else 5 answer Unsat 6 else 7 v some variable in P that is not yet assigned a value by f 8 answer Unsat 9 for each value while answer Unsat 10 f v 11 answer Exhaustive Search f P 12 return answer Date26史忠植 高级人工智能 贪心法 贪心法把构造可行解的工作分阶段来完成 在 各个阶段 选择那些在某些意义下是局部最优的 方案 期望各阶段的局部最优的选择带来整体最 优 例 Dijkstra的最
14、短路径算法 Kruskal的求最小 生成树算法 信号灯问题 Date27史忠植 高级人工智能 回溯算法 有些问题需要彻底的搜索才能解决问题 然而 彻底的搜索要以大量的运算时间 为代价 对于这种情况可以通过回溯法来 去掉一些分支 从而大大减少搜索的次数 八皇后问题 迷宫问题 深度优先周游树或图 Date28史忠植 高级人工智能 回溯算法 Backtracking Top P 1 f the null assignment 2 return Backtracking f P Date29史忠植 高级人工智能 回溯算法 Backtracking f P 1 if f is a total assig
15、nment of the variables in P 2 answer f 3 else 4 v some variable in P that is not yet assigned a value by f 5 answer Unsat 6 for each value while answer Umsat 7 f v x 8 if f satisfies the constraints in P 9 answer Backtracking f P 10 return answer Date30史忠植 高级人工智能 回溯算法 尽管回溯法好于生成测试法 但对于非平凡 问题仍然是低效的 其原
16、因在于搜索空间中不同 路径的搜索重复相同的失败子路径 一些研究者 认为 造成这种反复的原因是所谓的局部不一致 性 最简单的情形是所谓的结点不一致性 对一 个变量vi的一个一元约束 存在域中一个值vi不 满足该约束 这样 每当vi取到 a 时就会出现 不一致性 另一种重复的情形 是所谓的弧不一致性 Date31史忠植 高级人工智能 3 3 约束传播 CONSTRAINT PROPAGATION 弧一致性 Arc consistency Date32史忠植 高级人工智能 弧一致性 Arc consistency 如果对vi 的当前域中的所有值x 存在vj的当 前域中的某值y使得 vi x和vj y是vi与vj之间 的约束所允许的 则弧 vi vj 是弧一致的 弧一致性的概念是有向的 即 vi vj 是弧一致的并不自动地意味着 vj vi 是一致 的 Date33史忠植 高级人工智能 3 3 CONSTRAINT PROPAGATION All of the Mackworth algorithms make use of a Revise procedure Let Dv be the c
