讲座时间：2024年7月24日
讲座组织：中国计算机学会
主讲人：李宏博 副教授
问题实例
经典问题实例：n皇后问题
在一个n * n的国际象棋棋盘上，放置n个皇后，使得任意两个皇后之间不能互相攻击。横向、纵向、对角线、反对角线只能有一个皇后。
一般来说，手工求解，4皇后可以解出来；8皇后费点力气也可以解出来；但是100皇后基本上就无法手动求解了。
解决方法基本上就是一个个试。
经典问题实例：旅行商问题
给定n个城市和任意两个城市之间的距离，寻找一种周游方案从某个城市出发，最终回到这个城市，并且每个城市经过一次，使得旅行的总距离最短。
如何解决这个问题?
● 尝试所有的可能性
● n!种可行方案
● 在距离矩阵中每次选择距离最近的两个城市连接?
○ 012430距离37
○ 014230距离23
以上两个问题如何用同一套算法进行解决？
— —约束程序设计
约束程序设计
传统的程序设计
● 为解决某些特定问题，使用程序设计语言告诉计算机算法的每一个执行步骤。
● 计算机执行程序，解决问题。
高级的约束程序设计
● 为解决某些特定问题，使用约束程序设计语言（建模）告诉计算机待解决的问题描述
● 计算机调用约束求解器来求解所描述的问题。
约束程序设计优点：
● 问题描述能力强:现有约束求解器可提供多种多样的约束类型。
● 约束程序设计是求解离散组合搜索问题的通用方法。
● 使用约束程序设计解决离散组合搜索问题，用户只关注如何将问题描述告诉计算机，即用户只关注问题建模。
● 用户建模完成后，求解器进行自动求解。求解器的求解算法是由科研人员进行设计研究，即科研人员主要关注约束求解算法。
求解算法
● 完备算法(也叫精确算法)
○ 回溯搜索:求解约束满足问题
○ 分支限界搜索:求解约束优化问题
● 非完备算法:主要使用启发式方法求解约束优化问题
○ 贪婪搜索
○ 局部搜索
○ 智能计算方法:遗传算法、蚁群算法......
注：完备算法与非完备算法互补
完备算法 VS 非完备算法
● 完备算法
○ 约束满足问题
■ 若有解，算法终止时可找到可行解
■ 若无解，算法终止时可证明无解。
○ 约束优化问题
■ 算法终止时可找到最优解，并且证明解的最优性。
○ 算法可能无法在有效时间内终止
● 非完备算法:主要解决约束优化问题
○ 可能快速找到一个高质量解，甚至是最优解
○ 无法保证一定找到最优解，无法证明解的最优性
○ 当优化问题约束比较复杂，可行解难找，非完备算法可能无法找到可行解
对比来看，非完备算法可以找一个高质量的解，但不一定是最优解。那么如果找到最优解一定是使用完备算法，但是完备算法无法在有效时间终止的问题，如何解决呢？个人认为简单粗暴的一点，提高算力即可。比如说用传统计算机需要计算24个小时，用量子计算机的超高算力，可能毫秒级就可以出来结果。
分支限界搜索 与 向溯搜索
● 分支限界搜索
1. 先调用回溯搜索找到一个可行解S0，然后在问题中添加一个约束，使得下一个可行解的优化目标比obj(S0)更好;
2. 寻找新的可行解，重复1过程，直到某次更新上界后没有找到可行解;
3. 最后一次找到的可行解即是最优解。
● 举例说明旅行商问题
1. 不考虑优化目标，找一个可行方案S0，obj(So)=100
2. 加入约束条件，令obj<100，寻找下一个可行方案，得S1，obj(S1)=90。
3. 加入约束条件，令obj<90，寻找下一个可行方案Si:
4. 若有可行方案，重复3，若无可行方案，则上一个Si是最优解
约束满足问题
约束
全局约束举例
约束程序设计（8皇后问题）
约束传播
● 用户建模后的约束满足问题，有d"种可能的取值组合，其中n是变量个数，d是变量的值域大小。
● 回溯搜索算法本质上是穷举所有取值组合
● 约束传播算法通过推理对搜索过程进行剪枝，减少需探索的组合数。
约束传播与局部相容
四皇后问题穷举搜索树
四皇后问题的回溯搜索过程
约束求解
约束求解的核心技术
● 搜索策略
○ 理想情况下，每次为变量赋值时，恰好选到在解中的那个赋值
● 约束传播算法
○ 约束传播算法的剪枝能力
○ 约束传播算法本身的实现代价
● 冲突记录
● 重启搜索
搜索策略-失败优先原则
失败优先原则:尽量选择最有可能导致失败的变量进行赋值
● 最小值域(dom):每次选择值域最小(候选值最少)的变量进行赋值
● 最大度(deg):每次选择连接约束最多的变量进行赋值
● dom/deg:每次选择该比值最小的变量进行赋值
● 基于影响力的启发式、基于活跃度的启发式、基于冲突历史的启发式、失败加权度启发式、基于失败率的启发式......
约束求解的搜索策略
最小值域
失败加权度变量启发式
基于失败的变量启发式（李教授研究）
