如何在mxn矩阵中找到最低成本路径 [英] How to find lowest cost path in a mxn matrix

问题描述

我有一个mXn矩阵，从[0] [0]单元开始我需要通过尽可能低的成本路径转到[m] [n]，其中cost是单元格值（整数，大于0）。只有可能的移动是向右，向下和对角向下。

我尝试过动态编程方法以找到最低成本但无法打印路径。

例如对于矩阵{（3,2,8），（1,9,7），（0,5,2），（6,4,3）}它的成本为11，但是我的方法是将矩阵转换为成本矩阵，路径打印错误。



预期产量：

成本：11

路径：BBDR（即遍历运动，下方，下方，Rigth）



此处附带的代码我在互联网上找到。请提供我打印路径的片段。



我尝试过：

  public   static   int  minimumCostPathDP（ int  [] [] costMatrix， int  m， int  n）{
  int  [] [] minimumCostPath =  new   int  [m + 1] [n + 1]; 
 minimumCostPath [ 0 ] [ 0 ] = costMatrix [ 0 ] [ 0 ]; 
 
  for （ int  i =  1 ; i< = m; i ++）{
 minimumCostPath [i] [ 0 ] = minimumCostPath [i  -   1 ] [ 0 ] + costMatrix [i] [ 0  ]。 
} 
 
  for （ int  j =  1 ; j< = n; j ++）{
 minimumCostPath [ 0 ] [j] = minimumCostPath [< span class =code-digit> 0 ] [j  -   1 ] + costMatrix [ 0 ] [j]的; 
} 
 
  for （ int  i =  1 ; i< = m; i ++）{
  for （ int  j =  1 ; j< = n; j ++）{
 minimumCostPath [i] [j] = costMatrix [i] [ j] 
 + minimum（minimumCostPath [i  -   1 ] [j  -   1 ]，
 minimumCostPath [i  -   1 ] [j]，
 minimumCostPath [i] [j  -   1 < /跨度>]）; 
} 
} 
  return  minimumCostPath [m] [n]; 
} 
 
  public   static   int  minimum（ int  a， int  b， int  c）{
  return  Math.min（a，Math.min（b，c））; 
} 
 
  public   static   void  main（ String  [] args）{
  int  [ ] [] costMatrix = {{ 3 ， 2 ， 8 }，{ 1 ， 9 ， 7 }，{ 0 ， 5 ， 2 }，{ 6 ， 4 ， 3 }}; 
 System.out.println（ 最低成本： + minimumCostPathDP（costMatrix， 3 ， 2 ））; 
} 
} 

解决方案

此程序用于计算矩阵的最低成本，但没有别的。

此代码没有规定告诉最低成本路径，只有它的价值。



我担心你需要工作一点点并制作一个程序，检查每个可能的路径，直到找到最低成本的路径。



注：Java知道数组的长度，在

  public   static   int  minimumCostPathDP（ int  [] [] costMatrix， int  m， int  n）

， m 和 n 可以可以从 costMatrix 中扣除：

引用：

我在互联网上找到了这里附带的代码。请提供我的代码片段来打印路径。

闻起来像HomeWork！

看起来你擅长搜索互联网，现在是时候自己工作了。

如果您想了解如何打印图表，请检查：

Dijkstra在Java中的最短路径算法 - 教程 [ ^ ]

使用Dijkstra算法在两个顶点之间找到最短路径的Java程序 - Sanfoundry [ ^ ]

感觉很自由实现自己的打印图表方法。

I have an mXn matrix, starting from [0][0] cell I need to go to [m][n] through the lowest possible cost path, where costs are cell values (integer, greater than 0). Only moves possible are right, down and diagonally down.
I have tried Dynamic programming approach to find the lowest cost but could not be able to print the path.
e.g. for matrix {(3,2,8),(1,9,7),(0,5,2),(6,4,3)} its giving cost as 11, but as my approach converting the matrix to cost matrix, the path is printing wrong.

expected output:
cost: 11
path: B B D R (i.e. the traversal movements, Below, Down, Rigth)

The code attached here I have found in the internet. Please provide me snippet to print the path.

What I have tried:

public static int minimumCostPathDP(int[][] costMatrix, int m, int n) {
        int[][] minimumCostPath = new int[m+1][n+1];
        minimumCostPath[0][0] = costMatrix[0][0];
 
        for (int i = 1; i <= m; i++) {
            minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0];
        }
 
        for (int j = 1; j <= n; j++) {
            minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j];
        }
 
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                minimumCostPath[i][j] = costMatrix[i][j]
                                        + minimum(minimumCostPath[i - 1][j - 1],
                                                  minimumCostPath[i - 1][j],
                                                  minimumCostPath[i][j - 1]);
            }
        }
        return minimumCostPath[m][n];
    }
 
    public static int minimum(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
 
    public static void main(String[] args) {
        int[][] costMatrix = { { 3, 2, 8 }, { 1, 9, 7 }, { 0, 5, 2 }, {6, 4, 3} };
        System.out.println("Minimum cost: " + minimumCostPathDP(costMatrix, 3, 2));
    }
}

解决方案

This program is made to compute the minimum cost on a matrix, but nothing else.
This code have no provision to tell the minimum cost path, only its value.

I fear you will have to work a little and make a program that check every possible path until you find the one with minimum cost.

Nota: Java knows the length of arrays, in

public static int minimumCostPathDP(int[][] costMatrix, int m, int n)

, m and n can be deduced from costMatrix

Quote:

The code attached here I have found in the internet. Please provide me snippet to print the path.

Smell like HomeWork!
Looks like you are good at searching internet, now its time to work on your own.

If you would like fo find out how to print diagram, check this:
Dijkstra's shortest path algorithm in Java - Tutorial[^]
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm - Sanfoundry[^]
Feel fre to implement your own printing "diagram" method.

这篇关于如何在mxn矩阵中找到最低成本路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！