algorithm - 尽量减少在指定路径上行驶时花费的时间

Question

这个问题与this one有关，它源自优化一组点的路径。这里的情况如下:一个物体沿着由二维点列表组成的指定路径行进。 (更多的 D 是可能的，但由于每一圈在技术上都是二维的，因此求解二维就可以了。)在每个点，该对象都可以通过一个矢量来改变它的速度，该矢量的最大长度是预先确定的(分配给一个点)。路径末端的速度无关紧要。问题是，如何确定走这条路所花费的最短时间？这个任务有什么有效的算法吗？一个贪心算法最终会在特别准备的数据的情况下让物体慢得像爬行一样，甚至不能让物体转向下一个指定点。向后贪婪算法也有同样的错误，以最大速度到达终点并不总是好的。

一个例子:点向量是:{(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)