允许向左/向右/向下和向上移动的最小成本路径

2021年4月15日15:26:46 发表评论 1,096 次浏览

本文概述

给定一个二维网格, 该网格的每个像元都包含整数成本, 代表通过该像元所要经过的成本, 我们需要找到一条从左上角像元到右下角像元的路径, 从而使总成本最小。

注意 ：

假设输入矩阵中不存在负成本周期。

这个问题是下面的问题的延伸。

最小成本路径, 允许左右移动。

在前面的问题中, 只允许向右和向下移动, 但在此问题中, 我们被允许向下, 向上, 向右和向左移动, 即沿所有四个方向移动。

例子：

A cost grid is given in below diagram, minimum 
cost to reach bottom right from top left 
is 327 (= 31 + 10 + 13 + 47 + 65 + 12 + 18 + 
6 + 33 + 11 + 20 + 41 + 20)

The chosen least cost path is shown in green.

推荐：请在"实践首先, 在继续解决方案之前。

使用类似于先前问题的动态编程无法解决此问题, 因为此处的当前状态不仅取决于右侧和底部单元, 还取决于左侧和上部单元。我们使用以下方法解决此问题：dijkstra的算法。网格的每个像元代表一个顶点, 相邻像元代表相邻的顶点。我们不会从这些单元格中生成一个明确的图形, 而是将使用dijkstra算法中的矩阵。

在下面的代码中

Dijkstra算法的实现

用来。更改以下实现的代码以应对矩阵表示的隐式图。还请参见下面的代码中dx和dy数组的使用, 这些数组用于简化访问每个像元的相邻顶点的过程。

C ++

//C++ program to get least cost path in a grid from
//top-left to bottom-right
#include <bits/stdc++.h>
using namespace std;
  
#define ROW 5
#define COL 5
  
//structure for information of each cell
struct cell
{
     int x, y;
     int distance;
     cell( int x, int y, int distance) :
         x(x), y(y), distance(distance) {}
};
  
//Utility method for comparing two cells
bool operator<( const cell& a, const cell& b)
{
     if (a.distance == b.distance)
     {
         if (a.x != b.x)
             return (a.x <b.x);
         else
             return (a.y <b.y);
     }
     return (a.distance <b.distance);
}
  
//Utility method to check whether a point is
//inside the grid or not
bool isInsideGrid( int i, int j)
{
     return (i>= 0 && i <COL && j>= 0 && j <ROW);
}
  
//Method returns minimum cost to reach bottom
//right from top left
int shortest( int grid[ROW][COL], int row, int col)
{
     int dis[row][col];
  
     //initializing distance array by INT_MAX
     for ( int i = 0; i <row; i++)
         for ( int j = 0; j <col; j++)
             dis[i][j] = INT_MAX;
  
     //direction arrays for simplification of getting
     //neighbour
     int dx[] = {-1, 0, 1, 0};
     int dy[] = {0, 1, 0, -1};
  
     set<cell> st;
  
     //insert (0, 0) cell with 0 distance
     st.insert(cell(0, 0, 0));
  
     //initialize distance of (0, 0) with its grid value
     dis[0][0] = grid[0][0];
  
     //loop for standard dijkstra's algorithm
     while (!st.empty())
     {
         //get the cell with minimum distance and delete
         //it from the set
         cell k = *st.begin();
         st.erase(st.begin());
  
         //looping through all neighbours
         for ( int i = 0; i <4; i++)
         {
             int x = k.x + dx[i];
             int y = k.y + dy[i];
  
             //if not inside boundary, ignore them
             if (!isInsideGrid(x, y))
                 continue ;
  
             //If distance from current cell is smaller, then
             //update distance of neighbour cell
             if (dis[x][y]> dis[k.x][k.y] + grid[x][y])
             {
                 //If cell is already there in set, then
                 //remove its previous entry
                 if (dis[x][y] != INT_MAX)
                     st.erase(st.find(cell(x, y, dis[x][y])));
  
                 //update the distance and insert new updated
                 //cell in set
                 dis[x][y] = dis[k.x][k.y] + grid[x][y];
                 st.insert(cell(x, y, dis[x][y]));
             }
         }
     }
  
     //uncomment below code to print distance
     //of each cell from (0, 0)
     /*
     for (int i = 0; i <row; i++, cout <<endl)
         for (int j = 0; j <col; j++)
             cout <<dis[i][j] <<" ";
     */
     //dis[row - 1][col - 1] will represent final
     //distance of bottom right cell from top left cell
     return dis[row - 1][col - 1];
}
  
