Minimālo izmaksu ceļš ar atļautām kustībām pa kreisi, pa labi, uz leju un uz augšu
Izmēģiniet to GfG praksē 
Izvade
Dots 2D režģa izmērs n*n kur katra šūna apzīmē izmaksas, lai pārvietotos caur šo šūnu, uzdevums ir atrast minimālās izmaksas lai pārvietotos no augšā pa kreisi šūnu uz apakšā pa labi šūna. No dotās šūnas mēs varam pārvietoties 4 virzieni : pa kreisi pa labi uz augšu uz leju.
Piezīme: Tiek pieņemts, ka ievades matricā nepastāv negatīvu izmaksu cikli.
Piemērs:
Ievade: režģis = {{9 4 9 9}
{6 7 6 4}
{8 3 3 7}
{7 4 9 10}}
Rezultāts: 43
Paskaidrojums: Minimālais izmaksu ceļš ir 9 + 4 + 7 + 3 + 3 + 7 + 10.
Pieeja:
Ideja ir izmantot Dijkstras algoritms lai atrastu minimālo izmaksu ceļu caur tīklu. Izmantojot šo pieeju, režģis tiek uzskatīts par grafiku, kurā katra šūna ir mezgls, un algoritms dinamiski pēta visrentablāko ceļu uz apakšējo labo šūnu, vienmēr vispirms paplašinot zemāko izmaksu ceļus.
Soli pa solim pieeja:
- Izmantojiet minimālo kaudzi, lai vienmēr vispirms apstrādātu viszemāko izmaksu ceļu un iebīdītu tajā augšējo kreiso šūnu.
- Inicializējiet izmaksu matricu ar maksimālajām vērtībām, iestatot sākuma šūnas izmaksas uz tās režģa vērtību.
- Katrai šūnai pārbaudiet visas 4 blakus esošās šūnas
- Ja tiek atrasts zemāku izmaksu ceļš, atjauniniet šūnas izmaksas un ievietojiet to kaudzē.
- Atgrieziet minimālās izmaksas, lai sasniegtu apakšējo labo šūnu.
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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 ));
Izvade
43
Laika sarežģītība: O(n^2 log(n^2))
Palīgtelpa: O(n^2 log(n^2))
Kāpēc nevar izmantot dinamisko programmēšanu?
Dinamiskā programmēšana šeit neizdodas, jo, atļaujot kustību visos četros virzienos, tiek izveidoti cikli, kuros šūnas var atkārtoti apskatīt, pārkāpjot pieņēmumu par optimālo apakšstruktūru. Tas nozīmē, ka izmaksas, lai sasniegtu šūnu no noteiktās šūnas, nav fiksētas, bet ir atkarīgas no visa ceļa.
Saistītie raksti:
Minimālo izmaksu ceļš
Izveidojiet viktorīnu
