精华内容
下载资源
问答
  • 期末了,通过写博客的方式复习一下dp,把自己理解的dp思想通过样例全部说出来说说我所理解的dp思想dp一般用于解决多阶段决策问题,即每个阶段都要做一个决策,全部的决策是一个决策序列,要你求一个最好的决策...

    期末了,通过写博客的方式复习一下dp,把自己理解的dp思想通过样例全部说出来

    说说我所理解的dp思想

    dp一般用于解决多阶段决策问题,即每个阶段都要做一个决策,全部的决策是一个决策序列,要你求一个

    最好的决策序列使得这个问题有最优解

    将待求解的问题分为若干个相互联系的子问题,只在第一次遇到的时候求解,然后将这个子问题的答案保存

    下来,下次又遇到的时候直接拿过来用即可


    dp和分治的不同之处在于分治分解而成的子问题必须没有联系(有联系的话就包含大量重复的子问题,那

    么这个问题就不适宜分治,虽然分治也能解决,但是时间复杂度太大,不划算),所以用dp的问题和用分

    治的问题的根本区别在于分解成的子问题之间有没有联系,这些子问题有没有重叠,即有没有重复子问题


    dp和贪心的不同之处在于每一次的贪心都是做出不可撤回的决策(即每次局部最优),而在dp中还有考察

    每个最优决策子序列中是否包含最优决策子序列,即是否具有最优子结构性质,贪心中每一步都只顾眼前

    最优,并且当前的选择是不会依赖以前的选择的,而dp,在选择的时候是从以前求出的若干个与本步骤

    相关的子问题中选最优的那个,加上这一步的值来构成这一步那个子问题的最优解


    讲得再多不如看几个很经典的样例,带你初步入门dp

    我不会讲很多具体该怎么做,而是剖析这些经典例题中的dp思想,真真正正的1懂得了dp思想的话,做题事

    半功倍(自己深有体会)


    样例1:数字三角形问题

    7

    3 8

    8 1 0

    2 7 4 4

    4 5 2 6 5

    从顶部向下走,每次只能走下面或者右下,走完全程,问你怎么走使得权值最大(问题描述不是很详细,关

    于数字三角形问题是什么问题请百度)

    那么dp的思想到底是怎么体现的呢?

    dp是要先分解成很多相互联系的子问题,要解决一个子问题,依赖于前面和此子问题相关的已经解决的子

    问题中选一个最优的加上这个子问题的解,就是这个子问题的最优解

    具体做法:

    1.分析问题的最优解,找出最优解的性质,并刻画其结构特征:

    问题的最优解:所有走法中最大的权值是多少?

    最优解的性质和结构特征:只能向正下或者右下走,每走一行的最大权值等于前面一行的最大权值加上这一

    行的走的两个方向中的最大值

    2.递归的定义最优值:

    要找到从0行出发的最优值,就要找到从第1行出发的最优值

    要找到从1行出发的最优值,就要找到从第2行出发的最优值

    ………………………

    要找到第3行出发的最优值,就要找到从最后一行出发的最优值

    为什么是这样呢?我们分析一下

    题目要你求从0行出发的最优值,那么我们就是要找到从第一行出发的最优值,加上第0行到第1行的最优值

    但是,很重要的一点,我们需要递归求解,要先求解从倒数第一行出发的最优值,然后根据从倒数第一行出

    发的最优值求出从倒数第二行出发的最优值

    3.采用自底向上的方式计算问题的最优值:

    这个就是我上面说的,要先求解从倒数第一行出发的最优值,然后根据从倒数第一行出发的最优值求出从倒

    数第二行出发的最优值,自底向上的计算,迭代的方式求解子问题

    4.根据计算最优值时间得到的信息,构造最优解

    这个就是问你具体是怎么走的,我们需要在求解子问题的时候保存一些信息,采用构造出最优解(最优值和

    最优解是不同的,最优值在本问题中是一个走法中权值之和最大的那一个,而最优解是具体的走法),这里

    题目没有要求就是不用去构造最优解,构造起来也挺麻烦的。。。。

    解法:

    dp【i】【j】:代表从第i行第j列出发得到的最优值

    dp【i】【j】=max(dp【i+1】【j】,dp【i+1】【j+1】)+a【i】【j】

    表示从第i行第j列出发的最优值等于到i+1行的两种走法中最大的那一个加上出发点的权值

    贴个链接:

    https://www.cnblogs.com/yinbiao/p/8995253.html

    贴个代码:

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;
        scanf("%d",&n);//n行
        int a[n][n];
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        int dp[n][n];
        memset(dp,0,sizeof(dp));
        for(int j=0;j<n;j++)
        {
            dp[n-1][j]=a[n-1][j];
        }
        for(int i=n-2;i>=0;i--)
        {
            for(int j=0;j<=i;j++)
            {
                dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
            }
        }
        printf("%d\n",dp[0][0]);
        return 0;
    }


    经典样例2:最长公共子序列问题 (LCS问题)

    给你两个序列,问你他们的最长LCS序列的长度是多少?(序列可以是不连续的,只要元素的相对位置一

    样)(不了解LCS问题的自行百度)

    那么在LCS问题中dp的思想体现在哪里呢?

    重复子问题:(超级容易发现的一个)

    我们要求x1~xi,Y1~Yj的LCS,那么是不是要求x1~xi-1,Y1~Yi-1的LCS

    我们要求x1~xi-1,y1~yi-1的LCS,那么是不是要求x1~xi-2,Y1~yi-2的LCS

    所以我们要求的x1~xi,Y1~Yj的LCS这个大问题中,包含了很多的重复子问题

    具体做法:

    c【i】【j】表示x1~xi,Y1~Yj的LCS序列长度

    x【i】==y【j】 c【i】【j】=c【i-1】【j-1】+1

    x【i】!=y【j】  c【i】【j】=max(c【i-1】【j】,c【i】【j-1)

    i==0||j==0 c【i】【j】=0

    贴个代码(求最优值和最优解)

    #include<bits/stdc++.h>
    #define max_v 1005
    using namespace std;
    char x[max_v],y[max_v];
    int dp[max_v][max_v];
    int l1,l2;
    int dfs(int i,int j)
    {
        if(i==-1||j==-1)
            return 0 ;
        if(x[i]==y[j])//来自左上角
        {
            dfs(i-1,j-1);
            cout<<x[i]<<" ";//先递归到最后再输出,,这样就是顺序的
        }
        else
        {
            if(dp[i-1][j]>dp[i][j-1])//来自上面
            {
                dfs(i-1,j);
            }
            else//来自左边
            {
                dfs(i,j-1);
            }
        }
        return 0;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        getchar();
        while(t--)
        {
            scanf("%s",x);
            scanf("%s",y);
            int l1=strlen(x);
            int l2=strlen(y);
            memset(dp,0,sizeof(dp));
            for(int i=1; i<=l1; i++)
            {
                for(int j=1; j<=l2; j++)
                {
                    if(x[i-1]==y[j-1])
                    {
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                    else
                    {
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            printf("%d\n",dp[l1][l2]);
            dfs(l1,l2);
            cout<<endl;
        }
        return 0;
    }
    
    
    /*
    2
    ABCBDAB
    BDCABA
    */


    经典样例三:矩阵连乘问题,纸牌问题,石头合并问题(都是一类问题,一起分析)

    给定n个矩阵{A1,A2…..An},其中A【i】与A【i+1】是可乘的,如何确定计算的次序,使得乘法的总次数最少

    首先我们要明白,计算的次序不同,那么乘法的总次数也不同

    类似的问题:给你n张牌,每张排都有一个数字,相邻的两张牌的权值可以相乘,相乘的两张牌可以合并为

    一张牌,新牌的权值是原来的两张牌的乘积

    这个问题还有石头合并问题都是同一类的问题,属于区间dp问题

    石头合并问题:给你一堆石头,排成一行,相邻的两个石头可以合并,合并成的石头的权值为原来两个石头

    的权值之和

    先来分析矩阵连乘问题:

    给你一个一维数组

    30,35,15,5,10,20,25

    只要相邻的矩阵才可以相乘

    思考一下,dp的思想是如何体现的

    第一步我们是要把问题分解成很多互相有联系的子问题(重复子问题是用dp的基础)

    简单的思考一下,每次矩阵相乘,最简单的就是两个可以相乘的矩阵相乘(A1,A2,A3),那最大的乘法次数就是A1*A2*A3

    但是如果是多个呢,我们是不是可以简化成下面这样

    A【i】,A【i+1】………………….A【k】………………A【j-1】,A【j】

    讲他们分成两个抽象矩阵

    第一个:A【i】….A【k】

    第二个:A【k+1】…..A【j】

    把大问题抽象成两个抽象矩阵相乘,那么更加最简单的那种抽象一下就知道求所有矩阵乘法的最大次数,就

    是求第一个抽象矩阵自己内部要乘的次数和第二个抽象矩阵内部自己要求的乘法次数然后加上这这两个抽象

    矩阵合并为一个大的抽象矩阵要乘的次数

    那么大问题是这样的,大问题里面是不是有很多这样的小问题,而且这些小问题还是重复的,比如A【k】

    的选择不同,那么乘的次序结果也不一样,A【k】的选择可以导致很多问题都有重复的部分,如果多次计

    算的话,无疑是很不明智的,这样的话跟分治就是没有什么区别了,这样的问题就叫做重复子问题

    A【k】的选择不同的话,会导致子问题有很多重复的部分,前面我们说了的,同时A【k】的选择不同的话

    会导致两个抽象矩阵相乘的结果也不一样,所以我们就要在所有的A【k】选择中找一个最小的

    所以我们现在在这个问题里面找到了dp思想的具体体现:大量的重复子问题

    具体做法:

    dp【i】【j】:代表矩阵i,矩阵i+1………….矩阵j的最少乘法次数

    总结上述:

    dp【i】【j】=min(dp【i】【k】+dp【k+1】【j】

    i<=k<=j-1

    贴个代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define max_v 1005
    int dp[max_v][max_v],a[max_v],s[max_v][max_v];
    void f(int i,int j)
    {
        if(i==j)
            return ;
        f(i,s[i][j]);
        f(s[i][j]+1,j);
        printf("A[%d:%d]*A[%d:%d]\n",i,s[i][j],s[i][j]+1,j);
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
    
        for(int i=1;i<=n;i++)
        {
            dp[i][i]=0;
        }
    
        for(int r=2;r<=n;r++)
        {
            for(int i=1;i<=n-r+1;i++)
            {
                int j=i+r-1;
                dp[i][j]=dp[i+1][j]+a[i-1]*a[i]*a[j];
                s[i][j]=i;
                for(int k=i+1;k<j;k++)
                {
                    int t=dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
                    if(t<dp[i][j])
                    {
                        dp[i][j]=t;
                        s[i][j]=k;
                    }
                }
            }
        }
        f(1,n);
    }
    
    /*
    6
    30 35 15 5 10 20 25
    
    A[2:2]*A[3:3]
    A[1:1]*A[2:3]
    A[4:4]*A[5:5]
    A[4:5]*A[6:6]
    A[1:3]*A[4:6]
    */

    分析了矩阵连乘问题,再来分析一下石头合并问题

    石头合并问题:其实这个问题跟矩阵连乘问题真的是一样的

    非常非常的类似

    A1,A2………………….An

    也是分解成两个抽象的石头

    A【i】,A【i+1】………A【k】……….A【j】

    第一个抽象石头:A【i】……..A【k】

    第二个抽象石头:A【k+1】…….A【j】

    我们现在把大问题分解成了两个抽象的石头合并问题

    问的是你合并完成后最小的权值是多少

    大问题的最小权值等于第一个抽象石头合并的权值加上第二个抽象石头合并的权值,再加上这两个抽象的石头合并的权值

    我们知道,A【k】的选择不同,会导致最后权值的不同,也会导致大量重复的子问题(前面在矩阵连乘wen他中具体分析了)

    所以我们要在所有的A【k】选择中,选择一个合并花费最小的

    现在我们把大问题分解成了这样一个问题,那么每个抽象的石头也还可以当初一个大问题继续分解呀,所以

    就分解成了很多子问题

    具体做法:

    dp【i】【j】:代表合并第i到第j个石头的最小花费

    sum【i】:表示1~i个石头的权值之和

    dp【i】【j】=min(dp【i】【k】+dp【k+1】【j】)+sum【j】-sum【i】+a【i】

    为什么是sum【j】-sum【i】+a【i】呢?

    因为我们要合并从第i个石头到第j个石头所需要的花费就是第i个石头到第j个石头的权值的和呀

    贴个代码:

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[n+1];
            for(int i=1; i<=n; i++)
            {
                scanf("%d",&a[i]);
            }
            int sum[n+1];
            int dp[n+1][n+1];
            for(int i=1; i<=n; i++)
            {
                int t=0;
                for(int j=1; j<=i; j++)
                {
                    t=t+a[j];
                }
                sum[i]=t;
            }
            for(int i=1; i<=n; i++)
            {
                dp[i][i]=0;
            }
            for(int r=2; r<=n; r++)
            {
                for(int i=1; i<=n-r+1; i++)
                {
                    int j=i+r-1;
                    int t=dp[i][i]+dp[i+1][j]+sum[j]-sum[i]+a[i];
                    for(int k=i; k<=j-1; k++)
                    {
                        if(t>dp[i][k]+dp[k+1][j]+sum[j]-sum[i]+a[i])
                        {
                            t=dp[i][k]+dp[k+1][j]+sum[j]-sum[i]+a[i];
                        }
                    }
                    dp[i][j]=t;
                }
            }
            printf("%d\n",dp[1][n]);
        }
        return 0;
    }
    
    /*
    样例输入
    3
    1 2 3
    7
    13 7 8 16 21 4 18
    样例输出
    9
    239
    */


    经典样例四:最长递增子序列

    比如

    1,7,3,5,8,4,8

    问你最长的递增的子序列的长度是多少

    这个问题的最优解有多个,但是最优值只有一个:长度为4

    1,3,5,9

    1,3,5,8

    1,3,4,8

    这三个都是最优解,但是他们长度都是一样的,长度为4

    这些是我们看出来的

    那我们如何用dp的思想解题呢

    第一步分解成很多互相有联系的子问题

    要求第n个元素结尾的LIS序列的长度,就要求以第n-1个元素结尾的LIS序列的长度

    要求第n-1个元素结尾的LIS序列的长度,就要求以第n-2个元素结尾的LIS序列的长度

    …………..

    假设第n-1个元素结尾的LIS序列的长度为2,且第n个元素是大于第n-1个元素的(递增的),那么以第n

    个元素结尾的LIS序列的长度不就是以第n-1个元素结尾的LIS序列的长度加上1吗?

    再回过头来看看这些子问题

    他们中是不是含有大量重复的子问题

    dp【n】:代表以第n个元素结尾的LIS序列的长度

    比如我要求dp【n】,就要求dp【n-2】,dp【n-3】

    在要求dp【n-1】的时候,也还要求dp【n-2】,dp【n-3】一次

    这个就是求了很多次,想想当n足够大的时候,子问题足够多的时候,求的重复的子问题是不是很多很多

    这样的话速度太慢

    所以这个时候,dp的作用就是体现出来了,保存已经求解过的子问题的值,下次又遇到这个子问题的时

    候,直接拿出来用就好啦

    做法:

    dp【1】=1

    dp【i】=max(dp【j】+1) 要求:a【j】<a【i】,j<i

    就是在第i个元素的前面找到LIS序列长度最大的,加上1,(先决条件是递增的)

    贴个代码:(最优值和一个最优解)

    #include<bits/stdc++.h>
    using namespace std;
    #define max_v 1005
    int a[max_v],dp[max_v];
    void f(int n,int result)
    {
        bool flag=false;
        if(n<0||result==0)
            return ;
        if(dp[n]==result)
        {
            flag=true;
            result--;
        }
        f(n-1,result);
        if(flag)
            printf("%d ",a[n]);
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            memset(dp,0,sizeof(dp));
            dp[0]=1;
            for(int i=1;i<n;i++)
            {
                int t=0;
                for(int j=0;j<i;j++)
                {
                    if(a[j]<a[i])
                    {
                       if(t<dp[j])
                       {
                           t=dp[j];
                       }
                    }
                }
                dp[i]=t+1;
            }
            int t=0;
            for(int i=0;i<n;i++)
            {
                if(t<dp[i])
                {
                    t=dp[i];
                }
            }
            printf("%d\n",t);
            f(n,t);
            printf("\n");
        }
        return 0;
    }
    /*
    输入:
    7
    1 7 3 5 9 4 8
    输出:
    4
    1 3 4 8*/


    经典样例五:最大子段和问题

    比如:

    -2,11,-4,13,-5,-2

    什么叫最大字段和?就是连续的数字的和最大是多少,注意是段,而不是序列,序列可以是离散的,而段必

    须的连续的

    所以这个问题dp思想体现在哪里呢?

    这个问题其实跟LIS,LCS问题都差不多,都是线性dp问题

    第一步:分解成很多有联系的子问题

    要求以第n个元素结尾的最大字段和是多少,就要求以第n-1个元素结尾的最大字段和是多少

    要求以第n-1个元素结尾的最大子段和是多少,就要求以第n-2个元素结尾的最大字段和是多少

    为什么是这样呢?

    仔细思考一下

    以求第n-1个元素的1最大字段和为例

    如果我们知道了以第n-2个元素的最大字段和是多少,如果是正的,加上第n个元素值即可,如果是负数,

    那还不如不加呢,这样第n个元素的最大字段和还大一点,因为你加上一个负数肯定比原来的数小了呀

    那么dp思想中的重复子问题体现在哪里呢?

    体现在第一步,跟LIS问题中的体现是一样的,这里不再赘述

    贴个代码:(最优解)

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n;
            scanf("%d",&n);
            int a[n+1];
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            int dp[n+1];
            dp[1]=a[1];
            for(int i=2;i<=n;i++)
            {
                int x=dp[i-1];
                if(x<0)
                {
                    x=0;
                }
                dp[i]=x+a[i];
            }
            int maxvalue=dp[1];
            for(int i=2;i<=n;i++)
            {
                if(maxvalue<dp[i])
                {
                    maxvalue=dp[i];
                }
            }
            printf("%d\n",maxvalue);
        }
        return 0;
    }
    /*
    输入:
    2
    6
    -2 11 -4 13 -5 -2
    输出;
    20
    */


    经典样例六:01背包问题

    背包问题可以说是很经典的问题之一了,01背包问题,就是说每个物品只有两种选择,装还不装,且物品

    不可分割

    我先不讲01背包问题应该怎么做,讲01背包里面蕴含的dp思想

    dp适用于多阶段决策问题,就是每个阶段都要做决策,且你做的决策会影响的最终的结果,导致最终结果的值有所不同

    这个决策的概念在01背包里面用的可以说是体现的非常非常的透彻了,因为你每个阶段都要做决策呀,这

    个物品我到底是选还是不选呢

    声明一个 大小为  m[n][c] 的二维数组,m[ i ][ j ] 表示 在面对第 i 件物品,且背包容量为  j 时所能获得的最大价值 ,那么我们可以很容易分析得出 m[i][j] 的计算方法,

    (1). j < w[i] 的情况,这时候背包容量不足以放下第 i 件物品,只能选择不拿

    m[ i ][ j ] = m[ i-1 ][ j ]

    (2). j>=w[i] 的情况,这时背包容量可以放下第 i 件物品,我们就要考虑拿这件物品是否能获取更大的价值。

    如果拿取,m[ i ][ j ]=m[ i-1 ][ j-w[ i ] ] + v[ i ]。 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品,背包容量为j-w[i]时的最大价值,也是相当于为第i件物品腾出了w[i]的空间。

    如果不拿,m[ i ][ j ] = m[ i-1 ][ j ] , 同(1)

    究竟是拿还是不拿,自然是比较这两种情况那种价值最大。

    状态转移方程:

    if(j>=w[i])
         m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
    else
         m[i][j]=m[i-1][j];

    代码如下:(二维dp解决01背包问题,一维dp解决01背包问题)

    #include<bits/stdc++.h>
    using namespace std;
    int ZeroOnePack(int v[],int w[],int n,int c)//v1,v2....vn价值  w1,w2,w3...wn重量 n表示n个物品 c表示背包容量
    {
        int dp[n+1][c+1];
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<=c; j++)
            {
                if(j>=w[i])
                {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//第i个物品放入之后,那么前面i-1个物品可能会因为剩余空间不够无法放入
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                }
    
            }
        }
        return dp[n][c];
    }
    //空间优化,采用一维数组
    int ZeroOnePack_improve(int v[],int w[],int n,int c)//v1,v2....vn价值  w1,w2,w3...wn重量 n表示n个物品 c表示背包容量
    {
        int dp[c+1];
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            for(int j=c; j>=0; j--)
            {
                if(j>=w[i])
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    
            }
        }
        return dp[c];
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
    
            int n,c;
            scanf("%d %d",&n,&c);
            int v[n+1],w[n+1];
            for(int i=1; i<=n; i++)
            {
                scanf("%d",&v[i]);
            }
            for(int i=1; i<=n; i++)
            {
                scanf("%d",&w[i]);
            }
            // printf("%d\n",ZeroOnePack(v,w,n,c));
            printf("%d\n",ZeroOnePack_improve(v,w,n,c));
    
        }
        return 0;
    }
    
    /*
    1
    5 10
    1 2 3 4 5
    5 4 3 2 1
    
    14
    */
    展开全文
  • 大学里一直没搞懂的,软件工程思想,看这个终于搞明白了,语言幽默,例子清晰。
  • 思想品德课中的一例到底
  • 在现在的软件行业,面向对象的思想应该说是没有人不知道的,我们几乎天天都在提面向对象的思想。那到底什么是面向对象的思想,和面向过程有什么区别?大家一起来讨论讨论吧,说说自己的理解,各抒己见。
  • 蒸馏神经网络到底在蒸馏什么?(设计思想篇)

    万次阅读 多人点赞 2018-07-17 14:49:40
    蒸馏神经网络[1],是14年Hinton提出来的一个概念,其最本质的思想是来源于昆虫记里面的故事: “蝴蝶以毛毛虫的形式吃树叶积攒能量逐渐成长,最后变换成蝴蝶这一终极形态来完成繁殖。” 虽然是同一个个体,...

    阅读更多,欢迎关注公众号:论文收割机(paper_reader)

    Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean."Distilling the knowledge in a neural network." arXiv preprint arXiv:1503.02531 (2015)

    1 引言

    蒸馏神经网络[1],是14年Hinton提出来的一个概念,其最本质的思想是来源于昆虫记里面的故事:

    “蝴蝶以毛毛虫的形式吃树叶积攒能量逐渐成长,最后变换成蝴蝶这一终极形态来完成繁殖。”

    虽然是同一个个体,但是在面对不同环境以及不同任务时,个体的形态却是非常不同。不同的形态是为了完成特异性的任务而产生的变化,从而使个体能够更好的适应新的环境。

    比如毛毛虫的形态是为了更方便的吃树叶,积攒能量,但是为了增大活动范围提高繁殖几率,毛毛虫要变成蝴蝶来完成这样的繁殖任务。蒸馏神经网络,其本质上就是要完成一个从毛毛虫到蝴蝶的转变。

    因为在使用神经网络时,训练时候的模型和实际应用的模型往往是相同的,就好像一直是一个毛毛虫,既做了吃树叶积累能量的事情,又去做繁殖这项任务,既臃肿又效率低下。

    所以使用同样形态的模型,一方面会导致模型不能针对特定性的任务来快速学习,另一方面实际应用中如果也是用训练时非常庞大的模型会造成使用开销负担过重。

    蒸馏神经网络想做的事情,本质上更接近于迁移学习(Transfer Learning [2]),当然也可从模型压缩(Model Compression)[3]的角度取理解蒸馏神经网络。

    Hinton的这篇论文严谨的数学思想推导并不复杂,但是主要是通过巧妙的实验设计来验证了蒸馏神经网络的可行性,所以本专题主要从蒸馏的思想以及实验的设计来介绍蒸馏神经网络。而本文主要介绍设计思想部分。

    2 设计思想

    在用神经网络训练大规模数据集时,为了处理复杂的数据分布:一种做法是建立复杂的神经网络模型,例如含有上百层的残差网络,这种复杂的网络往往含有多达几百万个参数;

    另一种做法往往会混合多种模型,将几个大规模的神经网络在同一个数据集上训练好,然后综合(ensemble)多个模型,得到最终的分类结果。

    但是这种复杂模型,一是在新的场景下重新训练成本过高,二是由于模型过于庞大而难以大规模部署(deployment

    所以,最基本的想法就是将大模型学习出来的知识作为先验,将先验知识传递到小规模的神经网络中,之后实际应用中部署小规模的神经网络。这样做有三点依据:

    • 大规模神经网络得到的类别预测包含了数据结构间的相似性

    • 有了先验的小规模神经网络只需要很少的新场景数据就能够收敛;

    • Softmax函数随着温度变量(temperature)的升高分布更均匀

    数据结构间的相似性:

    神经网络模型在预测最终的分类结果时,往往是通过softmax函数产生概率分布的:

                                                                                q_i = \frac{exp(z_i/T))}{\sum_jexp(z_j/T)}                   (1)     

    这里将T定义为温度参数,是一个超参数,q_i是i类的概率值大小。

    比如一个大规模网络,如ImageNet这样的大网络,能够预测上千种类别,正确类别的概率值能够达到0.9,错误类的概率值可能分布在10^-8~10^-3这个区间中。虽然每个错误类别的的概率值都很小,但是10^-3还是比10^-8高了五个数量级,这也反映了数据之间的相似性。

    比如一只狗,在猫这个类别下的概率值可能是0.001,而在汽车这个类别下的概率值可能就只有0.0000001不到,这能够反映狗和猫比狗和汽车更为相似,这就是大规模神经网络能够得到的更为丰富的数据结构间的相似信息。

    将大规模神经网络的soft target作为训练目标

    由于大规模神经网络在训练的时候虽然是通过0-1编码来训练的,由于最后一层往往使用softmax层来产生概率分布,所以这个概率分布其实是一个比原来的0-1 编码硬目标(hard target)更软的软目标(soft target)。这个分布是由很多(0,1)之间的数值组成的。

    同一个样本,用在大规模神经网络上产生的软目标来训练一个小的网络时,因为并不是直接标注的一个硬目标,学习起来会更快收敛。

    更巧妙的是,这个样本我们甚至可以使用无标注的数据来训练小网络,因为大的神经网络将数据结构信息学习保存起来,小网络就可以直接从得到的soft target中来获得知识。

    这个做法类似学习了样本空间嵌入(embedding)信息,从而利用空间嵌入信息学习新的网络。

    随着温度上升,软目标分布更均匀

    公式(1)中,T参数是一个温度超参数,按照softmax的分布来看,随着T参数的增大,这个软目标的分布更加均匀。

    因此:

    1. 首先用较大的T值来训练模型,这时候复杂的神经网络能够产生更均匀分布的软目标;

    2. 之后小规模的神经网络用相同的T值来学习由大规模神经产生的软目标,接近这个软目标从而学习到数据的结构分布特征;

    3. 最后在实际应用中,将T值恢复到1,让类别概率偏向正确类别。

    所以,蒸馏神经网络取名为蒸馏(Distill),其实是一个非常形象的过程。

    我们把数据结构信息和数据本身当作一个混合物,分布信息通过概率分布被分离出来。首先,T值很大,相当于用很高的温度将关键的分布信息从原有的数据中分离,之后在同样的温度下用新模型融合蒸馏出来的数据分布,最后恢复温度,让两者充分融合。这也可以看成Prof. Hinton将这一个迁移学习过程命名为蒸馏的原因。

    阅读更多,欢迎关注公众号:论文收割机(paper_reader)


    参考文献:

    [1] Hinton,Geoffrey, Oriol Vinyals, and Jeff Dean. "Distilling the knowledge in aneural network." arXiv preprint arXiv:1503.02531 (2015).

    [2] Pan,Sinno Jialin, and Qiang Yang. "A survey on transfer learning." IEEE Transactionson knowledge and data engineering 22.10 (2010): 1345-1359.

    [3] Buciluǎ, Cristian, Rich Caruana, andAlexandru Niculescu-Mizil. "Model compression." Proceedings of the12th ACM SIGKDD international conference on Knowledge discovery  and data mining. ACM, 2006.

     

    展开全文
  • dubbo 的 spi 思想什么? 面试官心理分析 继续深入问呗,前面一些基础性的东西问完了,确定你应该都 ok,了解 dubbo 的一些基本东西,那么问个稍微难一点点的问题,就是 spi,先问问你 spi 是啥?然后问问你 dubbo...

    面试题

    dubbo 的 spi 思想是什么?

    面试官心理分析

    继续深入问呗,前面一些基础性的东西问完了,确定你应该都 ok,了解 dubbo 的一些基本东西,那么问个稍微难一点点的问题,就是 spi,先问问你 spi 是啥?然后问问你 dubbo 的 spi 是怎么实现的?

    其实就是看看你对 dubbo 的掌握如何。

    面试题剖析

    spi 是啥?

    spi,简单来说,就是 service provider interface,说白了是什么意思呢,比如你有个接口,现在这个接口有 3 个实现类,那么在系统运行的时候对这个接口到底选择哪个实现类呢?这就需要 spi 了,需要根据指定的配置或者是默认的配置,去找到对应的实现类加载进来,然后用这个实现类的实例对象。

    举个栗子。

    你有一个接口 A。A1/A2/A3 分别是接口A的不同实现。你通过配置 接口 A = 实现 A2,那么在系统实际运行的时候,会加载你的配置,用实现 A2 实例化一个对象来提供服务。

    spi 机制一般用在哪儿?插件扩展的场景,比如说你开发了一个给别人使用的开源框架,如果你想让别人自己写个插件,插到你的开源框架里面,从而扩展某个功能,这个时候 spi 思想就用上了。

    Java spi 思想的体现

    spi 经典的思想体现,大家平时都在用,比如说 jdbc。

    Java 定义了一套 jdbc 的接口,但是 Java 并没有提供 jdbc 的实现类。

    但是实际上项目跑的时候,要使用 jdbc 接口的哪些实现类呢?一般来说,我们要根据自己使用的数据库,比如 mysql,你就将 mysql-jdbc-connector.jar 引入进来;oracle,你就将 oracle-jdbc-connector.jar 引入进来。

    在系统跑的时候,碰到你使用 jdbc 的接口,他会在底层使用你引入的那个 jar 中提供的实现类。

    dubbo 的 spi 思想

    dubbo 也用了 spi 思想,不过没有用 jdk 的 spi 机制,是自己实现的一套 spi 机制。

    Protocol protocol = ExtensionLoader.getExtensionLoader(Protocol.class).getAdaptiveExtension();
    

    Protocol 接口,在系统运行的时候,,dubbo 会判断一下应该选用这个 Protocol 接口的哪个实现类来实例化对象来使用。

    它会去找一个你配置的 Protocol,将你配置的 Protocol 实现类,加载到 jvm 中来,然后实例化对象,就用你的那个 Protocol 实现类就可以了。

    上面那行代码就是 dubbo 里大量使用的,就是对很多组件,都是保留一个接口和多个实现,然后在系统运行的时候动态根据配置去找到对应的实现类。如果你没配置,那就走默认的实现好了,没问题。

    @SPI("dubbo")  
    public interface Protocol {  
          
        int getDefaultPort();  
      
        @Adaptive  
        <T> Exporter<T> export(Invoker<T> invoker) throws RpcException;  
      
        @Adaptive  
        <T> Invoker<T> refer(Class<T> type, URL url) throws RpcException;  
    
        void destroy();  
      
    }  
    

    在 dubbo 自己的 jar 里,在/META_INF/dubbo/internal/com.alibaba.dubbo.rpc.Protocol文件中:

    dubbo=com.alibaba.dubbo.rpc.protocol.dubbo.DubboProtocol
    http=com.alibaba.dubbo.rpc.protocol.http.HttpProtocol
    hessian=com.alibaba.dubbo.rpc.protocol.hessian.HessianProtocol
    

    所以说,这就看到了 dubbo 的 spi 机制默认是怎么玩儿的了,其实就是 Protocol 接口,@SPI("dubbo") 说的是,通过 SPI 机制来提供实现类,实现类是通过 dubbo 作为默认 key 去配置文件里找到的,配置文件名称与接口全限定名一样的,通过 dubbo 作为 key 可以找到默认的实现类就是 com.alibaba.dubbo.rpc.protocol.dubbo.DubboProtocol

    如果想要动态替换掉默认的实现类,需要使用 @Adaptive 接口,Protocol 接口中,有两个方法加了 @Adaptive 注解,就是说那俩接口会被代理实现。

    啥意思呢?

    比如这个 Protocol 接口搞了俩 @Adaptive 注解标注了方法,在运行的时候会针对 Protocol 生成代理类,这个代理类的那俩方法里面会有代理代码,代理代码会在运行的时候动态根据 url 中的 protocol 来获取那个 key,默认是 dubbo,你也可以自己指定,你如果指定了别的 key,那么就会获取别的实现类的实例了。

    如何自己扩展 dubbo 中的组件

    下面来说说怎么来自己扩展 dubbo 中的组件。

    自己写个工程,要是那种可以打成 jar 包的,里面的 src/main/resources 目录下,搞一个 META-INF/services,里面放个文件叫:com.alibaba.dubbo.rpc.Protocol,文件里搞一个my=com.bingo.MyProtocol。自己把 jar 弄到 nexus 私服里去。

    然后自己搞一个 dubbo provider 工程,在这个工程里面依赖你自己搞的那个 jar,然后在 spring 配置文件里给个配置:

    <dubbo:protocol name=”my” port=”20000” />
    

    provider 启动的时候,就会加载到我们 jar 包里的my=com.bingo.MyProtocol 这行配置里,接着会根据你的配置使用你定义好的 MyProtocol 了,这个就是简单说明一下,你通过上述方式,可以替换掉大量的 dubbo 内部的组件,就是扔个你自己的 jar 包,然后配置一下即可。

    在这里插入图片描述

    dubbo 里面提供了大量的类似上面的扩展点,就是说,你如果要扩展一个东西,只要自己写个 jar,让你的 consumer 或者是 provider 工程,依赖你的那个 jar,在你的 jar 里指定目录下配置好接口名称对应的文件,里面通过 key=实现类

    然后对于对应的组件,类似 <dubbo:protocol> 用你的那个 key 对应的实现类来实现某个接口,你可以自己去扩展 dubbo 的各种功能,提供你自己的实现。

    展开全文
  • &#13; 期末了,通过写博客的方式复习一下...这个问题也困扰了我很久,做题的时候就不知道用什么算法能用分治法的基本特征:1.问题缩小到一定规模容易解决2.分解成的子问题是相同种类的子问题,即该问题具有最...

    期末了,通过写博客的方式复习一下算法,把自己知道的全部写出来

    分治:分而治之,把一个复杂的问题分解成很多规模较小的子问题,然后解决这些子问题,把解决的子问题合并起来,大问题就解决了

    但是我们应该在什么时候用分治呢?这个问题也困扰了我很久,做题的时候就不知道用什么算法

    能用分治法的基本特征:

    1.问题缩小到一定规模容易解决

    2.分解成的子问题是相同种类的子问题,即该问题具有最优子结构性质

    3.分解而成的小问题在解决之后要可以合并

    4.子问题是相互独立的,即子问题之间没有公共的子问题

    第一条大多数问题都可以满足

    第二条的大多数问题也可以满足,反应的是递归的思想

    第三条:这个是能分治的关键,解决子问题之后如果不能合并从而解决大问题的话,那凉凉,如果满足一,二,不满足三,即具有最优子结构的话,可以考虑贪心或者dp

    第四条:如果不满足第四条的话,也可以用分治,但是在分治的过程中,有大量的重复子问题被多次的计算,拖慢了算法效率,这样的问题可以考虑dp(大量重复子问题)

    了解了什么问题可以采用分治,那么分治到达怎么用?步骤是什么呢

    三个步骤:

    1.分解成很多子问题

    2.解决这些子问题

    3.将解决的子问题合并从而解决整个大问题

    化成一颗问题树的话,最底下的就是很多小问题,最上面的就是要解决的大问题,自底向上的方式求解问题

    说的再多不如看经典的样例,更好的体会分治的思想

    样例1:二分查找

    条件:数组有序,假设是升序数组

    虽然二分很容易,但是我还是要具体从算法思想分治的方向分析一下

    现在我们要在一个有序的升序数组里面查找一个数x有没有

    暴力的做法就是拿跟数组里面每个数比较一下,有的话就返回下标,这个是大问题

    仔细想一下,就知道这个大问题是由很多小问题组成的,小问题:在数组的一部分里面找x

    那么我们可以把数组分成很多部分,在很多部分里面找x,如果在这些部分里面没有找到x,那么把这些子问题合并起来,就是大数组里面没有x,否则就是有x

    这个真的很好的反应了分治的思想,先分解成很多小问题,解决这些小问题,把解决的小问题合并起来,大问题就解决了,二分具体的做法我就不多说了,都知道,贴个代码

    #include<string.h>
    #include<stdio.h>
    int k;
    int binarysearch(int a[],int x,int low,int high)//a表示需要二分的有序数组(升序),x表示需要查找的数字,low,high表示高低位
    {
        if(low>high)
        {
            return -1;//没有找到
        }
        int mid=(low+high)/2;
        if(x==a[mid])//找到x
        {
            k=mid;
            return x;
        }
        else if(x>a[mid]) //x在后半部分
        {
            binarysearch(a,x,mid+1,high);//在后半部分继续二分查找
        }
        else//x在前半部分
        {
            binarysearch(a,x,low,mid-1);
        }
    }
    int main()
    {
        int a[10]={1,2,3,4,5,6,7,8,9,10};
        printf("请输入需要查找的正数字:\n");
        int x;
        scanf("%d",&x);
        int r=binarysearch(a,x,0,9);
        if(r==-1)
        {
            printf("没有查到\n");
        }
        else
        {
            printf("查到了,在数列的第%d个位置上\n",k+1);
        }
        return 0;
    }

    经典样例二:全排列问题

    有1,2,3,4个数,问你有多少种排列方法,输出来

    仔细想想,采用分治的话,我们就要把大问题分解成很多的子问题,大问题是所有的排列方法

    那么我们分解得到的小问题就是以1开头的排列,以2开头的排列,以3开头的排列,以4开头的排列

    现在这些问题有能继续分解,比如以1开头的排列中,只确定了1的位置,没有确定2,3,4的位置,把2

    3,4三个又看成大问题继续分解,2做第二个,3做第二个,或者4做第二个

    一直分解下去,直到分解成的子问题只有一个数字的时候,不再分解

    因为1个数字肯定只有一种排列方式啊,现在我们分解成了很多的小问题,解决一个小问题就合并,合并成

    一个大点的问题,合并之后这个大点的问题也解决了,再将这些大点的问题合并成一个更大的问题,那么这

    个更大点的问题也解决了,直到最大的问题解决为止

    这个就是用分治的思想解决全排列问题,我主要想分析的是分治的思想者全排列问题上是怎么用的,不想分析具体全排列的做法,因为我觉得思想比方法更重要,在解题的时候深有体会,因为又的时候没有题是你做过的原题,全排列问题的具体做法参考我的这篇博客:https://www.cnblogs.com/yinbiao/p/8684313.html,也贴一下代码

    #include<string.h>
    #include<stdio.h>
    int k=0;
    char a[100];
    long long count=0;//全排列个数的计数
    void s(char a[],int i,int k)//将第i个字符和第k个字符交换
    {
        char t=a[i];
        a[i]=a[k];
        a[k]=t;
    }
    void f(char a[],int k,int n)
    {
        if(k==n-1)//深度控制,此时框里面只有一个字符了,所以只有一种情况,所以输出
        {
           puts(a);
           count++;
        }
        int i;
        for(i=k;i<n;i++)
        {
            s(a,i,k);
            f(a,k+1,n);
            s(a,i,k);//复原,就将交换后的序列除去第一个元素放入到下一次递归中去了,递归完成了再进行下一次循环。这是某一次循环程序所做的工作,这里有一个问题,那就是在进入到下一次循环时,序列是被改变了。可是,如果我们要假定第一位的所有可能性的话,那么,就必须是在建立在这些序列的初始状态一致的情况下,所以每次交换后,要还原,确保初始状态一致。
        }
    }
    int main()
    {
        gets(a);
        int l=strlen(a);//字符串长度
        f(a,k,l);
        printf("全排列个数:%lld\n",count);
        return 0;
    }


    经典样例三:整数划分问题

    给你一个数,问你所有的划分方式,比如4,4=1+3,4=1+1+2,4=2+2,4=1+1+1+1

    我们来分析一下,我们想用分治的话,就要找子问题,假设n是要划分的数,m说最大的加数,n=4,m=3

    分解成两类的子问题,一个是:一个是有m的情况,一个是没有m的情况,然后将有m的情况继续划分,分

    解成有m-1和没有m-1的情况,一直划分下去,直到m=1,比如n=4,m=3,划分成的子问题:有3,无

    3,有2,无2,有1,无1(没有意义,除非0+4=4),将这些子问题合并起来大问题就解决了,比如有

    3:1+3,没有3分成有2,和无2,有2:1+1+2,2+2,无2分成有1:1+1+1+1,一共四种解决方案

    我们来理一下思路:划分成子问题,解决这些子问题,合并

    但是注意:这个问题里面的子问题有很多是重复的,大量重复子问题,比如n=5,m=4,1+4=5,1+1+

    3=5,2+3=5,求3有几种划分方法的时候求了2次,如果n很大的话,那么就会有大量的重复子问题,这个时候可以采用dp(自己有点不理解重复子问题重复在哪里,觉得哪里有点不对劲)

    分析了一下题中分治的思想,具体做法参考我的这篇博客:https://www.cnblogs.com/yinbiao/p/8672198.html,也贴个代码

    /*
    整数划分问题
    :将一个整数划分为若干个数相加
    例子:
    整数4 最大加数 4
    4=4
    1+3=4
    1+1+2=4
    2+2=4
    1+1+1+1=4
    一共五种划分方案
    注意:1+3=4,3+1=4被认为是同一种划分方案
    */
    
    #include<stdio.h>
    int q(int n,int m)//n表示需要划分的数字,m表示最大的家数不超过m
    {
        if(m==1||n==1)//只要存在一个为1,那么划分的方法数肯定只有一种,那就是n个1相加
        {
            return 1;
        }else if(n==m&&n>1)//二者相等且大于1的时候,问题等价于:q(n,n-1)+1;意味着将最大加数减一之后n的划分数,然后加一,最后面那个一代表的是:0+n,这个划分的方案
        {
            return q(n,n-1)+1;
        }else if(n<m)//如果m>n,那么令m=n就ok,因为最大加数在逻辑上不可能超过n
        {
            return q(n,n);
        }else if(n>m)
        {
            return q(n,m-1)+q(n-m,m);//分为两种:划分方案没有m的情况+划分方案有m的情况
        }
        return 0;
    }
    int main()
    {
        printf("请输入需要划分的数字和最大家数:\n");
        int n,m;
        scanf("%d %d",&n,&m);
        int r=q(n,m);
        printf("%d\n",r);
        return 0;
    }


    经典样例4:归并排序

    把一个无序的数组,变成一个有序的数组,这个是大问题,根据分治的思想,要分解成很多的小问题,比如

    无序数组8个数,要使得数组有序,即使得这8个数有序,分解成两个子问题:使得前面4个数有序,使得后

    面的四个数有序,然后继续分解,在前面的4个数字中,又把它看成一个大问题,继续分解成两个小问题:

    使得前面两个数有序,使得后面两个数有序,直到小问题数组中只有一个数为止,因为一个数的数组肯定是

    有序的,小问题解决之后,还需要合并成一个大一点的问题,这样这个大一点的问题就也解决了,然后将两

    个大一点的问题继续合并成一个更大一点的问题,这样这个更大一点的问题也解决了,直到最后,最大的问

    题也解决了,这个就是分治思想在归并排序中的应用

    也贴个代码,附带详细的解析

    /*
    归并排序
    思想:
    1.分而治之,将一个无序的数列一直一分为二,直到分到序列中只有一个数的时候,这个序列肯定是有序的,因为只有一个数,然后将两个只含有一个数字的序列合并为含有两个数字的有序序列,这样一直进行下去,最后就变成了一个大的有序数列
    2.递归的结束条件是分到最小的序列只有一个数字的时候
    时间复杂度分析:
    最坏情况:T(n)=O(n*lg n)
    平均情况:T(n)=O(n*lg n)
    稳定性:稳定(两个数相等的情况,不用移动位置
    辅助空间:O(n)
    特点总结:
    高效
    耗内存(需要一个同目标数组SR相同大小的数组来运行算法)
    */
    #include<stdio.h>
    #define max 1024
    int SR[max],TR[max];
    int merge(int SR[],int TR[],int s,int m,int t)//SR代表两个有序序列构成的序列,s表示起始位置,m表示两个序列的分解位置,但是SR[m]仍是属于前面一个序列,t表示结束位置
    {//TR是一个空数组,用来存放排序好之后的数字
        int i=s,j=m+1,k=s;
        while(i<=m&&j<=t)
        {
            if(SR[i]<SR[j])
            {
                TR[k++]=SR[i++];
            }else
            {
                TR[k++]=SR[j++];
            }
        }
        while(i<=m)//当前面一个序列有剩余的时候,直接把剩余数字放在TR的后面
        {
            TR[k++]=SR[i++];
        }
        while(j<=t)//当后面一个序列有剩余的时候,直接把剩余数字放在TR的后面
        {
            TR[k++]=SR[j++];
        }
        return 0;
    }//该函数要求SR是由两个有序序列构成
    void copy(int SR[],int TR[],int s,int t)//把TR赋给SR
    {
        int i;
        for(i=s;i<=t;i++)
        {
            SR[i]=TR[i];
        }
    }
    int mergesort(int SR[],int s,int t)
    {
        if(s<t)//表示从s到t有多个数字
        {
            int m=(s+t)/2;//将序列一分为二
            mergesort(SR,s,m);//前一半序列继续进行归并排序
            mergesort(SR,m+1,t);//后一半序列同时进行归并排序,
            //以上递归调用的结束条件是s!<t,也就是进行分到只有一个数字进行归并排序的时候,一个序列只有一个数字,那么这个序列肯定是有序的
            //以上都是属于“分”的阶段,目的是获得两个有序的数列
            merge(SR,TR,s,m,t);//对这两个有序的数列,进行排序,变成一个同样大小但是有序的数列
            copy(SR,TR,s,t);//将在TR中排序好的数列给SR,方便SR递归调用归并排序,因为每次两个归并排序的结果都是保存在TR中的,现在要进行下一步就必须在TR数列的基础上面=进行,所以我们把TR给SR
        }else//表示从s到t只有一个数字(s==t),或者没有数字(s>t)
        {
            ;//空,也可省略,加一个else只是为了更好的理解程序
        }
        return 0;
    }
    int main()
    {
        int n;
        printf("请输入排序数字的个数:\n");
        scanf("%d",&n);
        int i;
        for(i=0;i<n;i++)
        {
            scanf("%d",&SR[i]);
        }
        mergesort(SR,0,n-1);//升序排列
        for(i=0;i<n;i++)
        {
            printf("%d ",SR[i]);
        }
        printf("\n");
        return 0;
    }


    经典样例五:棋盘覆盖问题

    不知道棋盘覆盖问题的请自行百度

    在棋盘的某个位置给了你一个不可覆盖点,现在大问题是问我们怎么用L形状块覆盖整个棋盘,现在我们要把大问题分解成很多的子问题:把整块大棋盘分成同样大小的四个棋盘,直到分解成的棋盘大小为1,就是只有一个格子的时候,不再分解,所以最小的子问题就是四个格子的棋盘,如果这个四个格子的棋盘有不可覆盖点的话,那么就进行棋盘覆盖,如果没有的话就进行覆盖点的构造然后在覆盖(先不讲怎么判断,怎么构造,只讲思想,具体做法我有专门的博客),所以这样我们就解决了这个四个格子的棋盘,把所有的这样的小问题解决的,也就是把解决好的小棋盘合并起来不就构成了我们需要的大棋盘吗?

    理清一下思路:

    分解棋盘(分解成四个小棋盘,一直分解下去,直到棋盘大小为1)

    解决问题(是直接覆盖还是先构造再覆盖)

    合并已经解决的问题(将已经解决的所有小问题合并起来就构成了我们需要覆盖的大棋盘,且此时大棋盘也

    已经覆盖好了)

    棋盘问题具体做法请参考我的这篇博客:https://www.cnblogs.com/yinbiao/p/8666209.html

    也贴一下代码吧

    #include<stdio.h>
    #define max 1024
    int cb[max][max];//最大棋盘
    int id=0;//覆盖标志位
    int chessboard(int tr,int tc,int dr,int dc,int size)//tr,tc代表棋盘左上角的位置,dr ,dc代表棋盘不可覆盖点的位置,size是棋盘大小
    {
        if(size==1)//如果递归到某个时候,棋盘大小为1,则结束递归
        {
            return 0;
        }
        int s=size/2;//使得新得到的棋盘为原来棋盘大小的四分之一
        int t=id++;
        if(dr<tr+s&&dc<tc+s)//如果不可覆盖点在左上角,就对这个棋盘左上角的四分之一重新进行棋盘覆盖
        {
            chessboard(tr,tc,dr,dc,s);
        }else//因为不可覆盖点不在左上角,所以我们要在左上角构造一个不可覆盖点
        {
            cb[tr+s-1][tc+s-1]=t;//构造完毕
            chessboard(tr,tc,tr+s-1,tc+s-1,s);//在我们构造完不可覆盖点之后,棋盘的左上角的四分之一又有了不可覆盖点,所以就对左上角棋盘的四分之一进行棋盘覆盖
        }
    
        if(dr<tr+s&&dc>=tc+s)//如果不可覆盖点在右上角,就对这个棋盘右上角的四分之一重新进行棋盘覆盖
        {
            chessboard(tr,tc+s,dr,dc,s);
        }else//因为不可覆盖点不在右上角,所以我们要在右上角构造一个不可覆盖点
        {
            cb[tr+s-1][tc+s]=t;
            chessboard(tr,tc+s,tr+s-1,tc+s,s);//在我们构造完不可覆盖点之后,棋盘的右上角的四分之一又有了不可覆盖点,所以就对右上角棋盘的四分之一进行棋盘覆盖
        }
    
    
         if(dr>=tr+s&&dc<tc+s)//如果不可覆盖点在左下角,就对这个棋盘左下角的四分之一重新进行棋盘覆盖
        {
            chessboard(tr+s,tc,dr,dc,s);
        }else//因为不可覆盖点不在左下角,所以我们要在左下角构造一个不可覆盖点
        {
            cb[tr+s][tc+s-1]=t;
            chessboard(tr+s,tc,tr+s,tc+s-1,s);//在我们构造完不可覆盖点之后,棋盘的左下角的四分之一又有了不可覆盖点,所以就对左下角棋盘的四分之一进行棋盘覆盖
        }
    
        if(dr>=tr+s&&dc>=tc+s)//如果不可覆盖点在右下角,就对这个棋盘右下角的四分之一重新进行棋盘覆盖
        {
            chessboard(tr+s,tc+s,dr,dc,s);
        }else//因为不可覆盖点不在右下角,所以我们要在右下角构造一个不可覆盖点
        {
            cb[tr+s][tc+s]=t;
            chessboard(tr+s,tc+s,tr+s,tc+s,s);//在我们构造完不可覆盖点之后,棋盘的右下角的四分之一又有了不可覆盖点,所以就对右下角棋盘的四分之一进行棋盘覆盖
        }
    
        //后面的四个步骤都跟第一个类似
    }
    int main()
    {
        printf("请输入正方形棋盘的大小(行数):\n");
        int n;
        scanf("%d",&n);
        printf("请输入在%d*%d棋盘上不可覆盖点的位置:\n",n,n);
        int i,j,k,l;
        scanf("%d %d",&i,&j);
        printf("不可覆盖点位置输入完毕,不可覆盖点的值为-1\n");
        cb[i][j]=-1;
        chessboard(0,0,i,j,n);
        for(k=0;k<n;k++)
        {
            printf("%2d",cb[k][0]);
            for(l=1;l<n;l++)
            {
                printf(" %2d",cb[k][l]);
            }
            printf("\n");
        }
        return 0;
    }


    经典样例六:快速排序

    快速排序中分治的思想体现在哪里呢?

    首先我们要了解快速排序的思想,选择一个基准元素,比基准元素大的放基准元素后面,比基准元素小的放

    基准元素前面,这个叫做分区,每次分区都使得一个元素有序,进行很多次分区以后,数组就是有序数组

    了,为什么是这样呢?因为每次分区,我们都使得了基准元素有序,以比基准元素小的为例,这些元素都比

    基准元素小,放在基准元素前面,但这些比基准元素小的元素自己是无序的,确定的位置只有基准元素位

    置,有序之后这些元素与基准元素的相对位置是不会变的,变的只有这些元素自己内部的位置,因为进行一

    次分区就可以使得一位元素有序,所以进行很夺次分区以后,数组就是有序的了,

    那么分治的思想到底体现在哪里呢/

    第一步:把大问题分解成很多子问题(每次使得一位元素有序,分区操作可以做到)

    第二步:解决子问题(进行分区操作,每次使得一位元素有序)

    第三步:所有子问题解决了那么最大的问题也解决了

    再简单分析一下:第一次分区是对整个数组进行分区,确定了第一个基准元素的位置,然后对比基准元素大

    的和比基准元素小的进行分区,确定第二个和第三个基准元素的位置,如果序列够好的话(每次分区时,比

    基准元素大的元素和比基准元素小的元素每次都一样多)n*logn时间可解决

    关于快排的具体做法请参考我的这篇博客:https://www.cnblogs.com/yinbiao/p/8805233.html

    也贴个代码吧(随机化快排,基准元素选择是随机的)

    #include<bits/stdc++.h>
    using namespace std;
    #define n 5
    int a[n];
    void swap_t(int a[],int i,int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    int par(int a[],int p,int q)
    {
        int i=p;//p是轴
        int x=a[p];
        for(int j=p+1;j<=q;j++)
        {
            if(a[j]<=x)
            {
                i++;
                swap_t(a,i,j);
            }
        }
        swap_t(a,p,i);
        return i;//轴位置
    }
    int Random(int p,int q)
    {
        return rand()%(q-p+1)+p;
    }
    int Randomizedpar(int a[],int p,int q)
    {
        int i=Random(p,q);
        swap_t(a,p,i);//第一个和第i个交换,相当于有了一个随机基准元素
        return par(a,p,q);
    }
    void RandomizedQuickSort(int a[],int p,int q)
    {
        if(p<q)
        {
            int r=Randomizedpar(a,p,q);
            printf("%d到%d之间的随机数:%d\n",p,q,r);
            RandomizedQuickSort(a,p,r-1);
            RandomizedQuickSort(a,r+1,q);
        }
    }
    int main()
    {
        int i;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
    
        }
        RandomizedQuickSort(a,0,n-1);
        for(i=0;i<n;i++)
        {
            printf("%d\n",a[i]);
        }
        return 0;
    }


    经典样例七:求第k小/大元素

    这是快排分区思想的应用,也要进行分区操作,和快排不同的是,快排分区之后还有继续处理基准元素

    两边的数据,而求k小/大不用,只用处理一边即可

    假如现在这里5个元素,分为1,2,3,4,5号位置

    第一种情况:假设求第3小元素,假设第一次分区的基准元素完成分区后在第2号位置,那么我们知道3>2

    所以只要对基准元素后面的元素继续分区就可以(注意k的值要变了,k代表的是在升序有序数组的1相对位

    置,现在对第一次分区的基准元素后面的元素进行分区操作,区间大小是变小了的,所以k值是要跟着变的)

    讲了这么多,所以分治的思想到底体现在哪里呢?

    跟快排一样,有分区操作,所以分治的思想在这里的体现和在快排的体现都是一样的,不同的是这里只要对

    基准元素前面元素或者后面元素进行继续分区(如果需要继续分区的话),而快排是基准元素两边都要继续

    分区的

    贴个代码(采用的是随机分区)

    #include<bits/stdc++.h>
    using namespace std;
    void swap_t(int a[],int i,int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    int par(int a[],int p,int q)//p是轴,轴前面是比a[p]小的,后面是比a[p]大的
    {
        int i=p,x=a[p];
        for(int j=p+1;j<=q;j++)
        {
            if(a[j]>=x)
            {
                i++;
                swap_t(a,i,j);
            }
        }
        swap_t(a,p,i);
        return i;//返回轴位置
    }
    int Random(int p,int q)//返回p,q之间的随机数
    {
        return rand()%(q-p+1)+p;
    }
    int Randomizedpar(int a[],int p,int q)
    {
        int i=Random(p,q);
        swap_t(a,p,i);//第一个和第i个交换,相当于有了一个随机基准元素
        return par(a,p,q);
    }
    int RandomizedSelect(int a[],int p,int r,int k)
    {
        if(p==r)
            return a[p];
        int i=Randomizedpar(a,p,r);
        int j=i-p+1;
        printf("i=%d j=%d\n",i,j);
        if(k<=j)
            return RandomizedSelect(a,p,i,k);
        else
            return RandomizedSelect(a,i+1,r,k-j);
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        int a[n];
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int x=RandomizedSelect(a,0,n-1,2);
        printf("%d\n",x);
    }


    样例大概就是这些



    还有一个很重要的知识点差点忘了复习,分治的主定理

    分治的一般形式:

    T(N)=aT(N/b)+f(n)

    1.a==1 T(n)=O(logn)

    2.a!=1  T(n)=O(n的logb a)次方

    3. a==b T(n)=O(n*log b a)

    4 a<b T(n)=O(n)

    5. a>b  T(n)=O(n的log b a次方)

    用于估算分治算法的时间复杂的(数学log 的指数和底数不好表示。。。)


    735119-20170111112835275-168981902

    735119-20170111112841431-2047172832
    展开全文
  • DevOps 到底什么到底什么

    千次阅读 2019-06-22 16:40:20
    DevOps 到底什么 2018 年,我们走访了近百个分布在各行各业中的 IT 团队,意外的发现,大多数的 IT 团队寻求改革并非来源于部门内部的自我革新,而是来源于业务部门的服务压力。正如同当年企业寻找 ERP,今天的...
  • web 前端入坑第一篇:web前端到底什么?有前途吗

    万次阅读 多人点赞 2016-08-01 14:49:20
    web前端到底什么? 某货: “前几年前端开发人员鱼目混杂,技术参差不齐,相对学习起来不规范,导致> 前端开发人员聚集,所以现在前端工种和工资还是没得到普遍重视,但近2年来,> > HTML5、JS 的流行...
  • 深入了解Windows句柄到底什么

    万次阅读 多人点赞 2013-12-30 11:02:23
    总是有新入门的Windows程序员问我Windows的句柄到底什么,我说你把它看做一种类似指针的标识就行了,但是显然这一答案不能让他们满意,然后我说去问问度娘吧,他们说不行网上的说法太多还难以理解。今天比较闲,我...
  • 面向对象思想总结

    万次阅读 多人点赞 2018-07-23 17:31:53
    面向对象和面向过程的思想有着本质上的区别,作为面向对象的思维来说,当你拿到一个问题时,你分析这个问题不再是第一步先做什么,第二步再做什么,这是面向过程的思维,你应该分析这个问题里面有哪些类和对象,这是...
  • 技术不如思想

    千次阅读 2012-10-29 09:14:39
    机房收费系统终于艰难的完成了,但是今天去五楼一测试发现出来了好多的问题.就是这些问题让人深深的体会到,技术不如思想贵.   之所以这么是因为出的...可是为什么有人想到了你却没想到,说到底还是思想或者思维的问题
  • 什么是spring框架,spring框架究竟有什么用呢?我们可以用spring框架来做些什么呢?让我们来具体了解一下,以及经常所说的IOC和AOP是一种怎样的思想到底是怎么实现这些思想的!
  • 编程思想之消息机制

    万次阅读 多人点赞 2015-05-07 23:01:51
    有很多人可能一听到消息机制就觉得其是一种非常高深和神秘的东西(我刚开始也是这种感觉),但你又无法避免地经常到接触它。...那到底什么是消息?消息机制又是怎样的工作原理?让我们一起刨根究底,探索它的来龙去脉吧!
  • SpringCloud到底什么

    万次阅读 多人点赞 2019-05-07 11:56:50
    什么是微服务 在介绍Spring Cloud之前,读者有必要了解一下什么是微服务。而要了解什么是微服务又要了解什么时候SOA。关于什么是SOA可以看笔者的这篇文章:...
  • 带着问题学,协程到底什么?

    万次阅读 多人点赞 2021-06-15 21:10:01
    但是协程到底什么呢? 协程其实是个古老的概念,已经非常成熟了,但大家对它的概念一直存在各种疑问,众说纷纷 有人说协程是轻量级的线程,也有人说kotlin协程其实本质是一套线程切换方案 显然这对初学者不太友好...
  • C++编程思想1

    千次阅读 2011-12-22 06:27:06
    学了好久的 C++了 发现自己对于C/C++还是没有深入的了解 于是 咬咬牙啃起了 C++编程思想 希望能有所感悟 。。 我以前是直接学C++的对于C不是很了解,然而又是在VC下 学习 所以 没有好好的 去学习 标准C++,直到我 看...
  • 到底什么是类呢?在讨论这个问题之前,我们先探讨一下类的由来。“类”在英语对应的单词是“Class”,如果大家翻一翻英语词典就可以查到“Class”的原意是指“种类、把...分类(或分等级)”。Class的概念最早应该是...
  • 函数式编程思想概论

    千次阅读 2019-06-26 10:57:16
    函数式编程思想概论前言函数λ 演算λ项绑定变量和自由变量约简α 变换β 约简η 变换纯函数、副作用和引用透明性函数式编程与并发编程总结 原文地址 前言 在讨论函数式编程(Functional Programming)的具体内容...
  • 思想洗澡

    千次阅读 2018-02-13 14:11:35
    笛卡尔是这个世界上最大为的哲学家,思想家,他提出的两个思想实验: 普遍怀疑论 不可知论 本篇文章也主要围绕这两个点来讲解。 普遍怀疑论 先来看普遍怀疑,笛卡尔认为,每个人一生中都应该“彻底地对自己的...
  • 编程思想与编程技法是相互影响的两件事,然而也是不可拆分的一回事儿!
  • 转化与划归思想

    千次阅读 2018-11-30 22:06:32
    化归思想 化归思想,将一个问题由难化易,由繁化简,由复杂化简单的过程称为化归,它是转化和归结的简称。 普遍联系和永恒发展是转化划归思想的哲学基础。   基本内容 化归不仅是一种重要的解题思想,也是一种...
  • opp的思想

    千次阅读 2012-05-25 07:36:06
    一、oop的基本思想 OOP的许多原始思想都来之于Simula语言,并在Smalltalk语言的完善和标准化过程中得到更多的扩展和对以前的思想的重新注解。可以说OO思想和OOPL几乎是同步发展相互促进的。与函数式程序设计...
  • PMF到底什么

    千次阅读 2019-12-08 12:09:34
    关注的数据指标在不同行业、不同业务模式的产品中对应的数值应该是不同的,核心思想在于需要找到一些关键的数据指标,然后通过数据指标来判断产品是否达到了PMF的标准。 用户级产品标准 · 每周使用天数超过3天 · ...
  • 到底什么是数据中台?

    万次阅读 多人点赞 2019-07-22 21:00:00
    最近可能大家听到“数据中台”这个词越来越频繁了,有时候我跟一些朋友聊起来,也是都在说这个,但是一直不知道这到底是个什么。最近就看到这篇文章,觉得说的还挺好的,分享给大家看...
  • 决策树到底什么

    万次阅读 2018-08-04 15:24:21
    本文思想及知识来源于对李航老师的统计学习方法的拜读,加上一些自己的理解整理,感谢李航老师伟大的著作:《统计学习方法》!   决策树是什么?(decision tree) 是一种分类与回归方法,主要用于分类,决策树...
  • 什么是切块思想,切块思想简单的说就是产品形体通过面或是体块切割出来的,这是建模当中最简单的方法,一个产品的外形可以通过不同形体的切割而得来。很多人在学完犀牛后一拿到产品走上来就用曲线曲面工具,画线扫描...
  • 软件分层的思想

    万次阅读 2015-05-21 10:59:52
    写程序的时候一直考虑这些是否和,这个方法是否应该封装,是否应该抽取,或者应该定义成接口还是抽象类,到底什么设计模式?始终没有一个好的解决办法,看到设计模式,就寄托着把程序里遇到的问题通过设计模式去...
  • 什么是 AOP? AOP 是一种思想,是 Aspect-oriented-programing(面向切面编程)的意思。AOP 可以将业务逻辑与系统级服务隔离,使业务逻辑跟各个系统级服务的耦合度降低,提高程序的通用性和开发效率。 ps:这里先...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 180,603
精华内容 72,241
关键字:

思想到底是什么