一维带吸引点的非重叠盒子最优放置算法求解

你描述的问题属于带线性约束的凸优化问题，核心是在满足盒子不重叠的顺序约束下，最小化每个盒子中心点到对应吸引点的距离总和。具体约束可转化为：对于相邻盒子i和i+1，需满足 C_{i+1} ≥ C_i + (w_i + w_{i+1})/2（其中w_i是第i个盒子的宽度），目标函数为 min Σ|C_i - P_i|。

1. 线性规划（LP）求解 #

由于目标函数中的绝对值可通过引入辅助变量转化为线性形式，结合线性的不重叠约束，整个问题可建模为标准线性规划问题：

• 引入非负变量 d_i^+ 和 d_i^-，令 C_i - P_i = d_i^+ - d_i^-
• 目标函数转化为 min Σ(d_i^+ + d_i^-)
• 约束条件：
  • 对所有i：d_i^+ ≥ 0, d_i^- ≥ 0
  • 对所有1≤i<N：C_{i+1} - C_i ≥ (w_i + w_{i+1})/2

可使用成熟的LP求解器（如单纯形法、内点法）直接求解，这类方法能保证找到全局最优解，适合中等规模的N（如N≤10^4）。

2. 投影梯度下降法 #

因为目标函数是凸函数，约束集合是凸集（线性不等式定义的可行域），投影梯度下降是高效的迭代求解方法：

• 每次迭代先对目标函数做无约束梯度下降（梯度为 sign(C_i - P_i)，对应绝对值函数的次梯度）
• 然后将更新后的C_i投影到满足不重叠约束的可行域：通过迭代调整相邻盒子的位置，确保每个C_{i+1}不小于C_i + (w_i + w_{i+1})/2，直到所有约束满足。

这种方法适合大规模N（如N≥10^4），迭代速度快，且容易实现。

3. 链状约束的凸优化专用方法 #

针对这种一维的链状顺序约束（每个变量仅受前一个变量的约束），有专门的高效投影算法，比如通过“前缀调整”来一次性修正所有约束：将初始的C_i序列调整为满足C'_i = max(C_i, C'_{i-1} + (w_{i-1} + w_i)/2)，从左到右遍历一次即可完成投影，配合梯度下降能大幅提升效率。

• 《线性规划导论》：详细讲解线性规划的建模方法、单纯形法与内点法的原理，适合理解LP求解的底层逻辑。
• 《凸优化》（Boyd & Vandenberghe）：系统介绍凸优化理论及各类求解算法，包括投影梯度下降在带线性约束问题中的应用。
• 运筹学领域的“连续变量调度”相关文献：这类研究聚焦于一维空间中带位置约束的目标优化问题，可找到针对此类盒子排列问题的具体推导和优化技巧。

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