精华内容
下载资源
问答
  • 经典算法SRC分类器

    千次阅读 2016-01-20 11:30:34
    自从05、06年开始,稀疏表示开始成为研究的热点。自从陶哲轩和他的小伙伴们...2008年,有Wright在PAMI上发表了一篇Sparse Representation based Classifier(SRC)的文章《Robust Face Recognition via Sparse Represe

    自从05、06年开始,稀疏表示开始成为研究的热点。自从陶哲轩和他的小伙伴们解决了稀疏表示的理论问题,压缩感知或Sparse Representation成为学术界的研究热点。2008年,有Wright在PAMI上发表了一篇Sparse Representation based Classifier(SRC)的文章《Robust Face Recognition via Sparse Representation》。该文章从训练样本中抽取一定的样本构建词典,然后使用词典来表示测试样本,选取对应最小残差值的类作为预测的结果。下面简单介绍该算法的过程。

        若Xi表示第i类的训练样本,大小为d*li,d为特征维数,li为样本数量。将所有类别(K类)的训练样本组合成一个矩阵为D=[X1 ... Xi ... XK],大小为d*l。对于任意一个测试样本,可以表示成如下的线性方式:

                                                           y = Da                    (1)

    根据线性代数的知识,已知Dy,系数a可以方便的求解出来。但是,一般情况下,远大于d。因此,公式(1)没有唯一的解。为了得到唯一的解,需要添加一个约束条件,即系数 尽可能的稀疏。因此公式(1)演变为如下的最优问题

                               y = Da   s.t. min ||a|| 1            (2)

    上述的问题等同于如下问题:

                                                   min ||a|| 1  s.t.y = Da        (3)

    该问题属于一种线性约束的最优化问题。已经有很多人研究了如何求解该问题,常用的方法包括梯度法,牛顿法等,这里不一一介绍了。

        求解得到合适的最优系数a*后,利用残差来确定相应的类别,方法如下:

                                                 y* = arg mini ei(y), ei(y) = ||y - Xiai*||2          (4)

    通过公式(4)求解对应的类别。下面给出一个测试样本的求解结果。


    图中左边图片为一个测试样本;中间为根据公式(3)求解出的稀疏系数a*;最右边是通过公式(4)计算的残差,可以看出第一个类别的残差最小,因此对应的类别为第1类。

    展开全文
  • 算法-递归算法

    千次阅读 2016-12-06 01:24:42
    递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。 本文主要从以下方面进行介绍递归算法: 1. 递归算法的概念 2. 递归算法的特点 3. 递归算法的应用 4. 递归...

    递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
    本文主要从以下方面进行介绍递归算法:
    1. 递归算法的概念
    2. 递归算法的特点
    3. 递归算法的应用
    4. 递归算法的典型实例

    1. 递归算法的概念

    递归过程一般通过函数或子过程来实现。递归方法:在函数或子过程的内部,直接或者间接地调用自己的算法。

    2. 递归算法的特点

    2.1 递归的特点

    (1) 递归就是在过程或函数里调用自身,分别称为直接递归和间接递归;
    (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口;
    (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低;
    (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。鉴于(3)(4)特点,所以一般不提倡用递归算法设计程序。但是有些问题必须用递归解决。

    2.2 递归的要求

    递归算法所体现的“重复”一般有三个要求:
    (1)每次调用在规模上都有所缩小(通常是减半);
    (2)相邻两次重复之间有紧密的联系,前一次要为后一次做准备(通常前一次的输出就作为后一次的输入);
    (3)在问题的规模极小时必须用直接给出解答而不再进行递归调用,因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件),无条件递归调用将会成为死循环而不能正常结束。

    3. 递归算法的实现

    3.1 递归的设计思路

    (1)确定递归公式
    (2)确定边界(终了)条件

    3.2 递归的设计模式

    procedure aaa(k:integer);
    begin
    if k=1 then (边界条件及必要操作)
    else begin
    aaa(k-1);
    (重复的操作);
    end;
    end;

    4. 递归算法的典型实例

    4.1 上楼问题/斐波那契数列

    问题描述: 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.
    问题分析:设n阶台阶的走法数为f(n)
    显然有
    f(1) = 1;
    f(2) = 2;
    f(n)={f(n-1)+f(n-2)} n>2
    递归结束条件: n = 1;
    算法实现:

    public class Step{
    
        public static void main(String args[]){
            System.out.println(step(3));
            System.out.println(step(4));
            System.out.println(step(15));
        }
    
        private static int step(int n){
            if(n == 1){  //定义出口
                return 1; 
            }else if(n == 2){ //定义出口
                return 2;
            }else{ //递归
                return step(n-1) + step(n-2); //递归公式
            }
        }
    }

    结果:
    递归>java Step
    3
    5
    987

    4.2 汉诺塔问题

    问题描述:汉诺塔问题如上图所示,将64个盘子从一个柱子移动到另一个柱子,可以借助一个柱子。每次只能移动一个盘,且不能出现小盘放在大盘上面。
    这里写图片描述
    问题分析:
    1个盘:从原柱(src)移动到目的柱(dist);
    n个盘:
    (1)将(n-1)个盘子从src通过dist移动到中间柱(temp);
    (2)将第n个盘子从src移动到dist;
    (3)将(n-1)个盘子从temp通过src移动到dist;
    算法实现

    public class Hanio{
        public static StringBuffer sb = new StringBuffer();
    
        public static void main(String args[]){
            System.out.println(hanio(1,"src","temp","dist"));
            sb.delete(0, sb.length() - 1);
            System.out.println(hanio(2,"src","temp","dist"));
            sb.delete(0, sb.length() - 1);
            System.out.println(hanio(3,"src","temp","dist"));
            sb.delete(0, sb.length() - 1);
            System.out.println(hanio(4,"src","temp","dist"));
        }
    
        private static String hanio(int n, String src, String temp, String dist){
            if(n == 1){
                sb.append(move(n,src,dist)); 
            }else {
                hanio(n-1,src,dist,temp);
                //hanio(1,src,temp,dist);
                sb.append(move(n,src,dist));
                hanio(n-1,temp,src,dist);
            }
            return sb.toString();
        }
        private static String move(int n, String src, String dist){
            return "Move No." + n + " pillar from " +  src + " to " + dist + "\n"; 
        }
    }

    运行结果

    Move No.1 pillar from src to dist

    Move No.1 pillar from src to temp
    Move No.2 pillar from src to dist
    Move No.1 pillar from temp to dist

    Move No.1 pillar from src to dist
    Move No.2 pillar from src to temp
    Move No.1 pillar from dist to temp
    Move No.3 pillar from src to dist
    Move No.1 pillar from temp to src
    Move No.2 pillar from temp to dist
    Move No.1 pillar from src to dist

    Move No.1 pillar from src to temp
    Move No.2 pillar from src to dist
    Move No.1 pillar from temp to dist
    Move No.3 pillar from src to temp
    Move No.1 pillar from dist to src
    Move No.2 pillar from dist to temp
    Move No.1 pillar from src to temp
    Move No.4 pillar from src to dist
    Move No.1 pillar from temp to dist
    Move No.2 pillar from temp to src
    Move No.1 pillar from dist to src
    Move No.3 pillar from temp to dist
    Move No.1 pillar from src to temp
    Move No.2 pillar from src to dist
    Move No.1 pillar from temp to dist

    展开全文
  • DINIC算法

    2016-07-28 10:36:15
    DINIC算法和EK算法原理其实是一样的,都是寻找增广路,但是在实现的细节上不同,首先,用bfs对顶点进行层次编号,当汇点不在层次图中的时候算法结束;其次,用dfs寻找增广路,在dfs中,用一个顶点扩展时,其实计算...
    • DINIC原理
      DINIC算法和EK算法原理其实是一样的,都是寻找增广路,但是在实现的细节上不同,首先,用bfs对顶点进行层次编号,当汇点不在层次图中的时候算法结束;其次,用dfs寻找增广路,在dfs中,用一个顶点扩展时,其实计算了多条增广路,这也是这个算法比EK算法快的原因。

    • Code

    #include <stdio.h>
    #include <string.h>
    
    #include <iostream>
    #include <queue>
    
    #define MIN(a,b) ((a)>(b)? (b):(a))
    
    using namespace std;
    
    const int SIZE=200;
    const int INF=0x3f3f3f3f;
    
    int src,des;
    int map[SIZE][SIZE];
    int d[SIZE];
    int n;
    
    void build()
    {
    
    }
    
    bool bfs(int src,int des)
    {
        memset(d,-1,sizeof(d));
        queue<int> que;
        que.push(src);
        d[src]=0;
        while(!que.empty()){
            int now=que.front();
            que.pop();
            for(int i=0;i<=1+n;i++)
                if(d[i]==-1&&map[now][i]>0){
                    d[i]=d[now]+1;
                    que.push(i);
                }
        }
        return d[des]>=0;
    }
    
    int dfs(int t,int sum,int des)
    {
        if(t==des)
            return sum;
        int tmp=sum;
        for(int i=0;i<=n+1&&sum;i++)
            if(d[i]==d[t]+1&&map[t][i]>0){
                int a=dfs(i,MIN(sum,map[t][i]),des);
                map[t][i]-=a;
                map[i][t]+=a;
                sum-=a;
            }
        return tmp-sum;
    }
    
    int DINIC(int src,int des)
    {
        int sum=0;
        while(bfs(src,des))
            sum+=dfs(src,INF,des);
        return sum;
    }
    
    int main()
    {
        build();
        printf("%d\n",DINIC(src,des));
        return 0;
    }
    展开全文
  • EK算法

    2016-07-28 09:39:30
    EK原理EK算法是求网络流最大流的算法。也称为寻找增广路算法,每次寻找一条增广路,求出这条路上最小的容量(木板原理),然后累加起来,直到最后找不到一条增广路为止。注意,在找到最小容量的时候,前向边要减去最小...
    • EK原理

      EK算法是求网络流最大流的算法。也称为寻找增广路算法,每次寻找一条增广路,求出这条路上最小的容量(木板原理),然后累加起来,直到最后找不到一条增广路为止。注意,在找到最小容量的时候,前向边要减去最小容量,而后向边要加上最小容量。这是为了形成能改正之前寻找增广路错误的残余网络,实际上这就是把之前的容量退回去,形成新的可行路径。


    • Code
    #include <stdio.h>
    #include <string.h>
    
    #include <iostream>
    #include <queue>
    
    #define MIN(a,b) ((a)>(b)? (b):(a))
    
    using namespace std;
    
    const int SIZE=200;
    const int INF=0x3f3f3f3f;
    
    int src,des;
    int map[SIZE][SIZE];
    int pre[SIZE];
    int n;
    
    void build()
    {
    
    }
    
    bool bfs(int src,int des)
    {
        memset(pre,-1,sizeof(pre));
        queue<int> que;
        que.push(src);
        pre[src]=0;
        while(!que.empty()){
            int now=que.front();
            que.pop();
            for(int i=0;i<=1+n;i++)
                if(pre[i]==-1&&map[now][i]>0){
                    pre[i]=now;
                    if(i==des)
                        return true;
                    que.push(i);
                }
        }
        return false;
    }
    
    int EK(int src,int des)
    {
        int maxflow=0;
        while(bfs(src,des)){
            int minflow=INF;
            for(int i=des;i!=src;i=pre[i])
                minflow=MIN(minflow,map[pre[i]][i]);
            for(int i=des;i!=src;i=pre[i])
                map[pre[i]][i]-=minflow,
                map[i][pre[i]]+=minflow;
            maxflow+=minflow;
        }
        return maxflow;
    }
    
    int main()
    {
        build();
        printf("%d\n",EK(src,des));
        return 0;
    }
    展开全文
  • KMP算法详解

    2016-02-06 11:38:53
    说道KMP算法,一定要先指出问题所在之处了,问题如下: 已知一个字符串a,b 想找到在字符串a中b首次完整出现的位置。 听到这个问题,首先想到的就是朴素算法,挨个来...def algorithm1(src, target): for i in r
  • 算法】聚类算法

    千次阅读 2018-04-24 16:29:41
    本篇介绍了聚类算法的种类,重点关注K-Means和DBSCAN两类聚类算法,并给出具体实现。 一、简介 1.1 什么是聚类 聚类是数据挖掘中的概念,就是按照某个特定标准(如距离)把一个数据集分割成不同的类...
  • 图像缩放: resize函数是在OpenCV中经常使用的函数,功能是将一副加载到Mat中的图像调整尺寸或者...设原始图像src的高为h,宽为w,图像上像素值为(x,y)。 设目标图像dst的高H,宽为W,图像上的像素值为(X,Y)。 ...
  • 遗传算法原理及算法实例

    万次阅读 多人点赞 2017-11-26 09:42:19
    遗传算法原理解析 遗传算法(GA)是一种元启发式自然选择的过程,属于进化算法(EA)大类。遗传算法通常是利用生物启发算子,如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。 借鉴生物进化理论,遗传...
  • MCMF算法

    千次阅读 2016-08-04 15:34:27
    最小费用最大流算法: ...求最小费用链也就相当于求src−>dessrc->des的最短路径。使用spfa+EKspfa+EK算法。得到MCMFMCMF算法 代码:#define MIN(a,b) ((a)>(b)? (b):(a))using namespace std;const int INF=0x3f3f3f3
  • 单源最短路径给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径,图中可能含有负权值的边。Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中...
  • 【经典算法】Bellman-Ford最短路径算法

    万次阅读 多人点赞 2017-06-12 10:53:14
    给定一个图,和一个源顶点src,找到从src到其它所有所有顶点的最短路径,图中可能含有负权值的边。 Dijksra的算法是一个贪婪算法,时间复杂度是O(VLogV)(使用最小堆)。但是迪杰斯特拉算法在有负权值边的图中不适用,...
  • Checksum算法

    万次阅读 2017-07-10 09:01:40
    checksum算法,IP checksum算法,tcp checksum算法,udp checksum算法
  • 背景提取算法——帧间差分法、背景差分法、ViBe算法、ViBe+算法: 背景提取有很多算法。针对静止摄像机的帧间差分法、高斯背景差分法、ViBe背景提取算法以及它的改进算法ViBe+,还有针对运动摄像机的光流法等。 本文...
  • 算法系列之八:RLE行程长度压缩算法

    万次阅读 多人点赞 2011-12-12 00:33:02
    RLE(Run Length Encoding)行程长度压缩算法(也称游程长度压缩算法),是最早出现、也是最简单的无损数据压缩算法。RLE算法的基本思路是把数据按照线性序列分成两种情况:一种是连续的重复数据块,另一种是连续的...
  • 1. 介绍 最小生成树的应用场景很广,例如电信公司需要将9个村庄进行网络连接,村庄间的距离都不相同,怎么连接才能达到成本最小了?...普利姆与克鲁斯卡尔算法都是贪心算法 2.1 普利姆(Prim)算法 2.1.1 原理 ...
  • RSA数字签名算法

    千次阅读 2016-12-08 21:18:22
    数字签名算法签名具有安全性、抗否认性的特点 ,数字签名——带有密钥(公钥、私钥)的消息摘要算法,用于验证数据完整性、认证数据来源、抗否认,遵循OSI参考模型、私钥签名和公钥验证。常用数字签名算法RSA、DSA、...
  • 单源最短路径问题给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。...前面Bellman-Ford最短路径算法讲了单源最短路径的Bellman-Ford算法(动态规划算法)。这里介绍另外一个更常见的算法Dijkstra算法。Dijks
  • 六之续、由KMP算法谈到BM算法

    万次阅读 热门讨论 2011-06-15 01:28:00
    六之续、由KMP算法谈到BM算法 作者:滨湖,July、yansha。说明:初稿由滨湖提供,July负责KMP部分的勘误,yansha负责BM部分的修改。全文由July统稿修订完成。出处:http://blog.csdn.net/v_JULY_v 。引言 在此...
  • Sample K算法

    千次阅读 2017-05-01 19:50:46
    最近去国内某牛叉互联网公司面试,出了一道算法题,看似简单,但是真正的答案十分巧妙。故此回忆并将原题以及解题思路记录下来,供大家学习: 随机的选取容量为N的数组中的k个元素,要求是不能重复选取,并且不能...
  • 本文总结了六种排序算法,分别是:选择法、冒泡法、直接插入法、希尔算法、快速算法、归并算法。 一、选择法排序 /* 选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序...
  • 回文算法

    千次阅读 2010-11-20 00:26:00
    回文算法概述: 给出一个整型数 n。转成二进制数后 从中找出一串0101010xxxx,如果前后顺寻颠倒 仍然相同,则为一个回文 求某个整数的最大回文的长度。   static int getHuiwenMaxLength...
  • DH算法(密钥交换算法

    千次阅读 2017-12-08 19:52:56
    二 DH密钥交换算法特点 构建本地密钥 双方密钥一致 三 DH相关参数 四 DH算法实现过程 1、初始化发送方的密钥(KeyPairGenerator、KeyPair、PublicKey) 2、初始化接受方的密钥(KeyFactory、X509...
  • RANSAC算法理解

    万次阅读 多人点赞 2018-01-26 22:28:59
    最早应该是十四讲上见过,在第九章的project中src中的visual_odometry.cpp中,最核心的求解3d-2d的变换中: //整个核心就是用这个cv::solvePnPRansac()去求解两帧之间的位姿变化 cv::solvePnPRansac( pts3d, pts...
  • 细化算法

    千次阅读 2016-02-28 10:22:10
    原文连接:... 程序编码参考经典的细化或者骨架算法文章: T. Y. Zhang and C. Y. Suen, “A fast parallel algorithm for thinning digital patterns,” Comm. ACM, vol. 27, no. 3, pp. 2
  • JAVA摘要算法

    千次阅读 2017-12-09 09:10:58
    数据摘要算法是密码学算法中非常重要的一个分支,它通过对所有数据提取指纹信息以实现数据签名、数据完整性校验等功能,由于其不可逆性,有时候会被用做敏感信息的加密。数据摘要算法也被称为哈希(Hash)算法、散列...
  • 图像插值算法(最近临插值算法

    千次阅读 2015-06-24 19:25:46
    对于图像缩放算法来说,最近临插值算法是最简单的。最近临插值算法的原理是在原图像中找到最近临的一个点,然后把这个点的像素值插入到目标图像中,最近临插值算法优点是算法简单,易于实现,但是缺点是由于相邻像素...
  • 单源点最短路径算法:Dijkstra算法

    千次阅读 2018-01-20 09:15:17
    图由节点和边组成,边有方向的图称为有向图,边没有方向的图称为无向图,最短路径算法里可以把无向图视为双向连接的有向图。 边有权重的图称为有权图,边没有权重的图称为无权图,无权图可以视为边的权重均为1的图...
  • A* 算法证明

    千次阅读 2015-12-03 14:25:11
    此文章目标人群为还未... 整个算法在执行过程中,会从src结点开始对图中的结点进行遍历(可能某些并不会被遍历到),算法在遍历到某个结点时,会记录下src到该结点经过的路径,该路径的长度就记为g(N)。在算法初始...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 151,053
精华内容 60,421
关键字:

src算法