史忠植 高级人工智能(中科院)第三章.pdf

高级人工智能
第三章

约束推理

史忠植

中国科学院计算技术研究所
第三章约束推理

3.1概述
3.2回溯法
3.3约束传播
3.4回跳法
3.5约束推理系统COPS
3.6ILOGSOLVER
3.7约束逻辑程序设计

2012-03-08史忠植约束推理2
概述

最优化问题

经济学所推崇的帕累托最优:
几个人拎着水桶在一个水龙头前面排队打水，水
桶有大有小。他们怎样排队，才能使得总的排队
时间最短。这是一个寻求“最优化”的题目，目标
是节省总的排队时间，达到最优。

2012-03-08史忠植约束推理3
概述
优化问题

•运筹学
•遗传算法
•神经网络
•约束推理

2012-03-08史忠植约束推理4
运筹学的工作步骤

1）提出和形成问题，
2）建立模型，
3）求解，
4）解的检验，
5）解的控制，
6）解的实施。

2012-03-08史忠植约束推理5
线性规划问题

例1(广告方式的选择)中华家电公司推销一种
新型洗衣机,有关数据见下表.销售部第一月的
广告预算为20000元,要求至少有8电视商业节
目,15家报纸广告/电视广告费不得超过12000
元,电台广播至少隔日有一次.现问该公司销售
部应当采用怎样的广告宣传计划,才能取得最
好的效果?

2012-03-08史忠植约束推理6
表1

广告方式广告费可用最期望的宣
用(元/高次数/传效果/单
次)月位
电视台a(白天,1分5001650
钟)
电视台b(晚上,30钞)10001080
每日晨报/(半版)1002430
星期日报/(半版)300440
广播电台/(1分钟)802515

2012-03-08史忠植约束推理7
线性规划问题

解:设x1,x2,x3,x4,x5分别是第一个月内电视台a,电视台
b,每日晨报,星期日报,广播电台进行广告宣传的次数,则
其数学模型为:

max50x1+80x2+30x3+40x4+15x5

500x1+1000x2+100x3+300x4+80x5≤20000,

x1+x2≥8,

x3+x4≥15,

500x1+1000x2≤12000,

s.t.x1≤16,x2≤10,x3≤24,x4≤4,15≤x5≤25,

x1,x2,x3,x4,x5≥0.

2012-03-08史忠植约束推理8
线性规划问题

…,n
2012-03-08史忠植约束推理9
线性规划问题
线性规划问题的标准形式为:
minz=CTX

AX=b
s.t.X≥0(假定b为非负)
注:任何形式的线性规划问题均可化为
标准型

2012-03-08史忠植约束推理10
求解--单纯形法

将所给问题化为标准形
找出一个初始可行基,建立初始单纯形表
检查所有检验数(若全为非负,则已得到最优解,
计算停止.否则继续下一步)
考察是否无解(若是,计算停止,否则继续下一步)
确定入基变量,出基变量
对初始单纯形表进行单纯形变换

2012-03-08史忠植约束推理11
约束满足问题CSP

.Given:
(1)setofvariables,
(2)domainsofthevariables
(3)constraintsthatthevariableshavetosatisfy

.Find:
Anassignmentofvaluestothevariables,
sothatthesevaluessatisfyallthegivenconstraints.

.Inoptimisationproblems,alsospecifyoptimisation
criterion
2012-03-08史忠植约束推理12
概述
一个约束满足问题(ConstraintSatisfaction
Problem,简称CSP)包含一组变量与一组变量间的约
束。
▪变量表示领域参数，每个变量都有一个固定的值
域。一个变量的值域可能是有限的，例如一个布尔变
量的值域包含两个值；也可能是离散无限的，如整数
域；也可能是连续的，如实数域。
{x1,x2,…xn},
{D1,D2,…Dn},.
{4,5,6,7}
{red,green,blue}

2012-03-08史忠植约束推理13
概述

▪约束可用于描述领域对象的性质、相互关系、任务
要求、目标等。约束满足问题的目标就是找到所有
变量的一个（或多个）赋值，使所有约束都得到满足。
•一元谓词。
•序关系语言，只包含偏序关系或实变量上的大小关系。
•形如“x-y>c”的方程。
•单位系数的线性方程与不等式，即所有的系数为
-1,0,1。
•任意系数的线性方程与不等式。
•约束的布尔组合。
•代数与三角方程。
2012-03-08史忠植