devbox
码创造者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

(十四)：常用十种算法(上)_合并为原问题p的算法

作者：码创造者 | 2024-07-29 01:59:24

赞

踩

合并为原问题p的算法

1.二分查找算法

这个没啥说的，分为两种：递归、非递归。

2.分治算法

2.1简介

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
分治算法可以解决很多问题：

  • 二分搜索
  • 大整数乘法
  • 棋盘覆盖
  • 合并排序
  • 快速排序
  • 线性时间选择
  • 最接近点对问题
  • 循环赛日程表
  • 汉诺塔

2.2步骤

分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
合并：将各个子问题的解合并为原问题的解。
分治(Divide-and-Conquer§)算法设计模式如下：
在这里插入图片描述
其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC§是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC§求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

2.3分治算法解决汉诺塔问题

2.3.1汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
假如每秒钟一次，共需多长时间呢？移完这些金片需要5845.54亿年以上，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

2.3.2汉诺塔问题思路分析

汉诺塔游戏的演示和思路分析:
如果是有一个盘， A->C
如果我们有 n >= 2 情况，我们总是可以看做是两个盘：

  • 1.最下边的盘
  • 2.上面的盘

先把 最上面的盘 A->B
把最下边的盘 A->C
把B塔的所有盘 从 B->C

2.3.3代码

  //哈诺塔的移动方法
    //使用分治算法
    public static void hannoiTower(int num,char a,char b,char c){
        //如果只有一个盘
        if (num==1){
            System.out.println("第1个盘子从"+a+"->"+c);
        }else{
            //如果是n>=2,我们总是可以看做两个盘1，最下面的一个盘2，上面的所有的盘
            //1、先把上面的所有的盘A->B,移动过程会使用到c
            hannoiTower(num-1,a,c,b);
            //2、把所有的下面的盘从A->C
            System.out.println("第"+num+"个盘从"+a+"->"+c);
            //3、把B塔的所有盘从B->C,移动过程使用到A塔
            hannoiTower(num-1,b,a,c);

        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

3.动态规划算法

3.1动态规划算法介绍

动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
动态规划可以通过填表的方式来逐步推进，得到最优解.

3.2应用场景-背包问题

背包问题：有一个背包，容量为4磅 ， 现有如下物品
在这里插入图片描述

  • 要求达到的目标为装入的背包的总价值最大，并且重量不超出背包容量
  • 要求装入的物品不能重复

3.2.1思路分析和图解

背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是：每种物品都有无限件可用)
这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果：
(1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0
(2) 当w[i]> j 时：v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略
(3) 当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}
// 当 准备加入的新增的商品的容量小于等于当前背包的容量,
// 装入的方式:
v[i-1][j]： 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值
v[i-1][j-w[i]] ： 装入i-1商品，到剩余空间j-w[i]的最大值
当j>=w[i]时： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} :

在这里插入图片描述

3.2.2代码

