MultiPatternSolver

English | 中文

多样板分配求解器(PatternChoiceRepair)

这是整个移植里唯一一处超出"移植上游"范畴、反向关闭了上游遗留难题的设计。

问题:贪心单选的天花板

VM 的解析器对每个输出键只解析一条样板(单次产出最小者优先,平局按注册顺序),且从不再回看。当同一产物有多条样板时,贪心选样可能对某个叶子超量需求——报出本可避免的缺料,或得到更差的配比。

参考套件里的 multi-dag/fibonacci/minimum 自上游 v1.9.6 起一直是唯一 FALSE_POSITIVE:该场景存在一个库存配置,使得任何单选择分配都至少缺 1(数学上可证,见下文),只有"这条用样板 A、那条用样板 B"的混合分配才能零缺口。原作评估"移植预算化回溯规划器"为高风险、暂缓;试过的"局部最小叶子代价"启发式也因破坏 greedy-trap 场景而回退。

思路:求解分配,再把拆分编码为数据

求解器(com.ae2vm.vm.PatternChoiceRepair)只在贪心首轮报缺时启动(成功请求零开销),分三步:

第一步:单选择枚举(纯代数,零引擎开销)

把每条候选样板的"每合成消耗输入"(排除催化剂种子等返回物)写成线性需求系统,从根按拓扑级联;对全部争用键(≤12 个)的 2^n 组合做纯代数求值。保留全部并列最优(上限 8 个)作为后续精修起点——哪个最优能长出混合拆分因图而异,单一起点可能每一步局部移动都非改进,必须多路并试。

第二步:拆分权重局部搜索

每个争用键带一个权重向量,其需求数按最大余数法分摊到各候选样板——混合拆分(X3 = 4×A + 1×B)由此可表达。移动规则:

• 在两个候选间转移一个权重单位,或对单一候选加一单位(ADD——从单热点状态表达 4:1 这类配比的关键);
• 等值移动只推进搜索位置(有界防振荡),严格改进才进入解;
• visited 键按行 GCD 规约:权重是配比,等比状态([0,2] 与 [0,1])是同一分配;不规约会被 ADD 移动的无穷等比阶梯耗尽横向预算。

第三步:虚拟样板合成 + 确认门

最优混合权重被合成为一条虚拟样板(VirtualPatternDetails):输入 = Σ 份额×各成分输入,产出 = 合并批量。拆分由此变成纯数据——执行循环、bundle 缓存、聚合、库存感知语义原样工作,引擎零改动。虚拟样板经普通偏好机制交给解析器,然后一次真实重放确认:严格更少总缺失才采纳,否则保留原计划。模型失真只会确认失败,永远不会让结果变差。

效果与数学注脚

• multi-dag/fibonacci/minimum 缺口 4 → 0,三库存模式 39/39 稳定 SUPPORTED(多次全新 JVM 零波动);
• 该场景最优库存 {X0=1, X1=9, X2=11} 由独立穷举证明不可被任何纯单选择分配精确实现(纯最优缺口 1),只能由混合份额 X3 = 4×A + 1×B 精确匹配,且满足恒等式:X0 = B 份额数、X1 = 4 + A + B、X2 = 7 + A;
• 全管线成本:毫秒级纯代数 + 一次确认重放;快路径后 solver 场景 hot 中位 ~3.3ms。

与上游的关系

上游把"预算化回溯规划器"(Thunderbolt 的完整规划器)评估为高风险;本方案不引入回溯规划器,而是证明:只要把"选择"从执行期解耦到求解期,再把解编码为数据,贪心架构同样能到达精确解。逐场景决策链追踪工具 TraceSimulationState 保留在测试源集,接线点见 Ae2VmReferencePlanner 注释。