xquad 排列(Permutations)模式实战:用 ONEHOTR/ONEHOTC 在 N×N 二元网格上构建置换矩阵

原创2026-10-11 22:38:231,644 阅读

xquad 排列(Permutations)模式实战:用 ONEHOTR/ONEHOTC 在 N×N 二元网格上构建置换矩阵

导读

本文讲解 xquad 约束编程(CP)建模中的排列(Permutations)模式:把 N 个事物分配到 N 个位置上,使每个事物恰好占一个位置、每个位置恰好容纳一个事物。这是旅行商问题(TSP)等"排序 / 逐一访问"类问题的核心骨架。读完本文,你将掌握:如何用 xquad.cp 的 Problem/Domain/Types 声明 N×N 二元网格模型并施加行、列两族 one-hot 约束;如何编译、验证、运行编码器并确认模型展开的系数;以及该模式的变量成本与两类典型失败模式。本文以 cookbook/permutations.md 为骨架,结合仓库源码与测试展开。

一、模式识别:什么时候用排列

排列模式解决的是双射分配问题:N 个事物 ↔ N 个位置,双方都必须被恰好用满。题目中只要出现"顺序"(order)或"每个访问一次"(visit each once)这类字眼——例如一条巡回路线(tour),或者把 N 位客人安排进 N 把椅子——就可以套用本模式。

它与 Assignment(分配)模式 的界限值得一开始就说清:分配模式允许一个槽位容纳多个事物、也允许某些槽位空闲(N 个事物对 B 个槽位,B 不必等于 N);排列模式则要求行列两个方向同时约束死,得到的是一个置换矩阵。cookbook 目录的五种形状总览表把本模式的典型示例指向 examples/tsp/。

二、编码骨架:N×N 二元网格上的两族 one-hot

排列模式的编码是一个 \(N \times N\) 的二元网格:

x[thing, position] = 1  表示 事物 thing 坐在位置 position

约束分两族:

  • ONEHOTR(行 one-hot):每行恰好一个 1,即"这个事物恰好占据一个位置";
  • ONEHOTC(列 one-hot):每列恰好一个 1,即"这个位置恰好容纳一个事物"。

两者合力,才把可行解压成置换矩阵——每行每列恰好一个 1。单独任何一个都无法保证双射。

底层指令:ONEHOTR / ONEHOTC 的系数展开

在 XQVM 指令层面,High-Level Constraints 给出了两者的精确展开。对二元变量(\(x^2 = x\)),ONEHOTR 对行 row 施加:

H+=penalty⋅(∑cxrow,c−1)2H \mathrel{+}= \text{penalty} \cdot \left(\sum_c x_{\text{row},c} - 1\right)^2

展开为:该行每个单元格的线性系数 -penalty,以及该行每对单元格之间的二次系数 +2·penalty。ONEHOTC 对列 col 完全对称:该列每个单元格线性 -penalty,列内每对单元格二次 +2·penalty。

这也是为什么本文第五节的模型系数会是"每单元格 -20、每对 +20"(penalty=10 时线性 -2×penalty、二次 +2×penalty)。值得注意的是,EQUALITY 指令正是 ONEHOTR/ONEHOTC 的一般形式——令所有权重 \(a_k = 1\)、目标 \(b = 1\),展开结果完全相同(见 constraints.md 的 EQUALITY 一节)。

三、纯排列建模:最小可运行示例

剥离掉目标函数后,排列模式本身可以独立成题。下面的 build_problem 来自 cookbook 原文,它分配网格、施加两族 one-hot、并用 colfind 从解中解码排列:

from xquad.cp import Domain, Problem, Types

def build_problem(n: int) -> Problem:
    problem = Problem("PurePermutation")
    num_items = problem.input("num_items", type=Types.Int)
    problem.define_model(size=num_items * num_items, domain=Domain.BINARY,
                          rows=num_items, cols=num_items)

    with problem.range(0, num_items) as row:
        problem.model.apply_onehot_row(row, penalty=10)
    with problem.range(0, num_items) as col:
        problem.model.apply_onehot_col(col, penalty=10)

    perm = problem.output("perm", type=Types.Vec)
    with problem.range(0, num_items) as position:
        perm.append(problem.sample.colfind(col=position, value=1))
    return problem