public static void main(String[] args) {
        int[] w={1,4,3};//物品重量
        int[] val={1500,3000,2000};//物品价值
        int m=4;//背包的容量
        int n=val.length;//物品的个数
        //创建二维数组
        //表示在前i个物品中能够装入容量为j的背包中的最大价值
        int[][] v=new int[n+1][m+1];
        //为了记录放入商品的情况，我们定义一个二维数组
        int[][] path=new int[n+1][m+1];
        //初始化第一行第一列，这里在本程序中可以不去处理，因为默认就是0
        for (int i=0;i<v.length;i++){
            v[i][0]=0;
            //将第一列设置为0
        }
        for (int i=0;i<v[0].length;i++){
            v[0][i]=0;
            //将第一行设置为0
        }
        for (int i=1;i<v.length;i++){//不处理第一行
            for (int j=1;j<v[0].length;j++){//不处理第一列
                //公式
                if (w[i-1]>j){
                    v[i][j]=v[i-1][j];
                }else {
                    //说明：因为我们的i是从1开始的
                    //v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
                    //为了记录商品存放到背包的情况，我们不能简单的使用上面的公式，需要使用if-else
                    if (v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        //把当前的情况记录到path
                        path[i][j]=1;
                    }else {
                        v[i][j]=v[i-1][j];
                    }
                }

            }

        }
        //输出v，看看目前的情况
        for (int i=0;i<v.length;i++){
            for (int j=0;j<v[i].length;j++){
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("==========");
        //输出最后我们是放入的哪些商品
        //遍历
        //这样输出会把所有的放入情况都得到，其实我们只需要最后的放入
//        for (int i=0;i<path.length;i++){
//            for (int j=0;j<path[i].length;j++){
//                if (path[i][j]==1){
//                    System.out.printf("第%d个商品放入背包\n",i);
//                }
//
//            }
//        }
        int i=path.length-1;//行的最大下标
        int j=path[0].length-1;//列的最大下标
        while (i>0&&j>0){//从path开始往后找
            if (path[i][j]==1){
                System.out.printf("第%d个商品放入背包\n",i);
                j-=w[i-1];
            }
            i--;
        }

    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

4.KMP算法

4.1应用场景

字符串匹配问题：：
有一个字符串 str1= “BBC ABCDAB ABCDABCDABDE”，和一个子串 str2=“ABCDABD”
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
要求：使用KMP算法完成判断，不能使用简单的暴力匹配算法.

4.2KMP算法介绍

KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法，Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串Р的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H.Morris三人于1977年联合发表，故取这3人的姓氏命名此算法， KMP方法算法就利用之前判断过信息，通过一个next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间
参考资料: https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

4.3思路分析

1、首先，用str1的第一个字符和str2的第一个字符去比较，不符合，关键词向后移动一位。
在这里插入图片描述
2、重复第一步，还是不符合，再后移。

在这里插入图片描述
3、一直重复一直到str1与str2有第一个字符重合为止。
在这里插入图片描述

4、接着比较字符串和搜索词的下一个字符，还是符合
在这里插入图片描述
5、遇到str1与str2对应的字符不符合
在这里插入图片描述
6.这时候，想到的是继续遍历Strl的下一个字符，重复第1步。(其实是很不明智的，因为此时BCD已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。)
在这里插入图片描述
7、怎么做到把刚刚重复的步骤省略掉？可以根据str2计算出一张部分匹配表，表的产生后面说。
在这里插入图片描述
8.已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数:
移动位数=已匹配的字符数–对应的部分匹配值
因为6-2等于4，所以将搜索词向后移动4位。
9、因为空格与c不匹配，搜索词还要继续后移，这时，已经匹配的字符数为2（“AB”），对应的部分匹配值为0。所以移动位数=2-0，结果为2，于是将搜索的词向后移二位。
在这里插入图片描述
10、因为空格与A不匹配，继续后移一位。
在这里插入图片描述
11、逐位比较，直到发现C与D不匹配。于是，移动位数=6-2，继续将搜索词向后移动4位。
在这里插入图片描述
12、逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。

在这里插入图片描述

4.4部分匹配表的产生

要解释清楚这个问题，首先要介绍什么是前缀，什么是后缀。
比如：字符串“bread”。
前缀有：b，br，bre，brea。
后缀有：read，ead，ad，d
部分匹配值就是前缀和后缀最长的共有元素的长度。以“ABCDABD”。
“A”的前缀和后缀都是空集，共有元素长度为0；
“AB”的前缀为A,后缀为B,共有的元素长度为0；
“ABC”的前缀为A,AB,后缀为BC,C,共有元素长度0。
“ABCD”的前缀为A,AB,ABC,后缀为BCD,CD,D,共有的元素长度为0；
部分匹配表的实质是，有时候，字符串头部和尾部会有重复。比如，“ABCDAB”之后有两个AB,那么他的部分匹配值就是2(AB的长度)。搜索词移动的时候，第一个AB向后移动4位，就可以来到第二个AB位置。

4.5代码

public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1="BBC ABCDAB ABCDABCDABDE";
        String str2="ABCDABD";
        int[] next=kmpNext("ABCDABD");
        System.out.println("next="+ Arrays.toString(next));
        int index=kmpSearch(str1,str2,next);
        System.out.println(index);
    }
    //写出我们的kmp搜索算法
    /**
     *
     * @param str1 原字符串
     * @param str2 子串
     * @param next 子串部分匹配表
     * @return -1是没有匹配到 否则就是第一个匹配的位置
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        //遍历
        for (int i=0,j=0;i<str1.length();i++){
            //需要处理str.charAt(i)!=str2.charAt(j),去调整j的大小
            while(j>0&&str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }
            if (str1.charAt(i)==str1.charAt(j)){
                j++;
            }
            if (j==str2.length()){
                return i-j+1;
            }
        }
        return -1;

    }

    //获取到一个字符串子串，他的部分匹配值
    public static int[] kmpNext(String dest){
        //创建一个next数组，保存部分匹配值
        int[] next=new int[dest.length()];
        next[0]=0;//如果字符串是长度为1，他的部分匹配值就是0
        for (int i=1,j=0;i<dest.length();i++){
            //当dest.charAt(i)!=dest.charAt(j),我们徐亚从next[j-1]获取新的j
            //直到我们发现有这个条件成立时候，才退出
            //这是kmp算法的核心点
            while (j>0&&dest.charAt(i)!=dest.charAt(j)){
                j=next[j-1];
            }
            //当这个条件满足时，部分匹配值+1
            if (dest.charAt(i)==dest.charAt(j)){
                j++;
            }
            next[i]=j;
        }
        return next;

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

5.贪心算法

5.1贪心算法介绍

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

5.2贪心算法应用

假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号。
在这里插入图片描述

5.2.1思路分析

如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算10个子集， 如图:
在这里插入图片描述
使用贪婪算法，效率高:
目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合:

  • 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
  • 将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
  • 重复第1步直到覆盖了全部的地区

5.2.2代码

// A code block
public static void main(String[] args) {
        //创建广播电视台，放入一个Map
        Map<String,HashSet> broadcast=new HashMap<String, HashSet>();
        //放入各电视台
        HashSet<String> hashSet=new HashSet<String>();
        hashSet.add("北京");
        hashSet.add("上海");
        hashSet.add("天津");
        //放第二组
        HashSet<String> hashSet2=new HashSet<String>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3=new HashSet<String>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");

        HashSet<String> hashSet4=new HashSet<String>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5=new HashSet<String>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        //加入到map中
        broadcast.put("k1",hashSet);
        broadcast.put("k2",hashSet2);
        broadcast.put("k3",hashSet3);
        broadcast.put("k4",hashSet4);
        broadcast.put("k5",hashSet5);
        //存放所有的地区
        HashSet<String> allAreas=new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        allAreas.add("深圳");

        //创建一个ArrayList，存放选择的电台的集合
        ArrayList<String> selects=new ArrayList<>();
        //定义一个临时的集合，在遍历的过程中。存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        HashSet<String> tempSet=new HashSet<>();
        //定义一个maxKey，保存再一次遍历过程中，能够覆盖的最大未覆盖地区对应的电台的key
        //如果maskKey不为空，则会加入到selectKey中
        String maxKey=null;
        while(allAreas.size()!=0){//如果allArae不为0表示还没有覆盖所有的地区
            //每进行一次while循环，需要
            maxKey=null;
            //遍历broadcasts,取出对应的key
            for (String key:broadcast.keySet()){
                //每进行一次for
                tempSet.clear();
                //当前key能够覆盖的地区
                HashSet<String> areas=broadcast.get(key);
                tempSet.addAll(areas);
                //这句话的意思是求tempSet和allAreas的交集，交集会赋给tempSet
                tempSet.retainAll(allAreas);
                //如果当前这个集合包含的未覆盖地区的数量比maxKey的指向的集合数量还要多
                //就需要重置maxKey
                if ((tempSet.size()>0)&&(maxKey==null||tempSet.size()>broadcast.get(maxKey).size())){
                    maxKey=key;

                }

            }
            //maxKey!=null时候，就应该maxKey加入selects
            if (maxKey!=null){
                selects.add(maxKey);
                //将maxKey指向的广播电视台覆盖的地区从allAreas中去掉
                allAreas.removeAll(broadcast.get(maxKey));
            }

        }
        System.out.println("得到的选择结果是："+selects);


    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84

5.3贪心算法的注意事项

  • 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
  • 比如上题的算法选出的是K1, K2, K3, K5，符合覆盖了全部的地区
  • 但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果K2 的使用成本低于K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的.
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/896696
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号