python - 通过抬高腿在中点连接一系列桥梁

Question

过去几周我一直在努力解决与我正在从事的个人项目相关的问题。我尝试了几种不同的方法，但它们似乎都没有给我我正在寻找的结果，所以我希望这里有人可以帮助我至少指出正确的方向。
情况:我想 build 一系列桥梁，这些桥梁将连接在每座桥梁之间的中点。我得到了地面的地形和将作为桥腿的柱子。 (每座桥有 2 条腿来支撑它上面的道路)。腿站立的地面不一定是平坦的，因此每座桥的腿之间的角度会有所不同。如果我在每座桥的腿上放一条路，由于桥的角度和腿的相对高度不同，当道路放在桥上时，道路可能不一定与道路相连它将建在以下两座桥之间的中点的桥上。因此，我可以在一组边界内抬起任何/所有桥腿，以使位于桥腿顶部的每条道路在桥腿之间的中点处与相邻道路相连。桥梁。 (道路延伸超出桥腿并终止于任何相邻桥梁之间的中点)
示例:我有一个沿 x 轴放置桥腿的点列表:x = [0, 200, 300, 500, 600, 800] (桥的每条腿之间的距离是 200，从桥的第二条腿到相邻桥的第一条腿的距离是 100。桥 1 将靠在位于 0 和 200 个单位的腿上，桥 2 将靠在 300 和 500 个单位的腿上，等等......道路应该在桥梁 1 和 2 之间连接的中点位于 250 个单位)。
我也知道桥腿的基础高度位于以下高度:y = [6, 1, 6, 9, 9, 12]高于海平面(高于 0)。
每条腿只能在bounds = (0, 10)的范围内向上移动(每条腿可以从其基础高度上升 0 个单位到 10 个单位)，以便使放置在腿顶部的道路在桥梁之间的中点连接到相邻的道路。
我正在尝试创建一个算法，该算法返回需要对每条腿进行的调整列表，以确保每座桥都在其共享中点连接到其相邻桥。
到目前为止，我目前的信念是，这是一个优化问题，我试图在桥梁之间的中点处尽量减少桥梁道路两端之间的垂直距离。但是，我已经尝试了多次不同的迭代，但到目前为止都没有运气。我对优化算法很陌生，所以这可能是我到目前为止失败的原因。 (使用 scipy.optimize.minimize )
也有可能这不是优化问题，可以通过其他方式解决，在这种情况下，我很乐意听取任何可以帮助我指明正确方向的人的其他方法。
如果有人能帮我解决这个问题，或者至少帮我指明正确的方向，我将不胜感激。
非常感谢任何反馈，我一定会快速回复您的任何问题或评论。非常感谢!
编辑:
例如:这是我们的桥梁在任何调整之前的样子(红色是桥梁的腿，绿色是桥梁之间的中点，蓝色箭头是桥梁道路终止的地方，蓝色横条代表基础高度桥)

这就是我们的桥梁经过一系列成功调整后的样子:(黑色箭头是新道路将停在腿上的地方)
如您所见，为了让我们的桥梁连接起来，一种可能的解决方案是抬高第 2 条腿和第 5 条腿(分别抬高大约 4 个单位和 1 个单位)

Answer 1

根据要求，这里是如何将其表述为线性程序并使用 OR-Tools 解决的方法。
对于每条腿，创建一个变量。此变量的下限是腿的当前高度。此变量的上限是腿的最大高度(例如，当前 + 10)。
对于每对相邻的桥梁，我们将它们相邻支腿之间的中点限制为两个桥梁的高度相同。
为了一个目标，我将满足于最小化斜率的最大差异。我们使用斜率而不是角度，因为它是线性的，斜率的差异很好地近似了角度的差异。 (绝对可以直接优化角度差异，但我们必须切换到 cvxpy 或支持非线性目标的东西。)

from ortools.linear_solver import pywraplp

x = [0, 200, 300, 500, 600, 800]
y = [6, 1, 6, 9, 9, 120]
initial_bounds = [(0, 10), (0, 9), (0, 9.5), (0, 8), (0, 7), (0, 9)]

# Returns the y value at x2 of the line between (x0,y0) and (x1,y1).
def extrapolate(x0, y0, x1, y1, x2):
    return y0 + (x2 - x0) / (x1 - x0) * (y1 - y0)


def solve(is_phase_one, bounds):
    solver = pywraplp.Solver.CreateSolver("GLOP")
    if is_phase_one:
        objective = solver.NumVar(0, solver.infinity(), "objective")
        new_y = [
            solver.NumVar(-solver.infinity(), solver.infinity(), "y%d" % i)
            for i in range(len(y))
        ]
        for i in range(len(y)):
            solver.Add(new_y[i] >= y[i] + bounds[i][0] - objective)
            solver.Add(new_y[i] <= y[i] + bounds[i][1] + objective)
    else:
        objective = 0
        new_y = [
            solver.NumVar(y[i] + bounds[i][0], y[i] + bounds[i][1], "y%d" % i)
            for i in range(len(y))
        ]
    for i in range(3, len(y), 2):
        midpoint = (x[i - 2] + x[i - 1]) / 2
        solver.Add(
            extrapolate(x[i - 3], new_y[i - 3], x[i - 2], new_y[i - 2], midpoint)
            == extrapolate(x[i - 1], new_y[i - 1], x[i], new_y[i], midpoint)
        )
    if not is_phase_one:
        for i in range(1, len(y), 2):
            z = solver.NumVar(0, solver.infinity(), "")
            slope = (new_y[i] - new_y[i - 1]) / (x[i] - x[i - 1])
            solver.Add(z >= slope)
            solver.Add(z >= -slope)
            objective += z
    solver.Minimize(objective)
    status = solver.Solve()
    assert status == pywraplp.Solver.OPTIMAL
    if is_phase_one:
        return [
            (
                bounds[i][0] - objective.solution_value(),
                bounds[i][1] + objective.solution_value(),
            )
            for i in range(len(y))
        ]
    else:
        return [variable.solution_value() for variable in new_y]


relaxed_bounds = solve(True, initial_bounds)
print(relaxed_bounds)
heights = solve(False, relaxed_bounds)
print(heights)

示例输出:

[(-6.1999999999999975, 16.199999999999996), (-6.1999999999999975, 15.199999999999998), (-6.1999999999999975, 15.699999999999998), (-6.1999999999999975, 14.199999999999998), (-6.1999999999999975, 13.199999999999998), (-6.1999999999999975, 15.199999999999998)]
[-0.1999999999999975, 16.199999999999996, 16.800000000000033, 2.8000000000000025, 22.199999999999996, 113.8]