[第03章约束推理.pptVIP

史忠植 高级人工智能 高级人工智能 第三章 约束推理 3.1 概 述 3.1 概 述 运筹学的工作步骤 1）提出和形成问题， 2）建立模型， 3）求解， 4）解的检验， 5）解的控制， 6）解的实施。 线性规划问题 例1(广告方式的选择) 中华家电公司推销一种新型洗衣机，有关数据见下表。销售部第一月的广告预算为20000元，要求至少有8个电视商业节目，15家报纸广告；电视广告费不得超过12000元，电台广播至少隔日有一次。现问该公司销售部应当采用怎样的广告宣传计划，才能取得最好的效果? 线性规划问题 线性规划问题 线性规划问题 线性规划问题 求解--单纯形法 将所给问题化为标准形 找出一个初始可行基，建立初始单纯形表 检查所有检验数(若全为非负，则已得到最优解,计算停止。否则继续下一步) 考察是否无解(若是，计算停止，否则继续下一步) 确定入基变量，出基变量 对初始单纯形表进行单纯形变换 3.1 概 述 3.1 概 述 3.1 概 述 3.1 概 述 3.1 概 述 3.1 概 述 CONSTRAINTS约束语言 CONSTRAINTS约束语言 约束逻辑程序设计语言CHIP 面向对象约束语言COPS 面向对象约束语言COPS 常用的算法 算法分析 穷尽有哪些信誉好的足球投注网站方法 穷尽有哪些信誉好的足球投注网站方法 贪 心 法 3.2 回 溯 法 3.2 Backtracking Algorithm Based on depth-first recursive search Approach Tests whether solution has been found If found solution, return it Else for each choice that can be made Make that choice Recur If recursion returns a solution, return it If no choices remain, return failure Some times called “search tree” 3.2 Solution to 8-Queens Puzzle 4-Queens Puzzle 4-Queens Tree 3.2 回 溯 法 3.2 回溯法 3.2 回溯法 3.3 约束传播 3.3 约束传播CONSTRAINT PROPAGATION 3.3 CONSTRAINT PROPAGATION 3.3 CONSTRAINT PROPAGATION 约束传播修改算法 约束传播AC-1算法 约束传播AC-3算法 回跳法Backjumping Backjumping Backjumping 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.11 约束推理系统COPS 3.12 ILOG Solver 3.12 ILOG Solver 3.12 ILOG SOLVER 3.12 ILOG SOLVER ILOG Schedule 1.0 ILOG Schedule 1.0 Scheduling Problem Constraints Constraints Algorithm Program Algorithm Program Algorithm Program Algorithm Program Optimal Solution to the Scheduling Problem //To create a total budget of limited capacity (here 29000). CtDiscreteResource* res = new CtDiscreteResource(schedule, CtRequiredResource, capacity); ? // To state th