最大限度地减少在指定路径上行驶所花费的时间

Question

这个问题关系到这一个,它是从在一组点的优化路径的.这里的情况如下:对象行进包括2D点列表的指定路径.(可以使用更多的Ds,但由于每个转弯在技术上都是2D,因此求解两个维度.)在每个点上,此对象可以通过向量来改变其速度,该向量最大长度是预先确定的(分配给一个点).路径尽头的速度无关紧要.问题是,如何确定在这条路上行走的最短时间？这个任务有什么有效的算法吗？贪婪算法最终可以使对象在特殊准备数据的情况下变慢,甚至不使对象能够转向下一个指定点.后向贪婪的算法也存在同样的错误,以最大速度到达终点并不总是好的.

一个例子:点向量是:{(0,0), (0,1), (1,1), (2,2)}和最大长度向量是{2.0, 2.0, 3.0}.该点例如(0,sqrt(2))从p1 行进到p2,然后(sqrt(2),0)从p2 行进到p3,并且(s,s)无论最大速度s是从p3到p4.这可能是一个次优解决方案,比如从p1减速到p2减速0.01,允许从p2加速到p3,然后再从p3加速到p4,可能的总时间小于此一组速度.

Answer 1

这是一个凸优化问题,可由常见的非线性优化库解决.在SciPy中:

import numpy as np
from scipy import optimize

points = np.array([[0., 0.], [0., 1.], [1., 1.], [2., 2.]])
movements = np.diff(points, axis=0)
lengths = np.linalg.norm(movements, axis=1)
directions = movements / lengths[:, np.newaxis]
max_acceleration = np.array([2., 2., 3.])

fun = lambda x: np.sum(lengths / x)
x0 = np.repeat(.5 * np.amin(max_acceleration), len(movements))
bounds = [(0., max_acceleration[0])] + [(0., None)] * (len(movements) - 1)
constraints = [
    dict(
        type='ineq',
        fun=lambda x, j: max_acceleration[j + 1] - np.linalg.norm(x[j] * directions[j] - x[j + 1] * directions[j + 1]),
        args=(i, )) for i in range(len(movements) - 1)
]
x = optimize.minimize(fun, x0, bounds=bounds, constraints=constraints).x
print(x)