几个关键 API 的说明(对应 xqcp/problem.py 与 xqcp/symbols.py 的实现):

  • problem.input("num_items", type=Types.Int) 声明一个运行时输入,编译成 INPUT 指令;输入必须在 define_model() 之前声明(input() 内部会检查)。
  • problem.define_model(size=..., domain=Domain.BINARY, rows=..., cols=...) 声明二元域、二维网格。Domain.BINARY 对应 VM 侧的 XQMXDomain.BINARY,编译器据此选择 BQMX 分配指令(见 xqcp/compiler.py 的 _ALLOCATOR 映射:BINARY→BQMX、SPIN→SQMX、INTEGER→XQMX)。rows=/cols= 必须成对给出,否则 define_model 直接抛 ValueError。
  • problem.range(0, num_items) 声明 RANGE 循环,产出循环变量;编译器会把 num_items * num_items 这种自乘折叠成 LOAD + SQR(见 compiler.py 的 _emit_size_expr),比一般乘法更省。
  • model.apply_onehot_row(row, penalty=10) 记录一条 onehot_row action;编译器发射序列为"压入行号 → 压入 penalty → ONEHOTR"(见 compiler.py 的 _emit_onehot_row),列约束对称。
  • problem.sample.colfind(col=position, value=1) 在给定列中找出取值为 1 的行号——即"哪个事物坐在该位置",对应 VM 指令 COLFIND(Python 侧实现见 xqvm_py/executor.py 的 _runner_COLFIND)。

四、编译、验证与运行:完整命令行流程

4.1 编译并验证编码器

把上面的 build_problem(3) 编译成 .xqasm 汇编后,xquad verify --text 会对汇编文本先汇编、再运行完整的字节码验证器(结构、跳转目标、循环嵌套、寄存器类型态、栈深度各阶段,见 xqcli/src/verify.rs):

ok: permutation_encoder.xqasm (29 instructions)

29 条指令,正好覆盖:输入读取、尺寸平方、BQMX 分配、RESIZE 设置网格、两个 RANGE 循环内的 3+3 条 ONEHOTR/ONEHOTC、以及输出段的 colfind 循环。

4.2 在 Rust VM 上运行编码器并求解

用 n = 3 编译,把编码器交给 Rust VM(xqvm crate)执行产出 XQMX 模型,再交给 SolverDWaveCPU(seed=42)求解。由于三个事物的 6 种排列全部能量相同(-60),换一个 seed 会解出不同排列,但下面两行输出始终成立:

decoded permutation (thing at each position): [0, 1, 2]
is a permutation of range(N): True
energy: -60

4.3 用 xquad run 从字节码独立复现模型

xquad run --text ... --calldata 3 直接从汇编字节码、以 calldata 3 确定性重建同一模型,不经过 Python 侧求解流程:

outputs:
  [0] = Model(XqmxModel { domain: Binary, size: 9,
    linear: {0: -20, ..., 8: -20},
    quadratic: {(0, 1): 20, (0, 2): 20, ..., (7, 8): 20}, rows: 3, cols: 3 })

run 子命令的 --text/--calldata/--outputs/--step-limit/--unlimited-steps 等参数定义见 xqcli/src/run.rs;calldata 以逗号分隔传入整数,默认输出槽位 16。

五、模型展开的数学:9 个 -20 与 18 个 +20

n = 3 的纯排列模型精确可数:

  • 9 个线性项 -20:网格共 9 个单元格,每个单元格同时属于一行和一列,因此被 -penalty 累加两次:\(-10 + (-10) = -20\)。这就是 cookbook 原文"每单元格被扣两次 penalty"的来历。
  • 18 个二次项 +20:同行对 3 行 × 每行 \(\binom{3}{2}=3\) 对 = 9 个;同列对同样 9 个,合计 18 个,每个 +2×penalty = +20。

这恰好就是 High-Level Constraints 中 ONEHOTR 与 ONEHOTC 展开公式叠加在同一网格上的结果——没有任何目标项介入。examples/tsp/ 构造的是完全相同的行/列结构,只是在上面叠加了距离系数;排列这一半在目标加入后一个系数都不会变。

顺带一提能量 -60 的由来:6 个 one-hot 约束(3 行 + 3 列)全部满足时,每个约束的激活变量贡献 -10 线性项、同族二次项为 0(同行/同列没有两个 1 同时激活),于是 \(6 \times (-10) = -60\)。XQMX 模型没有常数项字段,满足的约束以 -P 而非 0 形式驻留在模型里——这与 TSP 例子的能量核算(energy = tour_distance - 2·P·n)是同一个机制。

六、与 TSP 的关系:排列是巡回的一半

examples/tsp/ 是仓库中唯一完整体现本模式的示例(examples/tsp/runner.py):x[city, position] = 1 表示城市 city 处于巡回的第 position 个位置,目标把相邻位置城市间的距离叠加到同样的行列 one-hot 对上。其 build_problem 与纯排列版只有两处差异:

  1. 目标段多了一组嵌套循环,用 model.quadratic[(city_i, position), (city_j, next_position)].add(dist) 累加相邻位置距离耦合;
  2. one-hot 的 penalty 取 100(而不是 10),并同样用 colfind(col=position, value=1) 解码出 tour。

