首页 > 代码库 > 矩阵中的最小路径
矩阵中的最小路径
package 数阵中的最优路径;import java.util.Scanner;public class Main2 { /** * 数阵中的最小路径搜索 * 1:设计要点 * 应用动态规划设计从右下角逐行至左上角,确定n,m后,随机产生的整数二维数组a(n,m)作矩阵输出同时赋值给部分和数组b(n,m). * 数组b(i,j)为点(i,j)到到右下角的最小数值和stm(i,j)是点(i,j)向右(R)或向下(D)或向右下(0)的路标数组 * 注意到最后一行与最后一列各数只有一个出口,于是b[n][m]开始向左逐个推出同行的b[n][j](j=m-1,.....1);想上逐个推出同列 * b(i,m)(i = n-1,......1); * b(i,j)与stm(i,j)的值,由同一列下面的值b(i+1,j),与同一行右边的值b(i,j+1),其右下方的值b(i+1,j+1)值决定。 * 设min = min(b(i+1,j+1),b(i+1,j),b(i,j+1)) * 首先作赋值min=b(i+1,j+1),stm(i,j) = "0" * 如果b(i,j+1)<min,则min=b(i,j+1);stm(i,j) = "R" * 如果b(i+1,j)<min,则min=b(i+1,j);stm(i,j) = "D" * 然后赋值b(i,j) = b(i,j)+min. * * * * * * @param args */ public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("输入行数:"); int n = input.nextInt(); System.out.println("输入列数:"); int m = input.nextInt(); int a[][] = new int[30][30]; int b[][] = new int[30][30]; char[][]stm = new char[30][30]; //输出矩阵 for(int i=1;i<=n;i++) { for(int j = 1;j<=m;j++) { a[i][j] = (int)(Math.random()*20+1); b[i][j] = a[i][j]; System.out.printf("%4d",a[i][j]); } System.out.println(); } //计算最小路径 for(int j = m-1;j>=1;j--)//第n行递推为边界条件 { b[n][j]+=b[n][j+1]; stm[n][j]=‘R‘; } for(int i = n-1;i>=1;i--)//第m列递推为边界条件 { b[i][m]+=b[i+1][m]; stm[i][m]=‘D‘; } //逆推求取最小值 for(int i=n-1;i>=1;i--) for(int j = m-1;j>=1;j--) { int min = b[i+1][j+1]; stm[i][j] = ‘0‘; if(min > b[i+1][j]) { min = b[i+1][j]; stm[i][j]=‘D‘; } if(min > b[i][j+1]) { min = b[i][j+1]; stm[i][j] = ‘R‘; } b[i][j]+=min; } System.out.println(b[1][1]); }}
矩阵中的最小路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。