• 动态规划算法（1）--矩阵连乘和凸多边形剖分

    目录

    一、动态数组

    1、创建动态数组

    2、添加元素

    3、删除修改元素

    4、访问元素 

    5、返回数组长度

    6、for each遍历数组 

    二、输入多个数字 

    1、正则表达式

    2、has.next()方法

    三、矩阵连乘

    1、什么是矩阵连乘？

    2、动态规划思路

    3、手推m和s矩阵

    4、完整代码

    5、备忘录方法

    四、凸多边形剖分

    1、凸多边形形三角剖分原理

    2、完整代码 

    一、动态数组

    1、创建动态数组

            创建动态数组ArrayList，先调用ArrayList库，之后动态创建语句如下，括号内填写数组元素个数，不知道可以不填。

    1.     import java.util.ArrayList;
    2.     ArrayList num = new ArrayList<>();

    2、添加元素

            使用函数add添加元素。如:添加元素1。

        num.add(1);

            如果创建一个ArrayList num与list1相同（num和list1同为ArrayList类型）

        ArrayList num = new ArrayList<>(list1);

    3、删除修改元素

           使用函数remove删除特定索引的元素。如:删除索引为1的元素。

        num.remove(1);

            使用函数set修改特定索引的元素。如:将索引为1的元素修改为"java"。

        num.set(1,"java");

    4、访问元素 

            使用函数get返回特定索引的元素。如:返回索引1的元素并打印。

        system.out.println(num.get(1));

    5、返回数组长度

            使用函数size（）返回数组长度。如:返回数组num长度并打印

        system.out.println(num.size())

    6、for each遍历数组 

            i是遍历的数组每一个值，num是数组名。

    1.     for(int i:num)
    2.     {
    3.         System.out.println(i);
    4.     }

    二、输入多个数字 

    1、正则表达式

            不需要import其他的东西。输入一串以空格为间隔的数字，字符串形式，经过正则表达式拆解，存入num动态数组中。

            如果数字之间以逗号为间隔，则需要将匹配改为"，\\s+"。

    1.     import java.util.ArrayList;
    2.     ArrayList num = new ArrayList<>();
    3.     String input= new Scanner(System.in).nextLine();
    4.     String[] numbers=input.split("\\s+");
    5.     for (String number : numbers) 
    6.         {
    7.             num.add(Integer.parseInt(number));
    8.         }

    2、has.next()方法

            该方法存在弊端，不能退出循环。

    1.     import java.util.ArrayList;
    2.     ArrayList num = new ArrayList<>();
    3.     Scanner scanner=new Scanner(System.in);
    4.     int n;
    5.     int[] num;
    6.         
    7.     while(scanner.hasNext()) {
    8.          n=scanner.nextInt();
    9.          num.add(n);
    10.     }

    三、矩阵连乘

    1、什么是矩阵连乘？

            不同的结合方式，可以导致不同的数乘次数，因为乘法远大于加法量级，所以加法可以忽视。那什么样的括号选择是可以获得最少的数乘次数呢？

            如果一味的进行枚举，寻找最优的数乘次数需要指数级复杂度。显然这种方式，在较大的个数面前利用计算机是不能解决的。

    2、动态规划思路

    （1）首先定义几个结构，以便后续进行理解。

            A[1:n]，代表1到n个矩阵的连乘积。

            A[i:j]的最少数乘次数记为m[i][j]。

            p数组为矩阵链的值。比如30*35和35*15两个矩阵的矩阵链为30,35,15。

            s数组记录断开位置。

    （2）矩阵连乘遵循最优子结构，也就是说矩阵连乘的各子结构都是最优的。

            假设A[1:4]的最优子结构是 (A_1A_2)(A_3A_4) ，那么A[1:2]的最优子结构一定是(A_1A_2)。

            根据上面两条，我们能得出A[i:j]的最少数乘次数记为m[i][j]，

    3、手推m和s矩阵

            m矩阵和s矩阵几乎同步计算，仅保留上三角形，主对角线均为全0，依次按对角线进行计算，每计算完一条对角线向右上平移一条对角线。

            下面给出m[1][3]和s[1][3]的计算，可以看到从1断开（A_1(A_2A_3)）小于从2分割((A_1A_2)A_3)的值，所以m[1][3]选择较小者7875，s[1][3]=1。

            如果求解A[1:6]的最优解的匹配方式，倒序执行上面s步骤。

    4、完整代码

    1. import java.util.Scanner;
    2. import java.util.ArrayList;
    3. public class matrixplusnew {
    4.     public static void main(String[] args)
    5.     {
    6.         ArrayList num = new ArrayList<>();
    7.         String input= new Scanner(System.in).nextLine();
    8.         String[] numbers=input.split("\\s+");
    9.         for (String number : numbers) 
    10.         {
    11.             num.add(Integer.parseInt(number));
    12.         }
    13.  
    14.         int size=num.size()-1;
    15.         //6*6
    16.         int [][] m=new int[size+1][size+1];
    17.         int [][] s=new int[size+1][size+1];
    18.         MatrixChain(num,m,s);
    19.         //输出m数组
    20.         for(int i=1;i1;i++)
    21.         {
    22.             for(int j=1;j1;j++)
    23.             {
    24.                 System.out.print(m[i][j]);
    25.                 System.out.print("\t");
    26.             }
    27.             System.out.println("");
    28.         }
    29.         //输出s数组
    30.         for(int i=1;i1;i++)
    31.         {
    32.             for(int j=1;j1;j++)
    33.             {
    34.                 System.out.print(s[i][j]);
    35.                 System.out.print("\t");
    36.             }
    37.             System.out.println("");
    38.         }
    39.         //输出A[1:6]的匹配方式
    40.         Traceback(1, 6, s);
    41.  
    42.     }
    43.     //m数组和s数组生成
    44.     public static void MatrixChain(ArrayListp,int [][]m,int [][]s) {
    45. 		int n = p.size() - 1;
    46. 		for (int i = 1; i <= n; i++) {
    47. 			m[i][i] = 0;
    48. 		}
    49.  
    50. 		for (int r = 2; r <= n; r++) 
    51.         {
    52. 			for (int i = 1; i <= n - r + 1; i++) 
    53.             {
    54. 				int j = i + r - 1;    //这个位置非常巧妙，可以确保对角线依次执行
    55. 				m[i][j] = m[i + 1][j] + p.get(i - 1) * p.get(i) * p.get(j);//由于第二条对角线，依赖于第一条对角线计算m[i][i],m[i][i]值为0，故省略。
    56. 				s[i][j] = i;
    57.  
    58. 				for (int k = i + 1; k < j; k++)
    59.                  {
    60. 					int t = m[i][k] + m[k + 1][j] + p.get(i - 1) * p.get(k) * p.get(j);
    61. 					if (t < m[i][j]) 
    62.                     {
    63. 						m[i][j] = t;
    64. 						s[i][j] = k;
    65. 					}
    66. 				}
    67. 			}
    68. 		}
    69.     }
    70.     //获得括号匹配方式
    71.     private static void Traceback(int i,int j,int[][]s)
    72.     {
    73.         if(i==j)
    74.             return;
    75.         Traceback(i, s[i][j],s);    //单独写每两个子结构的最优解，可以供读者合成匹配方式
    76.         Traceback(s[i][j]+1,j,s);
    77.         System.out.print("A"+i+", "+s[i][j]);
    78.         System.out.println(" and A"+(s[i][j]+1)+", "+j);
    79.     }
    80. }

    5、备忘录方法

            备忘录算法自顶向下计算，但他不够灵活，每次计算完整矩阵链的最优次序。其中p，m数组都为类外数组，所有函数均可使用。通过减少重复计算，减少时间复杂度。

    1. public static int memoizedmatrixChain(int n){
    2. 	for (int i=0;i<=n;i++){
    3. 		for(int j=0;j<=n;j++){
    4. 			m[i][j]=0;
    5. 		}
    6. 	}//初始化备忘录数组
    7. 	return lookupChain(1,n);
    8. }
    9. public static lookupChain(int i,int j){
    10. 	if(m[i][j]>0)
    11. 		return m[i][j];//如果该项子问题有记录，返回该记录
    12. 	if(i==j)
    13. 		return 0;//如果相乘的两个矩阵相等，则返回0
    14. 	int u=lookupChain(i+1,j)+p[i-1]*p[i]p[j];//递归调用
    15. 	s[i][j]=i;//存储最佳断点
    16. 	for(int k=i+1;k//这里面将断点从i+1开始，可以断链的点直到j-1为止
    17. 		int t=lookupChain(i,k)+lookupChain(k+1,j)+p[i-1]*p[k]*p[j];
    18. 		if(t
    19. 			u=t;
    20. 			s[i][j]=k;
    21. 		}
    22. 	}
    23. 	m[i][j]=u;
    24. 	return u;
    25. }

    四、凸多边形剖分

            凸多边形三角剖分问题类似于矩阵连乘，都是利用动态规划分成子问题，对子问题递归求解。

    1、凸多边形形三角剖分原理

            通过不同的拆分方法，假设不同边有不同的权值，那么或者不同的组合方式有不同的函数映射，那么不同的三角剖分方式就会存在不同的解，那么最优解怎么求呢？

            类比于矩阵连乘的规律，我们也对不同的组合方式加括号表示。最后凸多边形剖分问题也表示为多个子问题叠加的解。

            那么根据矩阵连乘，有下面这种最优解的产生形式，可以根据不同的加权的关系写出函数关系，变成矩阵连乘问题。

    2、完整代码 

    1. public class MinWeightTriangulation {
    2.     public static void main(String [] args)
    3.     {
    4.         int size=5;
    5.         int m[][]=new int[size+1][size+1];
    6.         int s[][]=new int[size+1][size+1];
    7.         //定义权值
    8.         int num[][]= {{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0}};
    9.         Triangle(num,m,s);
    10.         for(int i=1;i1;i++)
    11.         {
    12.             for(int j=1;j1;j++)
    13.             {
    14.                 System.out.print(m[i][j]);
    15.                 System.out.print("\t");
    16.             }
    17.             System.out.println("");
    18.         }
    19.         Traceback(1, 5, s);
    20.     }
    21.     //计算最优值
    22.     public static void Triangle(int[][]num,int[][]m,int[][]s)
    23.     {
    24.         int n=5;
    25.         for(int i=1;i<=n;i++)
    26.             m[i][i]=0;
    27.         for(int r=2;r<=n;r++)
    28.         {
    29.             for(int i=1;i<=n-r+1;i++)
    30.             {
    31.                 int j=i+r-1;
    32.                 m[i][j]=m[i+1][j]+Weight(i-1, i, j, num);
    33.                 s[i][j]=i;
    34.                 for(int k=i+1;k
    35.                 {
    36.                     int t=m[i][k]+m[k+1][j]+Weight(i-1, k, j, num);
    37.                     if(t
    38.                     {
    39.                         m[i][j]=t;
    40.                         s[i][j]=k;
    41.                     }
    42.  
    43.                 }
    44.             }
    45.         }
    46.     }
    47.     //权重计算
    48.     public static int Weight(int i,int j,int k,int[][]num)
    49.     {
    50.         return num[i][j]+num[j][k]+num[i][k];
    51.     }
    52.     //返回匹配方式
    53.     public static void Traceback(int i,int j,int[][]s)
    54.     {
    55.         if(i==j)
    56.             return;
    57.         Traceback(i, s[i][j],s);
    58.         Traceback(s[i][j]+1,j,s);
    59.         System.out.print("A"+i+", "+s[i][j]);
    60.         System.out.println(" and A"+(s[i][j]+1)+", "+j);
    61.     }
    62. }

  • 相关阅读:
    NR 物理层 卷积
    漏洞-Alibaba Nacos derby 远程代码执行漏洞
    Lambda表达式
    【Python爬虫】requests库get和post方法使用
    Angular知识点系列（5）-每天10个小知识
    Part2_扩展MATSIM_Subpart3_个人汽车交通_第12章 交通信号灯和车道
    Linux内核源码分析 (B.3) 深入理解 Linux 物理内存分配全链路实现
    tabnine不能设置弹窗提示了
    Excel-VBA 快速上手（二、条件判断和循环）
    【漏洞复现】WiseGiga NAS远程命令执行漏洞
  • 原文地址：https://blog.csdn.net/m0_60177079/article/details/133465712