约束推理(ppt).pptVIP

史忠植 高级人工智能 高级人工智能 第三章 约束推理 概 述 概 述 运筹学的工作步骤 1）提出和形成问题， 2）建立模型， 3）求解， 4）解的检验， 5）解的控制， 6）解的实施。 线性规划问题 例1(广告方式的选择)中华家电公司推销一种新型洗衣机,有关数据见下表.销售部第一月的广告预算为20000元,要求至少有8电视商业节目,15家报纸广告/电视广告费不得超过12000元,电台广播至少隔日有一次.现问该公司销售部应当采用怎样的广告宣传计划,才能取得最好的效果? 表1  求解--单纯形法 将所给问题化为标准形 找出一个初始可行基,建立初始单纯形表 检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步) 考察是否无解(若是,计算停止,否则继续下一步) 确定入基变量,出基变量 对初始单纯形表进行单纯形变换 概 述 概 述 概 述 约束推理 约束有哪些信誉好的足球投注网站 约束语言 CONSTRAINTS约束语言 CONSTRAINTS约束语言 约束逻辑程序设计语言CHIP 面向对象约束语言COPS 面向对象约束语言COPS 穷尽有哪些信誉好的足球投注网站方法 穷尽有哪些信誉好的足球投注网站方法 贪心法 贪心法把构造可行解的工作分阶段来完成。在各个阶段，选择那些在某些意义下是局部最优的方案，期望各阶段的局部最优的选择带来整体最优。 例：Dijkstra的最短路径算法、Kruskal的求最小生成树算法、信号灯问题 回溯算法 有些问题需要彻底的有哪些信誉好的足球投注网站才能解决问题，然而，彻底的有哪些信誉好的足球投注网站要以大量的运算时间为代价，对于这种情况可以通过回溯法来去掉一些分支，从而大大减少有哪些信誉好的足球投注网站的次数。 八皇后问题 迷宫问题 深度优先周游树或图 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” Solution to 8-Queens Puzzle 4-Queens Puzzle 4-Queens Tree 回溯算法 回溯算法 回溯算法 3.3 约束传播CONSTRAINT PROPAGATION 弧一致性 3.3 CONSTRAINT PROPAGATION CONSTRAINT PROPAGATION 约束传播修改算法 AC-1 AC-3 Backjumping Backjumping Backjumping COPS COPS COPS COPS COPS COPS COPS COPS COPS COPS ILOG SOLVER ILOG SOLVER ILOG SOLVER ILOG Schedule 1.0 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 schedule with origin 0 and given horizon. CtSchedule* schedule = new CtSchedule(0, horizon); ? // To create an activity with the given duration. CtIntervalActivity* act = new CtIntervalActivity(schedule, duration); ? //To post a precedence constrai