时间戳

首页 > 解决方案 > 通过抬腿在中点连接一系列桥梁

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

问题描述

在过去的几周里，我一直在尝试解决与我正在从事的个人项目相关的问题。我尝试了几种不同的方法，但它们似乎都没有给我我正在寻找的结果，所以我希望这里有人可以帮助我至少指出正确的方向。

情况：我想建造一系列桥梁，连接在每座桥梁之间的中点。我得到了地面的地形和将用作桥腿的柱子。（每座桥都有两条腿来支撑上面的道路）。腿站立的地面不一定是平坦的，因此每座桥的腿之间的角度会有所不同。如果我在每座桥的腿上放一条路，由于桥的角度和腿的相对高度不同，所以当路放在桥上时，路不一定与路相连它将建在两座桥之间中点的下一座桥上。因为这，我被允许在一组界限内抬高桥的任何/所有腿，以使放置在桥腿顶部的每条道路在桥之间的中点与相邻的道路连接。（道路延伸到桥腿之外，并终止于任何相邻桥梁之间的中点）

示例：我有一个沿 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 个单位）

标签： pythonalgorithmoptimizationscipytrigonometry

解决方案

根据要求，以下是如何将其表述为线性程序并使用 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]

推荐阅读