精华内容
下载资源
问答
  • 图的遍历

    2021-01-21 15:09:28
    用深度优先搜索(DFS)法遍历图 深度优先搜索:每次都是沿着路径到不能再前进时才退到最近的岔道口。 以一个有向图进行DFS遍历: 从V0 开始进行遍历,黑色...从V1出发访问V3,但是从V3出发不能到达任何未访问顶点,因此退

    用深度优先搜索(DFS)法遍历图

    深度优先搜索:每次都是沿着路径到不能再前进时才退到最近的岔道口。
    以一个有向图进行DFS遍历:
    从V0 开始进行遍历,黑色表示结点未访问,白色表示结点已访问,虚线边表示当前遍历路径
    在这里插入图片描述

    1. 访问V0 ,发现从V0 出发可以到达两个未访问顶点:V1 和V2 ,因此准备访问V1 和V2 这两个顶点。
      在这里插入图片描述
    2. 从V0 出发访问V1 ,发现从V1 出发可以到达两个未访问顶点:V3 和V4 ,因此准备访问V3和V4这两个顶点。
      在这里插入图片描述
    3. 从V1出发访问V3,但是从V3出发不能到达任何未访问顶点,因此退回到当前路径上距离V3最近的仍有未访问分支顶点的岔道口V1
      在这里插入图片描述
    4. 从V1出发访问V4,发现从V4出发可以到达一个未访问顶点:V5,因此准备前往访问V5
      在这里插入图片描述
    5. 从V4出发访问V5,发现从V5出发不能到达任何未访问顶点,因此退回到当前路径上距离V5最近的仍有未访问分支顶点的岔道口V0
      在这里插入图片描述
    6. 从V0出发访问V2,发现从V2出发不能到达任何未访问顶点,因此退回到当前路径上距离V5最近的仍有未访问分支顶点的岔道口。但是此时路径上所有顶点的分支顶点都已被访问,因此DFS算法结束。
      在这里插入图片描述

    DFS的具体实现

    连通分量:在无向图中,如果两个顶点之间可以相互到达(可以是通过一定路径间接到达),那么就称这两个顶点连通。如果图G(V, E)的任意两个顶点都连通,则称图G为连通图;否则,称图G为非连通图,且称其中的极大连通子图为连通分量。

    强连通分量:在有向图中,如果两个顶点可以各自通过一条有向路径到达另一个顶点,就称这两个顶点强连通。如果图G(V, E)的任意两个顶点都强连通,则称图G为强连通图;否则,称图G为非强连通图,且称其中的极大强连通子图为强连通分量。

    例如:无向图,V1V2V3、V4V5V6V7、V8V9形成了三个连通分量;有向图,V1V2V3、V4、V5V6V7V8形成了三个强连通分量。
    在这里插入图片描述
    遍历图的伪代码

    DFS(u) //访问顶点u
    {
    	vis[u] = true; //设置u已被访问
    	for(从u出发能到达的所有顶点v) //枚举从u出发可以到达的所有顶点v
    	{
    		if(vis[v] == false) //如果v未被访问
    		{
    			DFS(v); //递归访问v
    		}
    	}
    }
    
    DFSTrave(G) //遍历图G
    {
    	for(G的所有顶点u) //对G的所有顶点u
    	{
    		if(vis[u] == false) //如果u未被访问
    		{
    			DFS(u); //访问u所在的连通块
    		}
    	}
    }
    

    定义MAXV为最大顶点数、INF为一个很大的数字

    constint MAXV = 1000; //最大顶点数
    constint INF = 100000000; //设INF为一个很大的数
    
    1. 邻接矩阵版
    int n, G[MAXV][MAXV]; //n为顶点数,MAXV为最大顶点数
    bool vis[MAXV] = {false}; //如果顶点i已被访问,则vis[i] == true。初值为false
    void DFS(int u, int depth) //u为当前访问的顶点标号,depth为深度
    {
    	vis[u] = true; //设置u已被访问
    	//如果需要对u进行一些操作,可以在这里进行
    	//下面对所有从u出发能到达的分支顶点进行枚举
    	for(int v = 0; v < n; v++) //对每个顶点v
    	{
    		if(vis[v] == false && G[u][v] != INF) //如果v未被访问,且u可到达v
    		{
    			DFS(v, depth + 1); //访问v,深度加1
    		}
    	}
    }
    
    void DFSTrave() //遍历图G
    {
    	for(int u = 0; u < n; u++) //对每个顶点u
    	{
    		if(vis[u] == false) //如果u未被访问
    		{
    			DFS(u, 1); //访问u和u所在的连通块,1表示初始为第一层
    		}
    	}
    }
    
    1. 邻接表版
    vector<int> Adj[MAXV]; //图G的邻接表
    int n; //n为顶点数,MAXV为最大顶点数
    bool vis{MAXV] = {false}; //如果顶点i已被访问,则vis[i] == true。初值为false
    
    void DFS(int u, int depth) //u为当前访问的顶点标号,depth为深度
    {
    	vis[u] = true; //设置u已被访问
    	/*如果需要对u进行一些操作,可以在此处进行*/
    	for(int i = 0; i < Adj[u].size(); i++)  //对从u出发可以到达的所有顶点v
    	{
    		int v = Adj[u][j];
    		if(vis[v] == false) //如果v未被访问
    		{
    			DFS(v, depth + 1); //访问v,深度加1
    		}
    	}
    }
    
    void DFSTrave() //遍历图G
    {
    	for(int u = 0; u < n; u++//对每个顶点u
    	{
    		if(vis[u] == false) //如果u未被访问
    		{
    			DFS(u, 1); //访问u和u所在的连通块,1表示初始为第一层
    		}
    	}
    }
    

    采用广度优先搜索法(BFS)遍历图

    广度优先搜索:需要使用一个队列,通过反复出队首顶点,将该顶点可到达的未曾加入过队列的顶点全部入队,直到队列为空时遍历结束。
    以一个有向图进行BFS遍历:
    从V0 开始进行遍历,黑色表示结点未访问,白色表示结点已访问,虚线边表示当前遍历路径
    在这里插入图片描述

    1. 当前队列内元素为{V0}进行访问。之后将从V0出发能够到达的两个未曾加入过队列的顶点V1、V2加入队列。
      在这里插入图片描述
    2. 当前队列内元素为{V1, V2},取出队首元素V1进行访问。之后,将从V1出发能够到达的两个未曾加入过队列的顶点V3、V4加入队列。
      在这里插入图片描述
    3. 当前队列内元素为{V2, V3, V4},取出队首元素V2进行访问。由于从V2出发无法找到未曾加入过队列的顶点(V1、V4均已加入过队列),因此不予处理。
      在这里插入图片描述
    4. 当前队列内元素为{V3, V4},取出队首元素V3进行访问。由于V3出发无法找到未曾加入过入过队列的顶点,因此不予处理。
      在这里插入图片描述
    5. 当前队列内元素为{V4},取出队首元素V4进行访问。之后,将从V4出发能够到达的一个未曾加入过队列的顶点V5加入队列。
      在这里插入图片描述
    6. 当前队列内元素为{V5},取出队首元素V5进行访问。由于从V5出发无法找到未曾加入过队列的顶点,因此不予处理。
      在这里插入图片描述
    7. 当前队列为空,BFS遍历结束。

    BFS的具体实现

    BFS遍历伪代码

    BFS(u) //遍历u所在的连通块
    {
    	queue q; //定义队列q
    	将u入队;
    	inq[u] = true; //设置u已被加入过队列
    	while(q非空) //只要队列非空
    	{
    		取出q的队首元素u进行访问;
    		for(从u出发可达的所有顶点v) //枚举从u能直接到达的顶点v
    		{
    			if(inq[v] == false) //如果v未曾加入过队列
    			{
    				将v入队;
    				inq[v] = true; //设置v已被加入过队列
    			}
    		}
    	}
    }
    
    BFSTrave(G) //遍历图G
    {
    	for(G的所有顶点u) //枚举G的所有顶点u
    	{
    		if(inq[u] == false) //如果u未曾加入过队列
    		{
    			BFS(u); //遍历u所在的连通块
    		}
    	}
    }
    
    1. 邻接矩阵版
    int n, G[MAXV][MAXV]; //n为顶点数,MAXV为最大顶点数
    bool inq[MAXV] = {false}; //若顶点i曾入过队列,则inq[i]==true。初值为false
    
    void BFS(int u) //遍历u所在的连通块
    {
    	queue<int> q; //定义队列q
    	q.push(u); //将初始点u入队
    	inq[u] = true; //设置u已被加入过队列
    	while(!q.empty()) //只要队列非空
    	{
    		int u = q.front(); //取出队首元素
    		q.pop(); //将队首元素出队
    		for(int v = 0; v < n; v++)
    		{
    		    //如果u的邻接点v未曾加入过队列
    			if(inq[v] == false && G[u][v] != INF)
    			{
    				q.push(v); //将v入队
    				inq[v] = true; //标记v为已被加入过队列
    			}
    		}
    	}
    }
    
    void BFSTrave() //遍历图G
    {
    	for(int u = 0; u < n; u++) //枚举所有顶点
    	{
    		if(inq[u] == false) //如果u未曾加入过队列
    		{
    			BFS(q); //遍历u所在的连通块
    		}
    	}
    }
    
    1. 邻接表版
    vector<int> Adj[MAXV]; //图G,Adj[u]存放从顶点u出发可以到达的所有顶点
    int n; //n为顶点数,MAXV为最大顶点数
    bool inq[MAXV] = {false}; //若顶点i曾入过队列,则inq[i] == true.初值为false
    
    void BFS(int u) //遍历单个连通块
    {
    	queue<int> q; //定义队列q
    	q.push(u); //将初始点u入队
    	inq[u] = true; //设置u已被加入过队列
    	while(!q.empty()) //只要队列非空
    	{
    		int u = q.front(); //取出队首元素
    		q.pop(); //将队首元素出队
    		for(int i = 0; i < Adj[u].size(); i++) //枚举从u出发能到达的所有顶点
    		{
    			int v = Adj[u][i];
    			if(inq[v] == false) //如果v未曾加入过队列
    			{
    				q.push(v); //将v入队
    				inq[v] = true; //标记v为已被加入过队列
    			}
    		}
    	}
    }
    
    void BFSTrave() //遍历图G
    {
    	for(int u = 0; u < n; u++) //枚举所有顶点
    	{
    		if(inq[u] == false) //如果u未曾加入过队列
    		{
    			BFS(q); //遍历u所在的连通块
    		}
    	}
    }
    

    与树的BFS遍历一样,在给定BFS初始点的情况下,可能需要输出该连通块内所有其他顶点的层号。
    首先,由于需要存放顶点层号。需要定义结构体Node,并在其中存放顶点编号和层号

    struct Node
    {
    	int v; //顶点编号
    	int layer; //顶点层号
    }
    

    vector邻接表中的元素就不再是int,而变为Node

    vector<Node> Adj[N];
    

    考虑层号的传递关系,当前顶点的层号为L,那么它所有出边的终点的层号都是L+1。

    void BFS(int s) //s为起始顶点编号
    {
    	queue<Node> q; //BFS队列
    	Node start; //起始顶点
    	start.v = s; //起始顶点编号
    	start.layer = 0; //起始顶点层号0
    	q.push(start); //将起始顶点压入队列
    	inq[start.v] = true; //起始顶点的编号设为已被加入过队列
    	while(!q.empty())
    	{
    		Node topNode = q.front(); //取出队首顶点
    		q.pop(); //队首顶点出队
    		int u = topNode.v; //队首顶点的编号
    		for(int i = 0; i < Adj[u].size(); i++)
    		{
    			Node next = Adj[u]pj]; //从u出发能到达的顶点next
    			next.layer = topNode.layer + 1; //next层号等于当前顶点层号加1
    			//如果next的编号未被加入过队列
    			if(inq[next.v] == false)
    			{
    				q.push(next); //将next入队
    				inq[next.v] = true; //next的编号设为已被加入过队列
    			}
    		}
    	}
    }
    
    展开全文
  • 哈密尔顿回路环球旅行问题即从一个结点出发经过所有结点回到出发点结点不能重复经过 设v1v2.vn是已知的n个城镇城镇vi到城镇vj的距离为dij现求从v1出发经各城镇一次且仅一次返回v1的最短路程 问题描述 解决方案 1....
  • MobileNet v1论文笔记

    2018-09-16 18:12:37
    MobileNet 论文笔记 ...出发点一个是Filter大小上,一个是Feature大小上。 模型结构 超参数1:Width Multiplier 简单来说这个就是调整Filter大小,进而减小模型大小 ...

    MobileNet v1论文笔记

    论文链接

    概述

    论文思想非常简单,主要就是利用depthwise CNN的结构来减少计算量,从而减小模型大小。论文提出了两个超参数,可以简单的调整模型大小。出发点一个是从Filter大小上,一个是从Feature大小上。

    核心思想

    (1)模型结构

    模型结构

    (2)超参数1:Width Multiplier

    简单来说这个就是调整Filter大小,进而减小模型大小
    这里写图片描述

    (3)超参数2:Resolution Multiplier

    调整Feature大小,进而减小模型大小
    这里写图片描述

    相关实现代码

    展开全文
  • 针对传统算法在抗光照变化影响、大位移光流和异质点滤除等方面的不足,人类视觉认知机理出发,提出了一种基于机器学习和生物模型的运动自适应 V1 -- MT(motion-adaptive V1 -- MT,MAV1MT)序列图像光流估计算法....
  • ShuffleNetV1/V2简述 | 轻量级网络

    千次阅读 2020-07-06 10:23:46
    ShuffleNet系列是轻量级网络中很重要的一个系列,ShuffleNetV1提出了channel shuffle操作,使得网络可以尽情地使用分组卷积来加速,而ShuffleNetV2则推倒V1的大部分设计,实际出发,提出channel split操作,在加速...

    ShuffleNet系列是轻量级网络中很重要的一个系列,ShuffleNetV1提出了channel shuffle操作,使得网络可以尽情地使用分组卷积来加速,而ShuffleNetV2则推倒V1的大部分设计,从实际出发,提出channel split操作,在加速网络的同时进行了特征重用,达到了很好的效果
    来源:晓飞的算法工程笔记 公众号

    ShuffleNet V1


    论文: ShuffleNet: An Extremely Efficient Convolutional Neural Network for Mobile Devices

    Introduction

      神经网络的精度越来越高,而推理性能也在逐渐变慢,在实际应用中不得不在性能与准确率间进行折中。为此,论文对小网络的耗时进行分析,提出了ShuffleNet。论文首先介绍了ShuffleNet的核心操作Channel Shuffle以及Group Convolutions,然后再介绍Shuffle unit的结构,最后介绍ShuffleNet的架构。

    Channel Shuffle for Group Convolutions

      在目前的一些主流网络中,通常使用pointwise卷积进行维度的降低,从而降低网络的复杂度,但由于输入维度较高,pointwise卷积的开销是十分巨大的。对于小网络而言,昂贵的pointwise卷积会带来明显的性能下降,比如在ResNext unit中,pointwise卷积占据了93.4%的计算量。为此,论文引入了分组卷积,首先探讨了两种ShuffleNet的实现:

    • 图1a是最直接的方法,将所有的操作进行了绝对的维度隔离,但这会导致特定的输出仅关联了很小一部分的输入,阻隔了组间的信息流,降低了表达能力。
    • 图1b对输出的维度进行重新分配,首先将每个组的输出分成多个子组,然后将每个子组输入到不同的组中,能够很好地保留组间的信息流。

      图1b的思想可以简单地用channel shuffle操作进行实现,如图1c所示,假设包含gg组的卷积层输出为g×ng\times n维,首先将输出reshape()为(g,n)(g, n),然后进行transpose(),最后再flatten()回g×ng\times n维。

    ShuffleNet Unit

      基于channel shuffle操作,论文提出了两种ShuffleNet unit,从图2a的基础残差结构开始,中间包含一个3×33\times 3深度卷积进行特征提取:

    • 图2b为特征图大小不变的ShuffeNet unit,将开始的1×11\times 1卷积层替换成pointwise分组卷积+channel shuffle操作,第二个pointwise分组卷积的作用是为了恢复到unit的输入维度,方便与shortcut进行element-wise addition。后面的两个卷积操作根据可分离深度卷积论文的建议只接了BN,没有接BN+ReLU。论文尝试了在第二个pointwise分组卷积后面再接一次channel shuffle操作,但并没有提高很多精度。
    • 图2c为特征图大小减半的ShuffleNet unit,可用于block间的特征下采样。主要在shortcut中添加3×33\times 3平均池化以及将最后的element-wise addition替换为channel concatenation,增加输出维度且不会带来太多的计算量。

      Shuffle unit的计算是比较高效的,对于c×h×wc\times h\times w的输入,bottleneck的中间维度为mm,ResNet unit的计算量为hw(2cm+9m2)hw(2cm + 9m^2)FLOPs,ResNeXt unit的计算量为hw(2cm+9m2/g)hw(2cm+9m^2/g)FLOPs,ShuffleNet unit的计算量为hw(2cm/g+9m)hw(2cm/g + 9m)gg为卷积的分组数。在同等计算资源情况下,计算量的减少意味着ShuffeNet可以使用维度更多的特征图,这在小网络中十分重要。
      需要注意的是,尽管深度卷积通常有较低的理论复杂度,但在实现时的效率是不高的。为此,ShuffleNet仅对bottleneck中的特征(维度较低)使用深度卷积。

    Network Architecture

      ShuffleNet的结构如表1所示,3个不同的stage由ShuffleNet unit堆叠而成,每个stage的首个ShuffleNet unit比较特殊,使用图2c的stride=2结构,特征图大小缩小一倍,channel数增大一倍。其它的ShuffleNet unit使用图2b的结构,bootlneck的维度设定为输出的1/41/4。表1中设计不同分组数的网络,并修改了对应的输出维度,模型大小整体保持在140MFLOPs左右,网络的分组数越大,可设置维度也越大。

    Experiments

      为了设定不同的网络复杂度,对表1的网络层维度加一个缩放因子ss,比如ShuffleNet 0.5X为表1的所有层输出维度减少一倍。

      对不同scale和分组数的性能。

      对比channel shuffle对不同网络大小作用。

      在保持复杂度的情况下,将stage2-4尽量替换成类似于其它主流网络结构(具体设计看原文),进行性能对比。

      对比同复杂度的MobileNet性能。

      对比主流网络的性能。

      对比作为目标检测主干的性能。

      CPU单线程推理速度对比。

    Conclusion

      ShuffleNet的核心在于使用channel shuffle操作弥补分组间的信息交流,使得网络可以尽情使用pointwise分组卷积,不仅可以减少主要的网络计算量,也可以增加卷积的维度,从实验来看,是个很不错的work。

    ShuffleNet V2


    论文: ShuffleNet V2: Practical Guidelines for Efficient
    CNN Architecture Design

    Introduction

      论文发现,作为衡量计算复杂度的指标,FLOPs实际并不等同于速度。如图1所示,FLOPs相似的网络,其速度却有较大的差别,只用FLOPs作为衡量计算复杂度的指标是不够的,还要考虑内存访问消耗以及GPU并行。基于上面的发现,论文从理论到实验列举了轻量级网络设计的5个要领,然后再根据设计要领提出ShuffleNet V2。

    Practical Guidelines for Efficient Network Design

      为了保证结果的正确性,论文在以下工业设备中进行理论的相关测试:

    • GPU. A single NVIDIA GeForce GTX 1080Ti is used. The convolution library is CUDNN 7.0
    • ARM. A Qualcomm Snapdragon 810.

      包含以下5个轻量级网络设计要领:

    1. G1: Equal channel width minimizes memory access cost (MAC).

      主流的网络大都使用深度分离卷积,其中pointwise卷积承担了大部分的计算开销。假设输入维度c1c_1和输出维度c2c_2,特征图大小为hhww,则1×11\times 1的卷积核的计算量B=hwc1c2B=hwc_1 c_2,内存访问消耗MAC=hw(c1+c2)+c1c2MAC=hw(c_1+c_2)+c_1 c_2,MAC可以表示为B相关的公式:

    MAC=hw(c1+c2)+c1c2hwc1c2+c1c2=hwB+BhwMAC=hw(c_1+c_2)+c_1 c_2 \ge hw\sqrt{c_1 c_2} + c_1 c_2=\sqrt{hwB} + \frac{B}{hw}

      上式在c1c_1c2c_2相等时取得最小值,即输入输出维度相等时,内存访问消耗最小。

      为了避免理论与实际不符,论文在实际设备上进行了对比,在保持FLOPs不变的情况下,调整输入输出维度的比例,可以看到1:1的情况下计算速度最快。因此,在设计结构时尽量保持卷积的输入输出的维度一致。

    1. G2: Excessive group convolution increases MAC

      分组卷积能够降低FLOPs,在固定的FLOPs情况下,分组卷积能够使用更多的channel数,但channel的增加会带来MAC的提高,1×11\times 1分组卷积的MAC与FLOPs的关系为

    gg为分组数,B=hwc1c2/gB=hwc_1 c_2/g为FLOPs。在固定输入和计算量情况下,MAC随着gg增加而增加。

      论文同样也在实际设备上进行了对比,使用更多的分组反而降低了推理的速度,主要由于MAC的增加。因此,需要谨慎地根据平台和任务选择分组数,选择大的分组数能带来一定程度的准确率提升,但也会导致计算消耗的快速提升。

    1. G3: Network fragmentation reduces degree of parallelism

      目前一些网络在单个block中使用了多通过,比如NASNET-A在单个block中使用了13个分支,而常规的网络仅使用2-3个分支。尽管这样的设计能够提升准确率,但是对设备并行计算不友好,会带来性能的下降。

      在实际设备上进行对比,在固定FLOPs情况下,分别对比串行和并行分支结构的性能。从结果来看,单分支的结构性能最好,性能的下降在GPU设备上最为明显。

    1. G4: Element-wise operations are non-negligible

      论文对ShuffleNetV1和MobileNetV2的耗时进行了分析,发现element-wise操作(ReLU, AddTensor, AddBias, etc)的消耗是不可忽视的,特别在GPU设备上。尽管这些操作FLOPs不高,但其MAC相对较高。

      在实际设备对比中,固定FLOPs的情况下,使用更多的element-wise操作会导致网络的性能下降。

      最后总结下论文发现的网络设计要领:

    • 使用相同输入输出维度的卷积
    • 了解分组卷积带来的损耗
    • 减少分支的数量
    • 减少element-wise操作

    ShuffleNet V2: an Efficient Architecture

      如上面提到的,ShuffleNetV1的pointwise分组卷积以及bottleneck结果均会提高MAC,导致不可忽视的计算损耗。为了达到高性能以及高准确率,关键是在不通过稠密卷积以及过多分组的情况下,获得输入输出一样的大维度卷积。

      ShuffeNetV1的unit结构如图3ab所示,为了达到上面的目的,V1的基础上加入channel split操作,如图3c所示。在每个unit的开头,将特征图分为ccc-c^{'}以及cc^{'}两部分。根据G3,一个分支直接往后传递。根据G1,另一个分支包含3个输入输出维度一样的卷积。根据G2,不再使用分组卷积,而且unit的开头已经相当于进行了分组卷积。在完成卷积操作后,将特征concate,恢复到unit的输入大小(符合G1),然后进行channel shuffle操作。这里没有了element-wise adddition操作,符合了G4,在实现的时候将concat/channel shuffle/channel split合在一起做了,能够进一步提升性能。
      空间下采样的操作进行了少量的修改,如图3d所示,去掉了channel split操作,因此输出的维度会翻倍。

      类似于ShuffleNetV1,设定c=c/2c^{'}=c/2stage2-4为堆叠ShuffleNet unit的结构,在全局池化前加了一个1×11\times 1卷积来帮助特征融合。ShuffleNetV2不仅速度快,准确率也不低,主要得益于两个方面,首先是模型性能高,使得可以使用更大的维度以及网络容量,其次是channel split可以使得部分特征直接穿过block,相当于DenseNet的特征重用。

      论文对DenseNet以及ShuffleNetV2的特征重用程度进行了可视化对比,在DenseNet中,相邻层的连接比其它层更强,意味着所有层的稠密连接存在冗余。而在ShuffleNet中,层间的影响力以(1c)/c=0.5(1-c^{'})/c=0.5的倍数进行衰减,与DenseNet有一定的相似性。

    Experiment

      将ShuffleNetV2 unit应用到大网络中进行对比。

      对比ShuffleNetV2作为检测网络主干的性能。

      与不同大小的主流分类网络进行性能对比。

    Conclusion

      论文从实践出发,以实际的推理速度为指导,总结出了5条轻量级网络的设计要领,并根据要领提出了ShuffleNetV2,很好地兼顾了准确率和速度,其中channel split操作十分亮眼,达到了类似DenseNet的特征重用效果。

    CONCLUSION


      ShuffleNet系列是轻量级网络中很重要的一个系列,ShuffleNetV1提出了channel shuffle操作,使得网络可以尽情地使用分组卷积来加速,而ShuffleNetV2则推倒V1的大部分设计,从实际出发,提出channel split操作,在加速网络的同时进行了特征重用,达到了很好的效果 。



    如果本文对你有帮助,麻烦点个赞或在看呗~
    更多内容请关注 微信公众号【晓飞的算法工程笔记】

    work-life balance.

    展开全文
  • 其中有5个顶点 Vertice(v),7条边 Edge (e),其中边上的数字代表边的权重 weight,假设我们以v1作为源点,想要找到从v1出发到其他各点的最短路径,其中路径长度指的是所经过的边的权重之和。那么根据dij

    Dijkstra单源最短路径算法

    Dijkstra算法是用来解决单源最短路径的经典方法。适用于带有非负数权重的单源有向图。

    举例说明:

    如对于以下一个图:


    这里写图片描述

    其中有5个顶点 Vertice(v),7条边 Edge (e),其中边上的数字代表边的权重 weight,假设我们以v1作为源点,想要找到从v1出发到其他各点的最短路径,其中路径长度指的是所经过的边的权重之和。那么根据dijkstra算法可以如下解决:


    这里写图片描述

    下面对算法的基本思路和实现过程进行解释说明:

    dijkstra算法往往被认为是一种贪心法,在每一次选择节点或者说路径的时候都要找邻接的顶点中最近的一个,但是实际上找到的是全局最优路径。首先,dijkstra算法将图上的所有顶点分成两类:一类是已经找到最短路径的S;一类是还未确定最短路径的Q,显然 Q = V - S 。该算法的大致思路是,每一步都在未确定最短路径的顶点中选择距离源点最短的一个,然后认为是已经确定的最短路径,然后用它来更新剩下的点的路径长度(这个过程叫做松弛,即算法中的最后一步RELAX)。更新后继续这一步骤,直到所有的点都进入S,也就是说到所有点的最短路径都被确定下来,算法结束。

    算法步骤具体如下:

    1. 先初始化,建立一个距离矩阵 distance ,大小为 Nv × Nv,其中Nv是顶点的数量。如果两点 i,j 之间直接相连,即邻接,那么distance( i, j ) = weight of i to j 。如两点不邻接,则distance( i, j ) = inf。置为无穷大。然后建立一个距离向量D ,长度为Nv,用来保存算法结束后计算出的从源点到每个点的最短距离。初始化D,即将源点所有邻接的点 k 的位置的D(k)的值置成源点到k的距离,不邻接为inf。D中的点现在都是未确定的,都是属于Q,此时S中只有源点自己。
    2. 找到D中最小的点imin,将其从Q加入S,即认为已经到该点的最短路径已经确定,就是D(imin),然后用这个点去更新未确定的点,所谓更新是指,找到imin这个点邻接的点,计算经由imin这个点到达它的邻接点的距离 D(imin) + distance(imin,thisvertice),并和D(thisvertice),即原来存储的到thisvertice的最短距离,进行比较,如果经过imin的距离即前者更小一些,那么就用这个更小的值更新D(thisvertice),这说明已经找到了另一条更近的到达thisvertice的路径。对所有的imin的邻接点做一遍,更新完毕。
    3. 重复2中的过程,直到所有的点都已经进入S,即都已经确定了最短路径。
    4. 此时D向量保存的就是源点到其他点的最短路径的值,所对应的路径在更新过程中已经得到了。

    下面用上图的栗子进行解释:

    首先

    D = 【 0, 1, inf, 3, 10 】

    ,最小是1(除了源点),所以V2已经确定,得到

    D = 【 0, 1*, inf, 3, 10 】

    然后用V2去更新,发现V2连着V3,经过V2到V3为 D(2) + distance(2,3) = 6 和 D(3) = inf 相比更小,所以更新V3。得到

    D = 【 0, 1*, 6, 3, 10 】

    然后选择V4,确定V4的最短路径就是D(4) = 3,得到

    D = 【 0, 1*, 6, 3*, 10 】

    然后看V4与V3,V5相连,更新V3,V5得到:

    D = 【 0, 1*, 5, 3*, 9 】

    然后选择V3,此时V3已经确定,得到:

    D = 【 0, 1*, 5*, 3*, 9 】

    用V3更新V5,得到:

    D = 【 0, 1*, 5*, 3*, 6 】

    选择V5,则 D = 【 0, 1, 5, 3, 6 】,至此,到所有的顶点的最短路径都已经找到。算法结束。

    感觉这个算法的一个(对于小编来说)比较难理解的或者说需要进一步解释一下的点在于:为什么每次更新得到的imin就是确定的?或者换句话说,为何每次更新都能得到一个最短路径?又或者说:取出的这个点imin,存不存在一条到达它的更短的路径?

    这个实际上是讲dijkstra算法的正确性问题,查了下书(CLRS),发现书中的做法如下:


    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述

    基本思想就是说,如果到u(就是前面的imin)的这条路径中除了imin这个点以外还有在Q中的点y的话,那么一方面,u是Q中之min,但是又由于权重非负,所以在y后面加上一些别的点直到u,肯定路径更长,所以u既小于等于到y的路径长度,又大于等于,所以就是等于。为了利用反证法,我们y取的是第一个出S但是长度为最小路径的点。而u我们规定为第一个不满足最小路经的点,由于u是第一个不满足,因此y满足最小路径,根据前面的推理,得到u为最小路径,和规定的矛盾,因此说明加入u仍保持最小路径。

    2018/01/25 21:39
    为了使灵魂宁静,一个人每天要做两件他不喜欢的事。 —— 毛姆

    展开全文
  • 移动通信自20世纪80年代... 本白皮书5G愿景与需求出发,分析归纳了5G主要技术场景、关键挑战和适用关键技术,提取了关键能力与核心技术特征并形成5G概念,在此基础上,结合标准与产业趋势,提出了5G适合的技术路线。
  • 图的遍历 之 深搜dfs

    2019-10-06 17:14:44
    从v1 出发,访问与v1 邻接但还没有访问过的顶点v2;然后再从v2 出发,进行类似的访问;…;如此进行下去,直至到达所有邻接顶点都被访问过的某个顶点x 为止;接着,回退一步,回退到前一次刚访问过的顶点,看是否...
  • 动态规划求解TSP(旅行商)问题

    万次阅读 2012-11-28 20:29:40
    某推销员要从城市v1出发,访问其它城市v2,v3,…,v6各一次且仅一次,最后返回v1。... K=1表示刚从V1出发,k=7表示已回到起点V1 状态变量Xk=(i,Sk):已遍历k个结点,当前位于i结点,还未遍历的结点集合为Sk。则
  • 对于树的最远两节点的距离的理解

    千次阅读 2015-04-25 17:16:22
    定义:n个节点的树,任选一个节点V0,找到距离它最远的节点V1,再找距离V1最远的节点V2,edge(V1,V2) 即为树的...因此,再从V1出发,找距离V1最远的节点V2,必定通过root,所以可以看成是找距离root最远的节点V2(不能回头搜索V1
  • DFS求图中两点的所有的路径

    万次阅读 多人点赞 2018-01-12 15:25:42
    用DFS算法来求图中两点的所有的路径,在给出代码前,先给大家讲解清楚该算法的原理。  DFS本来被用作图的遍历,现在我们对它进行改造...1.从v1出发,将v1标记,并将其入栈。 2.找到v0,将其标记,将其入栈。 3.找到
  • Sicily 3703. Huffman Coding V1

    千次阅读 2012-02-10 00:05:50
    Huffman树……自己查了下资料才知道具体是怎么弄出来的,基本步骤是: ...4.查找某一个节点的编码时,根节点出发,往左是0,往右是1,直到找到这个节点(必为叶子),整个历程就是这个节点的编码
  • 从V1出发,假设经过的路线为V1,V2,....VK,V1,那么必须满足K>2, 即除了出发点以外至少要经过2个其他不同的景区,而且不能重复经过同一个景区。 现在8600需要你帮他找一条这样的路线,并且花费越少越好。 能...
  • dfs 算法的使用

    千次阅读 2014-04-01 15:12:02
    算法思想,dfs算法是一个递归的过程,有回退的过程,对于一个无向连通图,访问图中某个顶点v0后,然后访问它的某一个邻接顶点v1,然后再从v1出发,访问v1的违访问过的邻接顶点,如此下去,直至到达所有的领接顶点都...
  • 边上权值非负情形的单源最短路径问题 Dijkstra算法的应用场景:给定一个带权有向图D与源点v,求从v到...②集合T是已求得最短路径的终点的集合,则可证明:下一条最短路径必然是从v1出发,中间只经过T中的顶点便可到达
  • 广度优先搜索

    2019-01-24 13:41:16
    广度优先搜索 前言 广度优先搜索也是图中遍历的一种...1.定一个出发点:假设我们从v1出发来遍历这个图,那么广度优先遍历就是按层来遍历, 2.遍历该节点所能到达的节点:他首先遍历v1能到的俩个节点v2和v3,然后将这...
  • 图的遍历:BFS和DFS

    2015-03-10 15:37:40
     深度优先遍历的基本思想是访问顶点V0,然后访问V0邻接到的未被访问的顶点V1,再从V1出发递归地按照深度优先的方式遍历。当遇到一个所有邻接于它的顶点都被访问过了的顶点u时,则回到自己访问顶点序列中最后一个...
  • 图的广度优先遍历

    2019-03-02 14:56:00
    广度优先遍历也是图的遍历中一种,其原理同广度优先搜索大致相同, 运用了队列,当我们找到一个未被访问过...如图C:从v1出发遍历过程为:v1-v2-v3-v4-v5-v6-v7 Code: #include<cstdio> #include<i...
  • dfs算法的使用

    千次阅读 2014-02-26 22:15:31
    算法思想,dfs算法是一个递归的过程,有回退的过程,对于一个无向连通图,访问图中某个顶点v0后,然后访问它的某一个邻接顶点v1,然后再从v1出发,访问v1的违访问过的邻接顶点,如此下去,直至到达所有的领接顶点都...
  • 现在某人要从V1出发,通过这个交通网到V8去,求使总费用最小的旅行路线。 在线作图软件:在线做图 最短路径代码: clear;clc; s=[1112334555566799];%边的顶点编号1 t=[234...
  • 图的深度优先遍历

    2019-03-02 11:01:00
    图的遍历方式有两种,分别是图的深度优先遍历和图的广度优先遍历 其中,深度优先遍历的应用更为广泛。 深度优先遍历同深度优先搜索,“不撞南墙不回头” ...比如上面这个图,它的深度优先遍历的顺序(从v1出发) ...
  • DFS和BFS链式前向星的实现

    千次阅读 2014-04-10 18:57:59
    图的深度优先遍历,基本思想是访问顶点,然后访问v0邻接到的未被访问的点顶点v1,在从v1出发递归地按照深度优先的方式遍历。当遇到一个所有邻接于它的顶点都被访问了的顶点u时,则回到已访问顶点的序列中最后一个...
  • 基本思想:访问顶点v0,然后访问v0邻接的未访问过的顶点v1,再从v1出发递归的按照深度优先的方式遍历。当遇到一个所有邻接于它的顶点都被访问过的顶点u时,则回到顶点序列中最后一个拥有未被访问过的相邻节点的顶点W,...
  • ACM图论算法—邮递员投递问题

    万次阅读 2016-10-21 22:31:14
    题目描述著名图论问题之一。邮递员从邮局出发送信,要求对辖区内每条街,都至少通过一次,再回邮局。在此条件下,怎样选择一条最短...快递员从V1出发给V2、V3、V4、V5、 V6、V7、V8、V9派发快递,求派完所有回到原出
  • 引例:求从v1出发到v11的最短路径 敲黑板划重点!!数学建模时更多是有向和无向的混合图!!(反向时即设置为inf) 程序: 子程序: function [min,path]=dijkstra(w,start,terminal) n=size(w,1);...
  • DFS深度优先遍历算法简单分析

    千次阅读 2014-02-21 13:31:32
    一般在涉及图论的算法题的时候都会用到遍历有关方面...有回退的过程,对于一个无向连通图,访问图中某个顶点v0后,然后访问它的某一个邻接顶点v1,然后再从v1出发,访问v1的违访问过的邻接顶点,如此下去,直至到达所有
  • 描述:一个加权有向完全图,找出里面的最小TSP圈。可以使用动态规划,差分,枚举... 变量K,已经便利过K个顶点,K=1,2,3,4,5,K=1表示刚从V1出发,K=5表示已经回到起点。 状态变量xk=(i, Sk); 已遍历k个节点,...
  • 在上篇文章中,我们已经总结出要求最短路径时的边权的三种可能情况,并且已经成功...此算法描述默认是从v1出发的 例题 12435 计算从结点1到其他各结点的最短路径,其算法流程如下: 首先按照a步骤初始化π数组(其实π
  • (1)某个顶点V出发,访问该顶点的所有邻接点V1,V2..VN (2)邻接点V1,V2...VN出发,再访问他们各自的所有邻接点 (3)重复上述步骤,直到所有的顶点都被访问过 .深度优先遍历(DFS) (1)某个顶点V出发,访问顶点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 542
精华内容 216
关键字:

从v1出发