Conditional Constraint Solving：千级变量约束优化专用算法咨询

这个问题的约束结构、变量取值域、优化目标的特殊性极强，完全没必要用通用约束求解器或者整数规划求解器，用基于单调闭包传播的线性时间贪心算法就能做到毫秒级求解，哪怕是数千变量、十万级约束的规模也毫无压力，具体实现逻辑如下：

核心思路 #

所有变量只能取1-4四个整数，所有约束都是单调的序关系、阈值判断，优化目标只统计取值为3的变量——1、2、4三个取值都不贡献目标计数，所以算法核心就是优先给变量分配不产生3的取值，用BFS做约束闭包传播，只有完全没有非3选项的时候才给变量赋3，彻底避免通用求解器分支、回溯的额外开销。

具体实现步骤 #

• 预处理建图
  给每个变量维护上下界数组low[i]、high[i]，初始分别设为1、4，同时建三个邻接表存约束关系：
  • le[i]：存所有满足x[i] <= x[j]的j，逻辑是i的取值升高时，j的下界必须同步抬升
  • ge[j]：存所有满足x[i] <= x[j]的i，逻辑是j的取值降低时，i的上界必须同步压低
  • cond[i]：存所有满足条件约束“若x[i]>=2则x[j]>=3”的j，逻辑是i的取值到2及以上时，j的下界必须抬到3以上
• 初始硬约束传播
  先把题目给的所有固定上下界约束（C<=x[i]、x[i]<=C）对应更新low[i]、high[i]，把所有发生更新的变量加入BFS队列，按以下规则传播到队列为空：
  1. 出队变量i如果是下界更新，遍历le[i]里的所有j，把low[j]更新为max(low[j], low[i])，如果low[j]变大就把j入队
  2. 出队变量i如果是上界更新，遍历ge[i]里的所有j，把high[j]更新为min(high[j], high[i])，如果high[j]变小就把j入队
  3. 传播中如果发现任意变量low[i] > high[i]，直接判定问题无解
  4. 如果任意变量i的low[i] >=2，遍历cond[i]里的所有j，把low[j]更新为max(low[j], 3)，如果low[j]变大就把j入队
     这一步跑完，所有被硬约束卡死的取值范围都会计算完成，此时如果有变量满足low[i]==3 && high[i]==3，直接计入最终的3值计数。
• 贪心赋值传播
  维护候选队列，把所有还没被固定取值（low[i] < high[i]）的变量按规则入队处理：
  1. 优先处理能取1、2的变量：只要low[i] <=2，就给变量赋当前能取到的最小非3值（能赋1就赋1，否则赋2），赋值后固定low[i]=high[i]=对应取值，入队按初始传播的规则做闭包传播，传播中触发新的固定取值就同步处理
  2. 其次处理下界已经到3的变量：如果low[i]==3且high[i]>=4，直接给变量赋4，固定low[i]=high[i]=4后入队传播，这个取值不会贡献目标计数，还能避免变量后续被赋3
  3. 每次队列清空后如果还有未赋值的变量，说明这个变量已经没有非3选项（low[i]=3 && high[i]=3），计数加1，固定取值后入队传播，循环直到所有变量处理完成

性能说明 #

整个算法时间复杂度是严格的O(N+M)，N是变量数，M是约束数，没有递归、回溯逻辑，常数极小，哪怕是上万变量、十万级约束的规模也能在几毫秒内跑完，完全满足高性能要求。

内容的提问来源于stack exchange，提问作者alex137