Minimaler Kostenpfad mit zulässigen Bewegungen nach links, rechts, unten und oben
Probieren Sie es bei GfG Practice aus 
Ausgabe
Gegeben sei ein zweidimensionales Größengitter n*n wobei jede Zelle die Kosten für die Durchquerung dieser Zelle darstellt. Die Aufgabe besteht darin, die zu finden minimale Kosten sich von der bewegen oben links Zelle zum unten rechts Zelle. Von einer bestimmten Zelle aus können wir einziehen 4 Richtungen : links rechts oben unten.
Notiz: Es wird davon ausgegangen, dass es in der Eingabematrix keine negativen Kostenzyklen gibt.
Beispiel:
Eingang: Gitter = {{9 4 9 9}
{6 7 6 4}
{8 3 3 7}
{7 4 9 10}}
Ausgabe: 43
Erläuterung: Der Mindestkostenpfad beträgt 9 + 4 + 7 + 3 + 3 + 7 + 10.
Ansatz:
Die Idee ist zu verwenden Dijkstras Algorithmus um den Weg mit minimalen Kosten durch das Gitter zu finden. Dieser Ansatz behandelt das Gitter als Diagramm, in dem jede Zelle ein Knoten ist und der Algorithmus dynamisch den kostengünstigsten Pfad zur Zelle unten rechts untersucht, indem er immer zuerst die Pfade mit den niedrigsten Kosten erweitert.
Schritt-für-Schritt-Ansatz:
- Verwenden Sie einen Min-Heap, um immer zuerst den Pfad mit den niedrigsten Kosten zu verarbeiten und die obere linke Zelle hineinzuschieben.
- Initialisieren Sie eine Kostenmatrix mit Maximalwerten und setzen Sie die Kosten der Startzelle auf ihren Rasterwert.
- Überprüfen Sie für jede Zelle alle 4 benachbarten Zellen
- Wenn ein Pfad mit niedrigeren Kosten gefunden wird, aktualisieren Sie die Kosten der Zelle und verschieben Sie sie in den Heap.
- Geben Sie die Mindestkosten zurück, um die Zelle unten rechts zu erreichen.
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
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 ));
Ausgabe
43
Zeitkomplexität: O(n^2 log(n^2))
Hilfsraum: O(n^2 log(n^2))
Warum kann dynamische Programmierung nicht verwendet werden?
Die dynamische Programmierung schlägt hier fehl, da durch das Zulassen von Bewegungen in alle vier Richtungen Zyklen entstehen, in denen Zellen erneut besucht werden können, wodurch die Annahme einer optimalen Unterstruktur gebrochen wird. Dies bedeutet, dass die Kosten für das Erreichen einer Zelle von einer bestimmten Zelle aus nicht festgelegt sind, sondern vom gesamten Pfad abhängen.
Verwandte Artikel:
Min. Kostenpfad
Quiz erstellen
