动态规划——设备更新问题

这里的设备更新问题是一个书上的问题，具体的问题可以参照课本p93，作为动态规划的一个例子，我们现在解释一下动态规划的阶梯思路

可化为最短路径问题的多阶段决策问题

最优化这个问题往往可以按照动态规划来处理，其特点是，可以将一个大问题划分成若干个阶段，逐个处理每一个小问题就得到了大问题。

解题思路：

• 可以通过构造适当的图，将它转化成最短路径问题。从而使问题变得清晰、直观；
• 一旦转化成功，剩下的就是利用迪杰斯特拉算法将最短路径求出来 就是最优的路径

算法的实现

因为利用的是迪杰斯特拉算法，不熟悉的可以参考我这篇博文（java语言） 迪杰斯特拉算法 | dwx-tx的小天地

package com.dwx.passage2;

import java.util.Scanner;

public class shebeigengxinwenti {
    //这是数学建模中地设备更新问题
    public static void main(String[] args) {
        //我计划 先将这些点和边存储进一个邻接矩阵里 在利用迪杰斯特拉算法就得解

        //一共有11个点 需要存储在一个20x20的整数二维数组中
        int[][] a = new int[20][20];
        //先对这个数组进行初始化
        //即 行坐标和列坐标相等就标为0
        //否则标为inf(9999)
        int inf = 9999;
        int i,j;
        for (i=0;i<20;i++){
            for (j=0;j<20;j++){
                if (i==j){
                    a[i][j] = 0;
                }else {
                    a[i][j] = inf;
                }
            }
        }
        System.out.println("=========================================================================================");
        //打印一下我们的初始化后的数组
        for (int[] ints : a) {
            for (int anInt : ints) {
                if (anInt==inf){
                    System.out.print("inf"+"\t");
                }else {
                    System.out.print(anInt+"\t");
                }
            }
            System.out.println();
        }
        System.out.println("=========================================================================================");
        //导入边关系
        //下边我会去数有几条边 然后并记录边的权值
        Scanner scanner = new Scanner(System.in);
        int m;
        int x,y,l;
        /*
        * 参数x:边的起始点
        * 参数y:边的终止点
        * 参数l:边的长度
        * 参数m:边的总个数
        * */
        System.out.print("请输入边数:");
        m = scanner.nextInt();
        for ( j = 1;j<=m;j++){
            System.out.print("请输入起始点:");
            x = scanner.nextInt();
            System.out.print("请输入终止点:");
            y = scanner.nextInt();
            System.out.print("请输入边长度:");
            l = scanner.nextInt();

            a[x][y] = l;
        }
        System.out.println("================录入数据====================");
        for (int[] ints : a) {
            for (int anInt : ints) {
                if (anInt==inf){
                    System.out.print("inf"+"\t");
                }else {
                    System.out.print(anInt+"\t");
                }
            }
            System.out.println();
        }

        //启动迪杰斯特拉算法 求0点到其他点的最短距离
        //一个dis数组用来存储第一行数据
        int[] dis = new int [20];
        for (i=0;i<20;i++){
            dis[i] = a[0][i];
        }

        //一个book[]数组 用来存储我们加入最短路径后的数
        int[] book = new int[20];
        //初始化我们的book数组
        for (i=0;i<20;i++){
            book[i] = 0;
        }
        //将第一个源点读入数组
        book[0] = 1;
        int min;
        int u = 0;
        int v = 0;
        //迪杰斯特拉算法的核心
        for (i=0;i<20;i++){
            min = inf;
            //寻找距离源点最近的点
            for (j=0;j<20;j++){
                if (book[j]==0 && dis[j] < inf){
                    //则把这个数读入book
                    min = dis[j];
                    u = j;
                }
            }
            //将这个点读入book数组
            book[u] = 1;
            for (v=0;v<20;v++){
                //收缩调整最短路径
                if (a[u][v] < inf){
                    if (dis[v]>dis[u]+a[u][v]){
                        dis[v] = dis[u]+a[u][v];
                    }
                }
            }
        }
        System.out.println("=================="+"处理后的最短路径"+"====================");
        for (int di : dis) {
            System.out.print(di+"\t");
        }
        System.out.println();





    }
}

数据

25
0 1 16
1 2 16
2 3 16
3 4 16
0 5 16
1 6 16
2 7 16
3 8 16
4 9 16
5 10 6
6 11 6
7 12 6
8 13 6
10 14 8
11 15 8
12 16 8
14 17 11
15 18 11
17 19 18
5 2 6
6 3 6
7 4 6
10 3 8
11 4 8
14 4 11

Donate