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

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)

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

Minimize time spent when travelling a designated path

language-agnostic

algorithm

mathematical-optimization