//Driver code to test above methods
int main()
{
     int grid[ROW][COL] =
     {
         31, 100, 65, 12, 18, 10, 13, 47, 157, 6, 100, 113, 174, 11, 33, 88, 124, 41, 20, 140, 99, 32, 111, 41, 20
     };
  
     cout <<shortest(grid, ROW, COL) <<endl;
     return 0;
}

Java

//Java program to get least cost path 
//in a grid from top-left to bottom-right
import java.io.*;
import java.util.*;
  
class GFG{
      
static int [] dx = { - 1 , 0 , 1 , 0 };
static int [] dy = { 0 , 1 , 0 , - 1 };
static int ROW = 5 ;
static int COL = 5 ;
  
//Custom class for representing
//row-index, column-index &
//distance of each cell
static class Cell
{
     int x;
     int y;
     int distance;
      
     Cell( int x, int y, int distance) 
     {
         this .x = x;
         this .y = y;
         this .distance = distance;
     }
}
  
//Custom comparator for inserting cells 
//into Priority Queue
static class distanceComparator 
   implements Comparator<Cell>
{
     public int compare(Cell a, Cell b)
     {
         if (a.distance <b.distance)
         {
             return - 1 ;
         }
         else if (a.distance> b.distance)
         {
             return 1 ;
         }
         else { return 0 ;}
     }
}
  
//Utility method to check whether current
//cell is inside grid or not
static boolean isInsideGrid( int i, int j)
{
     return (i>= 0 && i <ROW &&
             j>= 0 && j <COL);
}
  
//Method to return shortest path from 
//top-corner to bottom-corner in 2D grid
static int shortestPath( int [][] grid, int row, int col)
{
     int [][] dist = new int [row][col];
      
     //Initializing distance array by INT_MAX 
     for ( int i = 0 ; i <row; i++)
     {
         for ( int j = 0 ; j <col; j++)
         {
             dist[i][j] = Integer.MAX_VALUE;
         }
     }
      
     //Initialized source distance as
     //initial grid position value
     dist[ 0 ][ 0 ] = grid[ 0 ][ 0 ];
      
     PriorityQueue<Cell> pq = new PriorityQueue<Cell>(
                   row * col, new distanceComparator());
                    
     //Insert source cell to priority queue
     pq.add( new Cell( 0 , 0 , dist[ 0 ][ 0 ]));
     while (!pq.isEmpty())
     {
         Cell curr = pq.poll();
         for ( int i = 0 ; i <4 ; i++)
         {
             int rows = curr.x + dx[i];
             int cols = curr.y + dy[i];
              
             if (isInsideGrid(rows, cols))
             {
                 if (dist[rows][cols]> 
                     dist[curr.x][curr.y] + 
                     grid[rows][cols])
                 {
                      
                     //If Cell is already been reached once, //remove it from priority queue
                     if (dist[rows][cols] != Integer.MAX_VALUE)
                     {
                         Cell adj = new Cell(rows, cols, dist[rows][cols]);
                                         
                         pq.remove(adj);
                     }
                      
                     //Insert cell with updated distance 
                     dist[rows][cols] = dist[curr.x][curr.y] +
                                        grid[rows][cols];
                                         
                     pq.add( new Cell(rows, cols, dist[rows][cols]));
                 }
             }
         }
     }
     return dist[row - 1 ][col - 1 ];
}
  
//Driver code
public static void main(String[] args) 
throws IOException
{
     int [][] grid = { { 31 , 100 , 65 , 12 , 18 }, { 10 , 13 , 47 , 157 , 6 }, { 100 , 113 , 174 , 11 , 33 }, { 88 , 124 , 41 , 20 , 140 }, { 99 , 32 , 111 , 41 , 20 } };
                       
     System.out.println(shortestPath(grid, ROW, COL));
}
}
  
//This code is contributed by jigyansu

输出如下：

327
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: