Percorso più veloce con accelerazione ai punti

Question

Questo è solo qualcosa che mi è venuto in mente da solo, ma sembra un problema divertente e mi ha convinto.

Hai una serie di punti nello spazio bidimensionale, con un punto designato "Inizio" e uno "Fine". Ogni punto ha coordinate (in metri dall'origine), ma anche un "numero di accelerazione" (in metri/secondo di delta-V). Al raggiungimento di un punto (incluso l'inizio), è possibile accelerare fino al numero di accelerazione di quel punto in qualsiasi direzione. Il costo del bordo dipende dalla tua velocità attuale, ma devi anche muoverti nella direzione corretta.

Esiste un algoritmo efficiente per trovare il percorso più veloce fino al punto finale? Non ho trovato niente di meglio di "Prova ogni percorso e verifica i risultati". Gli algoritmi di Djikstra e altri semplici algoritmi non funzionano, perché non si può facilmente dire che un percorso verso un punto intermedio sia migliore o peggiore di un altro, se vi arriva con diverse velocità iniziali.

Se è troppo semplice, cosa succede se aggiungi il requisito che devi fermare al punto finale? (Ad esempio, è necessario avere un valore inferiore al suo valore di accelerazione quando si raggiunge la fine.)

MODIFICA: Per essere chiari, la direzione è importante. Si mantiene un vettore di velocità mentre si attraversa il grafico e l'accelerazione significa aggiungere un vettore ad esso, la cui magnitudine è limitata al numero di accelerazione di quel punto. Ciò significa che ci sono situazioni in cui la costruzione di un'enorme velocità è dannosa, poiché andrai troppo veloce per "indirizzare" verso altri punti preziosi/la tua destinazione.

Answer 1

Penso che il requisito che si usi l'accelerazione da ciascun punto una sola volta rende questo problema NP completo nel caso generale. Prendere in considerazione un ingresso che assomiglia a questo:

Se la "enorme distanza" tra il punto finale e il resto dei punti è grande abbastanza per dominare il costo della soluzione finale, trovando una soluzione ottimale sarà si riduce a trovare un modo per raccogliere il maggior numero di accelerazioni possibili dall'inizio del grafico. Se si consente solo a ciascun punto di essere passato una volta, ciò equivale al problema del percorso hamiltoniano, che è NP completo.

Detto questo, il problema ha alcune regole extra su di esso (le distanze sono euclide, il grafico è sempre completo) che potrebbe finire per rendere più facile il problema.

Answer 2

È possibile provare a risolvere questo problema all'indietro, tracciando ricorsivamente i percorsi dall'estremità verso l'altro nodo, quindi designare la massima velocità lungo la linea per poter passare da quel nodo a qualsiasi altro. La regola di eliminazione sarà se un percorso dal nodo corrente a quello successivo esiste con meno velocità e meno tempo trascorso dalla fine, il che significa che l'altro percorso è più ottimale di default perché può raggiungere più nodi e richiede meno tempo. Una volta che un percorso raggiunge il nodo iniziale, dovrebbe essere ricalcolato in base alla velocità massima raggiungibile all'avvio e memorizzata. Quindi raccogli il percorso con meno tempo speso.

È necessario cercare qualsiasi percorso disponibile qui, perché i percorsi disponibili sul grafico dipendono dallo stato passato con una meccanica indiretta, utilizzando meno velocità consente più scelte.