高效最小化有理线性分式函数：求最小正值的快速算法

给定实常数 $a_i, b_i$，求所有 $s_i \in {+1, -1}$ 时，函数
$$f(s_1,...,s_n) = \left| \frac{\sum_{i=1}^n s_i a_i}{\sum_{i=1}^n s_i b_i} \right|$$
的最小正值。暴力枚举所有 $2^n$ 种组合的时间复杂度为 $O(n \cdot 2^n)$，以下是更高效的解法思路及问题检索方向：

一、高效算法方案 #

1. 分治算法（Meet-in-the-Middle） #

这是对中等规模 $n$（如 $n \leq 40$）最实用的优化方法，时间复杂度可降至 $O(2^{n/2} \cdot n)$：

• 将变量拆分为前后两组（各约 $n/2$ 个），分别枚举两组所有 $2^{n/2}$ 种符号组合，计算每组对应的 $A = \sum s_i a_i$ 和 $B = \sum s_i b_i$，存储为二元组集合 $S_1 = {(A_1, B_1)}$ 和 $S_2 = {(A_2, B_2)}$。
• 对 $S_1$ 中的点按斜率 $A/B$ 排序（跳过 $B=0$ 的情况）。
• 遍历 $S_2$ 中的每个点 $(A_2, B_2)$，我们需要在 $S_1$ 中找到点 $(A_1, B_1)$，使得 $\left| \frac{A_1+A_2}{B_1+B_2} \right|$ 最小且 $B_1+B_2 \neq 0$。这等价于寻找与点 $(-A_2, -B_2)$ 连线斜率绝对值最小的点，可通过二分查找在排序后的 $S_1$ 中快速定位候选点，计算并记录最小比值。

2. 子集和转化与动态规划（针对整数系数场景） #

若 $a_i, b_i$ 为整数，可将问题转化为子集和问题：

• 令 $t_i = \frac{1+s_i}{2} \in {0,1}$，则 $\sum s_i a_i = 2\sum t_i a_i - \sum a_i$，$\sum s_i b_i = 2\sum t_i b_i - \sum b_i$。
• 问题变为：对所有可能的子集和 $S_b = \sum t_i b_i$（对应 $\sum s_i b_i = 2S_b - \sum b_i \neq 0$），计算对应的 $S_a = \sum t_i a_i$，并求 $\left| \frac{2S_a - \sum a_i}{2S_b - \sum b_i} \right|$ 的最小值。
• 可使用动态规划预计算所有可能的 $S_b$ 及其对应的最小/最大 $S_a$，再遍历所有有效 $S_b$ 计算比值，时间复杂度取决于子集和的范围。

3. 连续放松+局部搜索（大规模场景近似解） #

当 $n$ 很大（如 $n > 50$），精确求解成本过高，可采用近似方法：

• 先将 $s_i$ 放松为连续变量 $s_i \in [-1,1]$，求解非线性优化问题：最小化 $\left| \frac{\sum s_i a_i}{\sum s_i b_i} \right|$（约束 $\sum s_i b_i \neq 0$），可通过拉格朗日乘数法、梯度下降等数值方法求解。
• 将连续解离散化为 $s_i \in {+1,-1}$，再进行局部搜索（如逐个翻转 $s_i$ 的符号，若能减小比值则保留），快速得到近似最优解。

二、问题检索方向 #

该问题属于组合优化中的符号选择问题，可通过以下关键词检索相关研究：

• 核心关键词：sign selection problem rational function minimization
• 关联方向：subset ratio optimization（子集比值优化）、binary variable ratio minimization（二元变量比值最小化）

可在Google Scholar、IEEE Xplore等学术数据库，或Stack Overflow、Math Stack Exchange等论坛中使用上述关键词查找已有的算法或理论结果。

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