运行 uv run python examples/tsp/runner.py --n 4 --seed 42 得到规范输出 tour: <a href="https://link.gitcode.com/i/e642e8fec26e58c702acd880c0b4672a" target="_blank">0, 2, 1, 3]、energy: -650(= 150 - 2×100×4),详见 [TSP 页面。注意:TSP 的"每个城市恰好一个位置、每个位置恰好一个城市"正是排列骨架,而"最短巡回"目标是在合法置换之上的择优——排列约束保证的是合法性而非最优性。

七、成本分析:N² 个变量是真正的开销

排列网格恰好 \(N^2\) 个变量——没有 slack 变量,没有辅助变量,因为 ONEHOTR 和 ONEHOTC 都只是改写已经存在的单元格的系数,从不新分配变量(对比 ATLEAST/REDUCE 等会增长模型尺寸的指令)。这种二次增长就是本模式的真实成本:

要排列的事物数量翻倍,变量数翻四倍——这还是在加任何目标项之前。

N = 10 时网格已 100 个变量,N = 20 时 400 个。相比 Assignment 模式 的 \(N \times B\),排列更贵;但这是"每位置必须恰好一个事物"这一语义的必然代价——删掉列约束得到的不是一个更便宜的排列,而是另一个问题(见下节)。

八、失败模式:两个方向、两类错误

8.1 语义失败:只施加一个轴

只施加 ONEHOTR 而不施加 ONEHOTC(或反之)不会报错,它会静默产出一个更宽松的模型:每个事物仍恰好选一个位置,但没有任何东西阻止两个事物选同一个位置。这个更宽松的规则正是 Assignment 模式,cookbook 原文明确警示:"只约束一个轴"是一种错误,而不是同一个约束的弱化版。反过来,给分配问题误加列 one-hot,也会把"N 个事物进 B 个槽"悄悄变成"事物与槽位的双射",当 \(N \neq B\) 时根本无可行解。

8.2 结构性失败:没有设置网格

ONEHOTR/ONEHOTC 从 RESIZE 设置的网格维度读取行数和列数。如果一个模型从未 RESIZE(rows 和 cols 均为 0),就没有行/列可供约束。两个解释器(Rust 与 Python)都会在需要网格的那条指令处抛 InvalidGridDimensions,而不是"展开成空约束"——这个错误定义见 xqvm/src/error.rs,RESIZE 对非正行列的拒绝逻辑见 xqvm/src/vm.rs(rows <= 0 || cols <= 0 即报错)。

关键结论:xquad verify 捕获不到这个错误。因为网格维度是运行时弹出的栈值(由 calldata 决定),不属于字节码验证器数据流能跟踪的静态信息;失败在编码器运行时(xquad run)才显现,而不是编译时。同理,越界的行/列(如 row >= rows)会抛 IndexOutOfBounds,同样只有运行时才触发。因此调试这类模型时,验证通过 ≠ 运行通过。

提示:xqcp 的 Python 侧还有一道提前防线——apply_onehot_row/apply_onehot_col 要求模型是二维的,否则在 _require_2d(xqcp/symbols.py)处直接抛 ValueError;但"二维却忘了设置网格尺寸"这类情况仍要等运行时才暴露。

8.3 测试佐证

仓库测试 xqcp/tests/test_xqcp.py 中的 test_onehot_row_and_col 直接验证"网格的每一行每一列都必须和为 1":构造 n×n 二元网格、逐行 apply_onehot_row(i, 100)、逐列 apply_onehot_col(j, 100),编译后校验解。它是把本文模式固化成回归测试的参考实现。

九、小结:什么时候选本模式

判断 结论
题目要求"每事物恰一位、每位恰一物"(双射) 用排列模式:N×N 网格 + ONEHOTR + ONEHOTC
只要求每事物选一个槽位,槽位可空可重复 用 Assignment 模式,去掉列约束
需要"每个访问一次"的巡回/排座 排列骨架 + 距离/偏好目标(如 TSP)
模型运行时报 InvalidGridDimensions 检查是否漏了 RESIZE(rows=/cols= 是否传入且非零)

排列模式是 xquad CP 工具链(xqcp DSL → .xqasm 汇编 → XQVM 编码器 → xqsa 求解器 → 验证器/解码器)中最基础的网格结构之一,理解它的系数展开、变量成本与失败语义,是后续组合更复杂问题(TSP、排班、路线规划)的起点。

登录后查看全文
xquad