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

Question

我在化学优化程序中遇到了一个等价于以下问题的问题。我找不到适合它的算法:

假设我有 N 个相同的自由移动方 block ，这些方 block 具有已知的初始经度、固定宽度和 M 个具有固定位置的相同“障碍物”。

是否有一种算法可以使这些方 block 的“最小”总水平运动能够:

1. 保留正方形的顺序
2. 导致方 block 和障碍物不重叠(“不接触”)；并且没有重叠 正方形之间。

“最小总移动量”一般描述移动前后的位置差。可以是偏差之和，也可以是均方根偏差等，取较容易的。

它不一定是 最小值，但需要一个接近的值才能进行良好的优化。

我可能有多达 50 个方 block 和 25 个障碍物，所以蛮力太慢了。

我还找到了 this post .但它不适用于固定的障碍物，也不一定保持方格的顺序。

Answer 1

O(|sq|^2 * |ob|) 一般复杂度。

ob = [1, 5, 6, 7, 10, 13]
sq = [-3, 0, 3, 6, 8, 14]

令 f(i, j) 代表最佳解决方案，其中 sq[i] 的正方形必须适合障碍物的左侧，ob[j ]。求解 f(i, 0) 以打包 1,2,3...50 个正方形，其中正确的障碍物是 ob[0]。然后，扩展到障碍物ob[1]，解决方案将是

f(i, 1) = min(
  f(k, 0) + cost of placing squares sq[k+1...i] between ob[0] and ob[1]
)
for all k

对每个 j 进行跟进。