获得最小移动以避免方形重叠的算法

Question

我在化学优化程序中遇到的问题与以下问题相同.我找不到一个好的算法:

假设我得到N相同的自由移动具有已知初始经度,固定宽度和具有固定位置的M个相同"障碍"的正方形.

是否有算法可以获得这些方格的"最小"总水平移动:

1. 保留正方形的顺序
2. 导致正方形和障碍物没有重叠("不接触"); 正方形之间没有重叠.

"最小总移动量"通常描述移动之前和之后的位置差异.它可以是偏差的总和,或均方根偏差等,以较容易的为准.

它不必是在最低限度,但近一个需要有一个良好的优化.

我可能有50个方格和25个障碍物,所以蛮力太慢了.

我也找到了这篇文章.但它不适用于固定的障碍物,并不一定保持正方形的顺序.

Answer 1

这感觉是NP 难的（尽管我不确定；证明尝试可能基于对 Bin-packing 的一些减少）。

编辑： 好吧...也许有一个多项式解（对我来说是50/50；我知道这没有多大帮助）。在这种情况下，以下内容将有效，我认为足以有效地解决您的问题，但不确定通过一些通常是 NP 难的代理问题来解决它是否是一个好主意。

您可以通过（混合）整数编程来解决它，它可以用作精确求解器或提供经过验证的近似值。

• 总体思路是引入N个连续变量来标记每个块的左侧位置
• 添加约束，例如：（x_i + L <= x_i+1对于所有连续对；也许更冗余的公式有帮助：对于所有排序对）
  • 这将保持顺序并禁止重叠块
  • x：位置
  • L：长度
• 现在，为了不碰到障碍物，您需要指标约束和一些布尔逻辑：
  • y_i = 1 iff x_i + L <= O_j_s（对于所有 i 对于所有 o；s = 左位置障碍）
  • z_i = 1 iff O_j_e <= x_i + L(e = 右位置)
  • 禁止两者都为真：（y_i + z_i <= 1对于所有我）
  • 指标约束将基于附加的二元变量y, z
• 如果目标是最小化轮班总时间：
  • 目标只是所有块之间的差异之x_i和以及每个块的起始位置：线性目标！
  • 这个绝对值（这是需要的）可以被线性化（无需引入离散变量）；请参阅 lpsolve 关于绝对值的教程
• 如果目标是尽量减少轮班次数：
  • 更多指标约束（已移动<->开始和最终之间的差异> 0）+这些指标变量的总和->线性目标！

这只是一个类似原型的想法。人们必须仔细定义重叠对您意味着什么（包含、排除；然后 StackOverflow 中描述了许多布尔方法：关键字：范围交集）。要制定指标约束，请查找整数编程指南或从此处开始。