讲座时间：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:每次选择该比值最小的变量进行赋值

● 基于影响力的启发式、基于活跃度的启发式、基于冲突历史的启发式、失败加权度启发式、基于失败率的启发式......

 

约束求解的搜索策略

最小值域

 

失败加权度变量启发式

 

基于失败的变量启发式（李教授研究）

 

讲座时间：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:每次选择该比值最小的变量进行赋值

● 基于影响力的启发式、基于活跃度的启发式、基于冲突历史的启发式、失败加权度启发式、基于失败率的启发式......

 

约束求解的搜索策略

最小值域

 

失败加权度变量启发式

 

基于失败的变量启发式（李教授研究）