Calea costului minim cu mișcări în stânga, dreapta, jos și sus permise
Încercați-l pe GfG Practice 
Ieșire
Având în vedere o grilă 2D de dimensiune n*n unde fiecare celulă reprezintă costul de parcurgere prin acea celulă, sarcina este de a găsi cost minim a muta de la stânga sus celula la dreapta jos celulă. Dintr-o celulă dată ne putem muta 4 direcții : stânga dreapta sus în jos.
Nota: Se presupune că ciclurile de cost negative nu există în matricea de intrare.
Exemplu:
Intrare: grilă = {{9 4 9 9}
{6 7 6 4}
{8 3 3 7}
{7 4 9 10}}
Ieșire: 43
Explicaţie: Calea costului minim este 9 + 4 + 7 + 3 + 3 + 7 + 10.
Abordare:
Ideea este de a folosi algoritmul lui Dijkstra pentru a găsi calea costului minim prin grilă. Această abordare tratează grila ca pe un grafic în care fiecare celulă este un nod, iar algoritmul explorează dinamic calea cea mai rentabilă către celula din dreapta jos, extinzând întotdeauna mai întâi căile cu cel mai mic cost.
Abordare pas cu pas:
- Folosiți un min-heap pentru a procesa întotdeauna mai întâi calea cu cel mai mic cost și împingeți celula din stânga sus în ea.
- Inițializați o matrice de cost cu valori maxime setând costul celulei de început la valoarea de grilă.
- Pentru fiecare celulă verificați toate cele 4 celule învecinate
- Dacă se găsește o cale cu un cost mai mic, actualizați costul celulei și împingeți-l în heap.
- Returnați costul minim pentru a ajunge la celula din dreapta jos.
Mai jos este implementarea abordării de mai sus:
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 ));
Ieșire
43
Complexitatea timpului: O(n^2 log(n^2))
Spațiu auxiliar: O(n^2 log(n^2))
De ce nu poate fi folosită programarea dinamică?
Programarea dinamică eșuează aici, deoarece permiterea mișcării în toate cele patru direcții creează cicluri în care celulele pot fi revizuite, rupând ipoteza optimă a substructurii. Aceasta înseamnă că costul pentru a ajunge la o celulă dintr-o celulă dată nu este fix, ci depinde de întreaga cale.
Articole înrudite:
Calea costului minim
Creați un test
