Свести к минимуму время, затрачиваемое при проезде по указанному пути

Question

Этот вопрос связан с this one, он был получен из оптимизации пути по множеству точек. Ситуация здесь такова: объект перемещается по выделенному пути, содержащему список двумерных точек. (Возможно больше 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. И это может быть субоптимальное решение, скажем, вы замедляетесь на 0,01 от p1 до p2, что позволяет ускорить переход от p2 к p3, а затем к другому tad в 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)