24/12/23史忠植高级人工智能1高级人工智能第三章约束推理AdvancedArtificialIntelligenceAdvancedArtificialIntelligence史忠植中国科学院计算技术研究所24/12/23史忠植高级人工智能2第三章约束推理3.1概述3.2回溯法3.3约束传播3.4回跳法3.5约束推理系统COPS3.6ILOGSOLVER24/12/23史忠植高级人工智能33.1概述最优化问题经济学所推崇的帕累托最优:几个人拎着水桶在一个水龙头前面排队打水，水桶有大有小。他们怎样排队，才能使得总的排队时间最短。这是一个寻求“最优化”的题目，目标是节省总的排队时间，达到最优。24/12/23史忠植高级人工智能43.1概述优化问题运筹学遗传算法神经网络约束推理24/12/23史忠植高级人工智能5运筹学的工作步骤1）提出和形成问题，2）建立模型，3）求解，4）解的检验，5）解的控制，6）解的实施。24/12/23史忠植高级人工智能6线性规划问题例1(广告方式的选择)中华家电公司推销一种新型洗衣机，有关数据见下表。销售部第一月的广告预算为20000元，要求至少有8个电视商业节目，15家报纸广告；电视广告费不得超过12000元，电台广播至少隔日有一次。现问该公司销售部应当采用怎样的广告宣传计划，才能取得最好的效果?24/12/23史忠植高级人工智能7线性规划问题广告方式广告费用(元/次)可用最高次数/月期望的宣传效果/单位电视台a(白天,1分钟)5001650电视台b(晚上,30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)802515表1中华家电公司推销新型洗衣机广告方式选择的数据表24/12/23史忠植高级人工智能8线性规划问题解：设x1,x2,x3,x4,x5分别是第一个月内电视台a，电视台b，每日晨报，星期日报，广播电台进行广告宣传的次数，则其数学模型为max50x1+80x2+30x3+40x4+15x5s.t.50x1+80x2+30x3+40x4+15x5≤20000，x1+x2≥8，x3+x4≥15，500x1+1000x2≤12000，x1≤16,x2≤10,x3≤24,x4≤4,15≤x5≤25,x1,x2,x3,x4,x5≥0。24/12/23史忠植高级人工智能9线性规划问题线性规划问题(LP)的一般形式为：min(max)zc1x1c2x2…cnxns.t.a11x1+a12x2+…+a1nxn≤(≥,＝)b1a21x1+a22x2+…+a2nxn≤(≥,＝)b2…am1x1+am2x2+…+amnxn≤(≥,＝)bmxj≥0,j1,2,…,n24/12/23史忠植高级人工智能10线性规划问题线性规划问题的标准形式为：minXCzT注：任何形式的线性规划问题均可化为标准型。AXbs.t.X≥0(假定b为非负)24/12/23史忠植高级人工智能11求解--单纯形法将所给问题化为标准形找出一个初始可行基，建立初始单纯形表检查所有检验数(若全为非负，则已得到最优解,计算停止。否则继续下一步)考察是否无解(若是，计算停止，否则继续下一步)确定入基变量，出基变量对初始单纯形表进行单纯形变换24/12/23史忠植高级人工智能123.1概述一个约束(Constraint)通常是指一个包含若干变量的关系表达式，用以表示这些变量所必须满足的问题。▪约束表示广泛地应用于人工智能的各个领域，包括定性推理、机械与电子设备的设计与分析等。▪约束满足系统的设计是一项困难而复杂的任务，因为约束满足问题在一般情况下是一个NP(Nonpolynomia)问题，所以必须使用各种策略与启发式信息。24/12/23史忠植高级人工智能133.1概述一个约束满足问题(ConstraintSatisfactionProblem,简称CSP)包含一组变量与一组变量间的约束。▪变量表示领域参数，每个变量都有一个固定的值域。一个变量的值域可能是有限的，例如一个布尔变量的值域包含两个值；也可能是离散无限的，如整数域；也可能是连续的，如实数域。{x1,x2,…,xn},{D1,D2,…,Dn},.{4,5,6,7}{red,green,blue}24/12/23史忠植高级人工智能143.1概述▪约束可用于描述领域对象的性质、相互关系、任务要求、目标等。约束满足问题的目标就是找到所有变量的一个（或多个）赋值，使所有约束都得到满足。▪现有的约束表示可分为几类，按复杂性的次序列举如下：一元谓词。序关系语言，只包含偏序关系或实变量上的大小关系。形如“x-y>c”或“x-y≥c”的方程。单位系数的线性方程与不等式，即所有的系数为-1,0,1。任意系数的线性方程与不等式。约束的布尔组合。代数与三角方程...
