问题描述
《终末地》 1.4 版本新增浮空回收玩法。一级问题都简单，但是二、三级有些还挺难
场景是：一个货物需要绑上热气球浮空回收。升空既有总浮力要求，也有平衡要求
货物被分成 5x5 的格子，给定浮力为 1~6 的不同数量的气球，要求在格子上放置完所有气球的情况下，使整块面板达到平衡
平衡分为上下平衡和左右平衡，不同格子浮力倍率不同，越远离中心的格子，倍率越高。最外圈 16 格每个格子浮力倍率是 2，内圈 8 格每个格子倍率是 1，中心 1 格倍率是 0
以下图为例，这是不平衡的状态
- 上下平衡： 第 1 行总数是 9，得到 9 x 2 的上倾斜量，第 4 行总数是 6，有 6 x 1 的下倾斜，因此累计 18 - 6 = 12，有 12 的上倾斜量
- 左右平衡： 第 3 列总数是 6，因为位于中线，没有倾斜量，第 5 列总数是 9，有 9 x 2 = 18，因此有 18 的右倾斜量
再看一个例子，这是平衡的状态
- 上下平衡： 第 2 行上倾斜量 11，第 4 行下倾斜 9，第 5 行写倾斜 1 x 2 = 2，忽略第 3 行，11 - 9 + 2，因此上下平衡
- 左右平衡： 第 1 列左倾 2，第 2 列左倾 9，第 4 列右倾 11，忽略第 3 列，11 = 9 + 2，因此左右平衡
分析解决
一开始我以为用方程组求解就行了，后面发现方程组解决不了每个谜题不同气球型号的数量限制问题。所以转向运筹学方法
设 5x5 的重量矩阵 A，记录每个格子上的气球重量
记
$$ w = [-2, -1, 0, 1, 2] $$
$$ I = [1, 1, 1, 1, 1]^T $$
那么，
上下平衡可表示成：
$$ wAI = 0 $$
左右平衡可表示成：
$$ wA^TI = 0 $$
一共有 6 种重量的气球，每种气球数量有限制。直接用矩阵 A 做决策变量是有困难的，考虑做独热编码，把决策要素拼凑成 A
对于每个单元格 (i,j) 和每个可能的取值 k∈{0,1,2,3,4,5,6}，定义 5x5x7 的逻辑矩阵 P：
$$ P_{ijk} = \begin{cases} 0 \qquad 不放置重量为\:k\:的气球 \\ 1 \qquad 放置重量为\:k\:的气球 \end{cases} $$
互斥性约束： 考虑每个位置上只能放一种重量的气球，因此：
$$ \sum_{k=0}^6 P_{ijk} = 1\quad(i=1..5,j=1..5) $$
地图约束： 考虑每个谜题，不是每个位置都能放气球，因此：
$$ P_{ij0} = 1 \quad (i, j 是所有不能放气球的位置) $$
至此，重量矩阵 A 拼图已成，可表示成：
$$ A_{ij} = \sum_{k=1}^6 kP_{ijk} \quad (i=1..5,j=1..5) $$
数量约束： 假设重量为 k 的气球数量限制为 c_k
此限制可表示为：
$$ \sum_{i=1}^5\sum_{j=1}^5 P_{ijk} = c_k \quad (k=1..6) $$
至此，问题所有要素分析完成。把它输入 lingo，求可行解即可
编写代码
上面分析中，发现重量矩阵 A 虽然直观，但对整个流程并不必须，可以把平衡条件优化为：
上下平衡：
$$ \sum_{i=1}^5 w_i \sum_{j=1}^5\sum_{k=1}^6 kP_{ijk} = 0 $$
左右平衡：
$$ \sum_{j=1}^5 w_j \sum_{i=1}^5\sum_{k=1}^6 kP_{ijk} = 0 $$
按上面的 0-1 公式，编写 LINGO 代码如下（只需修改 DATA 段里的 C（各重量气球数量）和 B（禁止格）即可求解任意谜题）：
MODEL:
SETS:
IDX /1..5/ : W; ! 权重向量（行/列通用）
K /0..6/; ! 每个格子的取值：0=空，1..6=气球重量
KW /1..6/ : C; ! 每种重量的气球数量限制
CELL (IDX,IDX) : B; ! B(i,j)=1 表示该格禁止放气球
CELLK(CELL,K) : P; ! P(i,j,k)=1 表示 (i,j) 放重量 k（k=0 表示空）
ENDSETS
DATA:
! 权重向量
W = -2 -1 0 1 2;
! 各重量气球数量 c_1..c_6，按实际修改
C = 2 3 4 0 0 0;
! 地图 B(i,j)：1=禁止格，不能放气球，0=可放气球，按实际修改
B = 1 0 0 0 1
0 1 0 0 0
0 0 0 0 0
0 1 0 1 1
0 1 0 0 1;
ENDDATA
! 常数目标：占位用
MIN = 0;
! 互斥性：每个格子只能放一种重量的气球，或者不放气球
@FOR(CELL(I,J):
@SUM(K(K0): P(I,J,K0)) = 1
);
! 地图约束：禁止格不能放气球
@FOR(CELL(I,J):
P(I,J,0) >= B(I,J)
);
! 数量约束：每种重量的气球数量恰好用完
@FOR(KW(K):
@SUM(CELL(I,J): P(I,J,K)) = C(K)
);
! 上下平衡
@SUM(IDX(I):
W(I) * @SUM(IDX(J):
@SUM(KW(K): K * P(I,J,K))
)
) = 0;
! 左右平衡
@SUM(IDX(J):
W(J) * @SUM(IDX(I):
@SUM(KW(K): K * P(I,J,K))
)
) = 0;
! 限制 P(i,j,k) 为 0-1 整数
@FOR(CELLK(I,J,K): @BIN(P(I,J,K)));
END
P(i,j,k) 就是 P_{ijk}
三条 @FOR 分别对应互斥、地图、数量约束，两条 @SUM 对应平衡约束
基于 LINGO 代码的 JS 实现
根据上面的 LINGO 模型，可用 js 做求解器网站。
前端界面的交互部分由 AI 完成，求解算法使用 javascript-lp-solver 库实现
lingo 代码转译为 js，效率虽然低了，但好处是可以免除后端，一个 <script> 就能引入，纯前端运行
求解器网站：https://balloon.simenchan.xyz
实际验证
第 1 问
地图： 中心九宫格不可用
气球： 6 号气球 2 个，3 号 2 个，2 号 3 个，1 号 1 个
抽象为下图
点击求解
第 2 问
地图： 右上箭头形状外格子都不可用
气球： 6 号气球 2 个，3 号气球 4 个，1 号气球 3 个
抽象为下图
点击求解
补充：4×4 与 6×6 的情况
实测发现游戏里实际还有 4×4 和 6x6 的浮空问题，所以给模型补上了 4×4 / 6×6 两种尺寸
改造方式非常简单：只需要换权重向量和维度上限 即可
一、替换 5x5 的 w = [-2, -1, 0, 1, 2]（原模型）为：
- 4×4：
w = [-2, -1, 1, 2] - 6×6：
w = [-3, -2, -1, 1, 2, 3]
二、把集合 IDX 的维数从 5 改成 4 或 6，IDX /1..4/（或 /1..6/）
其余逻辑全部复用，界面加一个棋盘尺寸下拉即可
补充测试
第 3 问
地图： 除中心四格，外围一圈都可放气球
气球： 1 个 6 号，2 个 3 号，2 个 2 号，6 个 1 号
抽象为下图
求解得到
暂无评论