recuperare il percorso con il peso più basso dalla matrice in modo ricorsivo

Question

diciamo che ho una matrice n^n. In ogni cella c'è un numero positivo, e ho bisogno di recuperare il percorso con il peso più basso.

percorso è ogni percorso che inizia in matrix[0][0] e finiscono in matrix[matrix.length-1][matrix[0].length-1], senza diagonali.

peso di di un percorso è la quantità di tutti i numeri nelle sue celle.

Ad esempio, supponiamo che ho questa matrice:

mat = {{1,2},{3,4}}; 

così {1,2,4} è un percorso, e {1,3,4} è un'altra percorso.

Il peso del primo percorso è (1 + 2 + 4) e la seconda ha un peso di (1 + 3 + 4), per cui la funzione restituirà .

Ho bisogno di risolverlo in modo ricorsivo. La pseudo codice dovrebbe essere qualcosa di simile:

if i > matrix.length-1 || i < 0 || j > matrix[0].length-1 || j < 0 
//then I passed the borders, so I need to step back. 
if i == matrix.length-1 && j == matrix[0].length-1 
//Then I reached the last cell, and I need to retrieve sum 

Quindi chiamare quattro recursives chiamate:

public static int smallPath(a, i+1, j, sum); 
public static int smallPath(a, i, j+1, sum); 
public static int smallPath(a, i-1, j, sum); 
public static int smallPath(a, i, j-1, sum); 

Poi ho bisogno di recuperare qualcosa, che cosa?

So che non è corrente ma questa è l'idea generale, qualcuno può aiutarmi a risolvere questo? Grazie!

Answer 1

io non sono sicuro se questa è la soluzione più efficace, ma si dovrebbe pensare a questo proposito:

1. si deve testare il modo casuale prima e ottenere la sua somma.
2. Approccio sistematico. Provane un altro e se la sua somma è più grande nel progresso, interrompila e prova l'altra.
3. Se si trova il più piccolo somma modo, catturare la sua somma (e le direzioni) e provare un altro fino a quando non v'è alcun modo lasciato
4. Hai il risultato :)

Questa soluzione sarebbe lavoro per i percorsi diretti. Voglio dire, passi sempre a destra o in basso. Non tornare indietro (in alto o a sinistra) - se inizi dalla cella in alto a sinistra e finisci in quella in basso a destra.

Controllare la differenza:

Il primo è ovvio, la somma più piccola è di 18 (3 + 2 + 1 + 0 + 1 + 2 + 4 + 3 + 2) .. ma nel secondo il risultato è secondo il mio metodo diretto 107 e non 17 come la soluzione corretta è.

In generale, per trovare la soluzione migliore è in questo caso molto complicato e devi specificare se imposti dei limiti o meno.

Answer 2

Dovresti essere in grado di utilizzare l'algoritmo di Dijstra, in cui i nodi sono "tra" le celle della matrice e le connessioni sono implicite dai pesi delle celle.

Per una risposta dettagliata, si prega di fare riferimento a questa domanda: Javascript: Pathfinding in a (50000*50000 grid) 2d array?