Kth Percorso ottimale in una matrice

Nella versione classica (k = 1, risoluzione per il miglior percorso), l'intuizione chiave utilizzata è la seguente.

1) Nel calcolo del miglior percorso per cella (i, j) (migliore [i] [j] è il costo del miglior percorso da top-left a (i, j)), notiamo che questo percorso potrebbe venire da sinistra o superiore vicino. Così facciamo (lasciando da parte i casi d'angolo per un momento)

best[i][j] = min(best[i][j-1], best[i-1][j]) + value[i][j]

2) Ora, se vogliamo calcolare k percorsi migliori dall'angolo in alto a sinistra a (i, j), possiamo ancora seguire una tecnica simile, ma più generale. Qui, meglio [i] [j] può essere pensato come una lista di k percorsi migliori invece di un percorso migliore.

best[i][j] = merge_and_select_k(best[i-1][j], best[i][j-1], k)

merge_and_select_k prende due liste di input, un intero k - Concatena le due liste e mantiene solo i migliori valori k. Ovviamente, devi anche aggiungere valore [i] [j] a tutti questi elementi selezionati.

3) Loop sulla matrice, proprio come nella versione classica e calcolare meglio [i] [j] per ogni i e j. Il tuo risultato finale è il migliore [n] [n] [k].

4) Funziona perché, dobbiamo solo considerare i migliori [i-1] [j] e i migliori [i] [j-1] per il calcolo migliore [i] [j]. La complessità temporale è O (k * n * n) e la complessità spaziale è O (k * n), poiché è necessario solo mantenere i valori per le righe correnti e precedenti.

Probabilmente non è il modo migliore , ma dato che non ci sono altre risposte, ecco a modo.

Il problema di trovare il percorso ottimale k-esimo è AFAIK non molto ben studiato per le matrici, ma è abbastanza comune nei grafici. Infatti, Wikipedia ha alcuni esempi di come può essere fatto in un grafico orientato ponderato. Quindi una soluzione che trasforma la tua matrice in un grafico e utilizza l'algoritmo del Wiki:

Algoritmo:

Trasforma la tua matrice in un grafico orientato ponderato. Ogni voce nella tua matrice sarà un vertice, e il vertice A ha un bordo al vertice B se A è sopra o a sinistra di B nella matrice. Il peso del bordo è il valore del vertice finale.

Ora, usa l'algoritmo di Yen per trovare il percorso ottimale k-esimo. (è un algoritmo abbastanza conosciuto, ma lungo, quindi non postarlo qui).

Complessità

La creazione del grafico è banale e richiede un tempo lineare nella dimensione della matrice. Il grafico risultante ha N^2 vertici e 2N(N-1) spigoli. L'algoritmo di Yen richiede chiamate K * l a Dijkstra, dove l è la lunghezza dei percorsi spur (in questo caso è 2N , poiché tutti i percorsi qui sono al massimo 2N lunghezza).

Quindi il runtime totale dovrebbe essere O(K * N^3 * log(N)) . Questo è un limite molto pessimistico, ma potreste scoprire che il comportamento cubico è effettivamente vero: questa soluzione non utilizza professionisti dalla struttura del grafo a matrice.

Dopo aver pensato un po 'di più:

Esiste un'evidente soluzione ingenua che accetta solo l'approccio standard di programmazione dinamica, e invece di memorizzare il percorso più breve per ogni nodo memorizza i k percorsi più brevi.

Questa soluzione sarà più veloce di quanto sopra, con clock a O(K * N^2) . Tuttavia, utilizza lo spazio O(K * N^2) , che è molto più grande di O(N * (K + N)) della soluzione di cui sopra. Immagino che qui avresti bisogno di prendere una decisione su quale risorsa è più scarsa.