algorithm - 在一维（在一条线上）散布/整理点的算法

Question

是否有一种非迭代算法可以在一条线上展开/整理点？

例子：

上线：初始情况。下线：点已分散。

约束：

• 我希望有一个不基于轻推点直到它们稳定的解决方案。换句话说，我更喜欢一种算法，例如，它可以求解一组方程，从而“一次性”计算所有点的新位置。
• 这是一个一维的情况。
• 结果点应该尽可能接近它们的初始位置，但与它的邻居保持一些最小的固定距离。不过，近似值很好。

标签： algorithmlinemathematical-optimizationpoint

Answer 1

基于小型通用数学优化的演示：

• LP/QP 可能会有所不同，因为惩罚的权重不同！
• cvxpy确实免费为我们提供了必要的线性化/重新表述（例如abs）

import cvxpy as cp
import numpy as np
import matplotlib.pyplot as plt

points = np.array([3, 4, 10, 13, 14, 15]) 
min_distance = 2

def solve(quadratic):
  # vars
  x = cp.Variable(points.shape[0])

  # constraints
  constrs = [x[i] - x[i-1] >= min_distance for i in range(1, points.shape[0])]

  # objective
  if not quadratic:
    obj = cp.Minimize(sum(cp.abs(x - points)))
  else:
    obj = cp.Minimize(cp.sum_squares(x - points))

  # setup problem + solve
  problem = cp.Problem(obj, constrs)
  problem.solve()

  return x.value

linear_sol = solve(False)
quad_sol = solve(True)

# visualize
f, (ax0, ax1, ax2) = plt.subplots(3, sharex=True)

colors = [plt.cm.tab10(i) for i in range(points.shape[0])]

ax0.set_title('Input data')
ax1.set_title('linear / abs | LP')
ax2.set_title('quadratic / sum-squares | QP')

for ind, _ in enumerate(points):
  ax0.axvline(points[ind], color=colors[ind])
  ax1.axvline(linear_sol[ind], color=colors[ind])
  ax2.axvline(quad_sol[ind], color=colors[ind])

f.suptitle("Min distance = {}".format(min_distance))
plt.show()

其行为类似于：