Camí de cost mínim amb moviments esquerra, dreta, inferior i amunt permesos
Prova-ho a GfG Practice 
Sortida
Donada una quadrícula 2D de mida n*n on cada cel·la representa el cost per recórrer aquesta cel·la, la tasca és trobar el cost mínim per moure's de la superior esquerra cel·la a la inferior dreta cel·la. Des d'una cèl·lula determinada ens podem moure 4 direccions : esquerra dreta amunt avall.
Nota: S'assumeix que els cicles de costos negatius no existeixen a la matriu d'entrada.
Exemple:
Entrada: quadrícula = {{9 4 9 9}
{6 7 6 4}
{8 3 3 7}
{7 4 9 10}}
Sortida: 43
Explicació: El camí de cost mínim és 9 + 4 + 7 + 3 + 3 + 7 + 10.
Enfocament:
La idea és utilitzar algorisme de Dijkstra per trobar la ruta de cost mínim a través de la xarxa. Aquest enfocament tracta la quadrícula com un gràfic on cada cel·la és un node i l'algorisme explora dinàmicament el camí més rendible cap a la cel·la inferior dreta ampliant sempre primer els camins de menor cost.
Enfocament pas a pas:
- Utilitzeu un munt mínim per processar sempre primer el camí de menor cost i introduir-hi la cel·la superior esquerra.
- Inicialitzar una matriu de costos amb valors màxims establint el cost de la cel·la inicial al seu valor de quadrícula.
- Per a cada cel·la, comproveu les 4 cel·les veïnes
- Si es troba una ruta de menor cost, actualitzeu el cost de la cel·la i introduïu-la a la pila.
- Torna el cost mínim per arribar a la cel·la inferior dreta.
A continuació es mostra la implementació de l'enfocament anterior:
C++ // C++ program to find minimum Cost Path with // Left Right Bottom and Up moves allowed #include using namespace std ; // Function to check if cell is valid. bool isValidCell ( int i int j int n ) { return i >= 0 && i < n && j >= 0 && j < n ; } int minimumCostPath ( vector < vector < int >> & grid ) { int n = grid . size (); // Min heap to implement dijkstra priority_queue < vector < int > vector < vector < int >> greater < vector < int >>> pq ; // 2d grid to store minimum cost // to reach every cell. vector < vector < int >> cost ( n vector < int > ( n INT_MAX )); cost [ 0 ][ 0 ] = grid [ 0 ][ 0 ]; // Direction vector to move in 4 directions vector < vector < int >> dir = {{ -1 0 } { 1 0 } { 0 -1 } { 0 1 }}; pq . push ({ grid [ 0 ][ 0 ] 0 0 }); while ( ! pq . empty ()) { vector < int > top = pq . top (); pq . pop (); int c = top [ 0 ] i = top [ 1 ] j = top [ 2 ]; // Check for all 4 neighbouring cells. for ( auto d : dir ) { int x = i + d [ 0 ]; int y = j + d [ 1 ]; // If cell is valid and cost to reach this cell // from current cell is less if ( isValidCell ( x y n ) && cost [ i ][ j ] + grid [ x ][ y ] < cost [ x ][ y ]) { // Update cost to reach this cell. cost [ x ][ y ] = cost [ i ][ j ] + grid [ x ][ y ]; // Push the cell into heap. pq . push ({ cost [ x ][ y ] x y }); } } } // Return minimum cost to // reach bottom right cell. return cost [ n -1 ][ n -1 ]; } int main () { vector < vector < int >> grid = {{ 9 4 9 9 }{ 6 7 6 4 }{ 8 3 3 7 }{ 7 4 9 10 }}; cout < < minimumCostPath ( grid ) < < endl ; return 0 ; }
Java // Java program to find minimum Cost Path with // Left Right Bottom and Up moves allowed import java.util.PriorityQueue ; import java.util.Arrays ; class GfG { // Function to check if cell is valid. static boolean isValidCell ( int i int j int n ) { return i >= 0 && i < n && j >= 0 && j < n ; } static int minimumCostPath ( int [][] grid ) { int n = grid . length ; // Min heap to implement Dijkstra PriorityQueue < int []> pq = new PriorityQueue <> (( a b ) -> Integer . compare ( a [ 0 ] b [ 0 ] )); // 2D grid to store minimum cost // to reach every cell. int [][] cost = new int [ n ][ n ] ; for ( int [] row : cost ) { Arrays . fill ( row Integer . MAX_VALUE ); } cost [ 0 ][ 0 ] = grid [ 0 ][ 0 ] ; // Direction vector to move in 4 directions int [][] dir = {{ - 1 0 } { 1 0 } { 0 - 1 } { 0 1 }}; pq . offer ( new int [] { grid [ 0 ][ 0 ] 0 0 }); while ( ! pq . isEmpty ()) { int [] top = pq . poll (); int c = top [ 0 ] i = top [ 1 ] j = top [ 2 ] ; // Check for all 4 neighbouring cells. for ( int [] d : dir ) { int x = i + d [ 0 ] ; int y = j + d [ 1 ] ; // If cell is valid and cost to reach this cell // from current cell is less if ( isValidCell ( x y n ) && cost [ i ][ j ] + grid [ x ][ y ] < cost [ x ][ y ] ) { // Update cost to reach this cell. cost [ x ][ y ] = cost [ i ][ j ] + grid [ x ][ y ] ; // Push the cell into heap. pq . offer ( new int [] { cost [ x ][ y ] x y }); } } } // Return minimum cost to // reach bottom right cell. return cost [ n - 1 ][ n - 1 ] ; } public static void main ( String [] args ) { int [][] grid = { { 9 4 9 9 } { 6 7 6 4 } { 8 3 3 7 } { 7 4 9 10 } }; System . out . println ( minimumCostPath ( grid )); } }
Python # Python program to find minimum Cost Path with # Left Right Bottom and Up moves allowed import heapq # Function to check if cell is valid. def isValidCell ( i j n ): return i >= 0 and i < n and j >= 0 and j < n def minimumCostPath ( grid ): n = len ( grid ) # Min heap to implement Dijkstra pq = [] # 2D grid to store minimum cost # to reach every cell. cost = [[ float ( 'inf' )] * n for _ in range ( n )] cost [ 0 ][ 0 ] = grid [ 0 ][ 0 ] # Direction vector to move in 4 directions dir = [[ - 1 0 ] [ 1 0 ] [ 0 - 1 ] [ 0 1 ]] heapq . heappush ( pq [ grid [ 0 ][ 0 ] 0 0 ]) while pq : c i j = heapq . heappop ( pq ) # Check for all 4 neighbouring cells. for d in dir : x y = i + d [ 0 ] j + d [ 1 ] # If cell is valid and cost to reach this cell # from current cell is less if isValidCell ( x y n ) and cost [ i ][ j ] + grid [ x ][ y ] < cost [ x ][ y ]: # Update cost to reach this cell. cost [ x ][ y ] = cost [ i ][ j ] + grid [ x ][ y ] # Push the cell into heap. heapq . heappush ( pq [ cost [ x ][ y ] x y ]) # Return minimum cost to # reach bottom right cell. return cost [ n - 1 ][ n - 1 ] if __name__ == '__main__' : grid = [ [ 9 4 9 9 ] [ 6 7 6 4 ] [ 8 3 3 7 ] [ 7 4 9 10 ] ] print ( minimumCostPath ( grid ))
C# // C# program to find minimum Cost Path with // Left Right Bottom and Up moves allowed using System ; using System.Collections.Generic ; class GfG { // Function to check if cell is valid. static bool isValidCell ( int i int j int n ) { return i >= 0 && i < n && j >= 0 && j < n ; } static int minimumCostPath ( int [][] grid ) { int n = grid . Length ; // Min heap to implement Dijkstra var pq = new SortedSet < ( int cost int x int y ) > (); // 2D grid to store minimum cost // to reach every cell. int [][] cost = new int [ n ][]; for ( int i = 0 ; i < n ; i ++ ) { cost [ i ] = new int [ n ]; Array . Fill ( cost [ i ] int . MaxValue ); } cost [ 0 ][ 0 ] = grid [ 0 ][ 0 ]; // Direction vector to move in 4 directions int [][] dir = { new int [] { - 1 0 } new int [] { 1 0 } new int [] { 0 - 1 } new int [] { 0 1 } }; pq . Add (( grid [ 0 ][ 0 ] 0 0 )); while ( pq . Count > 0 ) { var top = pq . Min ; pq . Remove ( top ); int i = top . x j = top . y ; // Check for all 4 neighbouring cells. foreach ( var d in dir ) { int x = i + d [ 0 ]; int y = j + d [ 1 ]; // If cell is valid and cost to reach this cell // from current cell is less if ( isValidCell ( x y n ) && cost [ i ][ j ] + grid [ x ][ y ] < cost [ x ][ y ]) { // Update cost to reach this cell. cost [ x ][ y ] = cost [ i ][ j ] + grid [ x ][ y ]; // Push the cell into heap. pq . Add (( cost [ x ][ y ] x y )); } } } // Return minimum cost to // reach bottom right cell. return cost [ n - 1 ][ n - 1 ]; } static void Main ( string [] args ) { int [][] grid = new int [][] { new int [] { 9 4 9 9 } new int [] { 6 7 6 4 } new int [] { 8 3 3 7 } new int [] { 7 4 9 10 } }; Console . WriteLine ( minimumCostPath ( grid )); } }
JavaScript // JavaScript program to find minimum Cost Path with // Left Right Bottom and Up moves allowed function comparator ( a b ) { if ( a [ 0 ] > b [ 0 ]) return - 1 ; if ( a [ 0 ] < b [ 0 ]) return 1 ; return 0 ; } class PriorityQueue { constructor ( compare ) { this . heap = []; this . compare = compare ; } enqueue ( value ) { this . heap . push ( value ); this . bubbleUp (); } bubbleUp () { let index = this . heap . length - 1 ; while ( index > 0 ) { let element = this . heap [ index ] parentIndex = Math . floor (( index - 1 ) / 2 ) parent = this . heap [ parentIndex ]; if ( this . compare ( element parent ) < 0 ) break ; this . heap [ index ] = parent ; this . heap [ parentIndex ] = element ; index = parentIndex ; } } dequeue () { let max = this . heap [ 0 ]; let end = this . heap . pop (); if ( this . heap . length > 0 ) { this . heap [ 0 ] = end ; this . sinkDown ( 0 ); } return max ; } sinkDown ( index ) { let left = 2 * index + 1 right = 2 * index + 2 largest = index ; if ( left < this . heap . length && this . compare ( this . heap [ left ] this . heap [ largest ]) > 0 ) { largest = left ; } if ( right < this . heap . length && this . compare ( this . heap [ right ] this . heap [ largest ]) > 0 ) { largest = right ; } if ( largest !== index ) { [ this . heap [ largest ] this . heap [ index ]] = [ this . heap [ index ] this . heap [ largest ] ]; this . sinkDown ( largest ); } } isEmpty () { return this . heap . length === 0 ; } } // Function to check if cell is valid. function isValidCell ( i j n ) { return i >= 0 && i < n && j >= 0 && j < n ; } function minimumCostPath ( grid ) { let n = grid . length ; // Min heap to implement Dijkstra const pq = new PriorityQueue ( comparator ) // 2D grid to store minimum cost // to reach every cell. let cost = Array . from ({ length : n } () => Array ( n ). fill ( Infinity )); cost [ 0 ][ 0 ] = grid [ 0 ][ 0 ]; // Direction vector to move in 4 directions let dir = [[ - 1 0 ] [ 1 0 ] [ 0 - 1 ] [ 0 1 ]]; pq . enqueue ([ grid [ 0 ][ 0 ] 0 0 ]); while ( ! pq . isEmpty ()) { let [ c i j ] = pq . dequeue (); // Check for all 4 neighbouring cells. for ( let d of dir ) { let x = i + d [ 0 ]; let y = j + d [ 1 ]; // If cell is valid and cost to reach this cell // from current cell is less if ( isValidCell ( x y n ) && cost [ i ][ j ] + grid [ x ][ y ] < cost [ x ][ y ]) { // Update cost to reach this cell. cost [ x ][ y ] = cost [ i ][ j ] + grid [ x ][ y ]; // Push the cell into heap. pq . enqueue ([ cost [ x ][ y ] x y ]); } } } // Return minimum cost to // reach bottom right cell. return cost [ n - 1 ][ n - 1 ]; } let grid = [ [ 9 4 9 9 ] [ 6 7 6 4 ] [ 8 3 3 7 ] [ 7 4 9 10 ] ]; console . log ( minimumCostPath ( grid ));
Sortida
43
Complexitat temporal: O(n^2 log(n^2))
Espai auxiliar: O(n^2 log(n^2))
Per què no es pot utilitzar la programació dinàmica?
La programació dinàmica falla aquí perquè permetre el moviment en les quatre direccions crea cicles on es poden revisar les cèl·lules trencant la suposició de la subestructura òptima. Això significa que el cost per arribar a una cel·la des d'una cel·la determinada no és fix, sinó que depèn de tot el camí.
Articles relacionats:
Ruta del cost mínim
Crea un qüestionari
