Ridurre al minimo il tempo trascorso quando si viaggia su un percorso designato

Question

Questa domanda è relativa a this one, derivava dall'ottimizzazione del percorso su un insieme di punti. La situazione è la seguente: Un oggetto percorre un percorso designato che consiste in un elenco di punti 2D. (Sono possibili più Ds, ma dato che ogni turno è tecnicamente 2D, la soluzione per le due dimensioni lo farà.) Ad ogni punto questo oggetto può cambiare la sua velocità con un vettore che la lunghezza massima è predeterminata (assegnata a un punto). La velocità alla fine del percorso è irrilevante. La domanda è: come determinare il tempo minimo trascorso percorrendo questo percorso? Esiste un algoritmo efficiente per questo compito? Un algoritmo avido può alla fine far rallentare l'oggetto in modo tale da essere sottoposto a scansione in caso di dati appositamente preparati, o addirittura non rendere l'oggetto in grado di tornare al suo prossimo punto designato. Un algoritmo avido di versioni precedenti è anche imperfetto con lo stesso errore, non sempre è buono arrivare alla fine alla massima velocità.

Un esempio: il vettore punto è: {(0,0), (0,1), (1,1), (2,2)} e il vettore di lunghezza massima è {2.0, 2.0, 3.0}. Il punto viaggia ad esempio a (0,sqrt(2)) da p1 a p2, quindi a (sqrt(2),0) da p2 a p3 e con (s,s) a qualsiasi velocità massima s da p3 a p4. E questa potrebbe essere una soluzione subottimale, dire di rallentare di uno 0,01 da p1 a p2, permettendo di accelerare di un po 'da p2 a p3, poi di un altro da p3 a p4, con un tempo totale possibile inferiore a questo insieme di velocità.

Answer 1

Questo è un problema di ottimizzazione convessa, risolvibile mediante librerie di ottimizzazione non lineare comuni. In 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)