实验二 动态规划.doc

西北师范大学数信学院学生实验报告 学号： 201271040138 2013 年 10 月 30 日 系别 计算机科学与工程学院 专业 软件工程 班级 12软件 姓名 赵海龙 课程名称 面向对象程序设计 课程类型 实验 学时数 实验名称 JAVA基本程序设计结构 实验目的和要求： 1． 掌握JAVA基本知识 2． 用JAVA的知识体系编程 实验内容： 动态规划算法 设平面上有一个m×n 的网格，将左下角的网格点标记为（0,0）而右上角的网格点标记为（m,n）。某人想从（0,0）出发沿网格线行进到达（m,n），但是在网格点（i,j）处他只能向下行进或者向右行进，向下行进的代价为aij（amj ＝＋∞），向右行进的代价是bij（bin ＝＋∞）。试设计一个动态规划算法，在这个网格中为该旅行者寻找一条代价最小的旅行路线。 代码： import java.util.*; import static java.lang.Math.*; public class MN { public static void main(String[] args) { final int m = 5; final int n = 5; // 定义向上，向右的代价 ，以及最优代价 int[][] Cost = new int[m+1][n+1]; int[][] Down = new int[m][n+1]; int[][] Right = new int[m+1][n]; int count = 0, i = 0, j = 0; // 随机的产生向上代价数组Above，并输出 for(i = 0; i m; i++) for(j = 0; j n+1; j++) { Random rand = new Random(); Down[i][j] = (rand.nextInt(5)+5); } System.out.printf(Down:\n); for(i = 0; i m; i++) { for(j = 0; j n+1; j++) { System.out.printf(%5d, Down[i][j]); } System.out.println(\n); } // 随机的产生向上代价数组Right，并输出 for(i = 0; i m+1; i++) for(j = 0; j n; j++) { Random rand = new Random(); Right[i][j] = (rand.nextInt(5)+5); } System.out.printf(Right:\n); for(i = 0; i m+1; i++) { for(j = 0; j n; j++) { System.out.printf(%5d, Right[i][j]); } System.out.println(\n); } // 求出最优代价数组Cost并输出 Cost[0][0] = 0; for(i = 1; i m+1; i++) Cost[i][0] = Cost[i-1][0] + Down[i-1][0]; for(j = 1; j n+1; j++) Cost[0][j] = Cost[0][j-1] + Right[0][j-1]; for(i = 0; i m; i++) for(j = 0; j n; j++) Cost[i+1][j+1] = min((Cost[i+1][j] + Right[i+1][j]), (Cost[i][j+1] + Down[i][j+1])); System.out.printf(最优距离:\n); for(i = 0; i m+1; i++) { for(j = 0; j n+1; j++) { System.out.printf(%5d,Cost[i][j]); }