精华内容
下载资源
问答
  • 路径覆盖

    千次阅读 2017-03-14 18:27:51
    homework3:路径覆盖 a.数据流图       b.数组越界时,可能会发生错误 c.不经过while循环,使得 初始条件n=1 d.. 点覆盖 {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} 边覆盖 {(1.2),(2,3),(3...

    homework3:路径覆盖



    a.数据流图

     

     

     

    b.数组越界时可能会发生错误

    c.不经过while循环,使得 初始条件n=1

    d..

    点覆盖  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

    边覆盖

    {(1.2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,5),(6,8),(8,9),(9,10),(9,11),(10,2),(11,2),(2,12),(12,13),(13,14),(14,15),(15,13),(13,16)}

    主路径覆盖

    {(1,2,3,4,5,6,7),

    (1,2,3,4,5,9,10),

    (1,2,3,4,5,9,11),

    (1,2,3,4,5,6,8,9,10),

    (1,2,3,4,5,6,8,9,11),

    (1,2,12,13,16),

    (1,2,12,13,14,15),

    (3,4,5,6,8,9,10,2,12,13,14,15),

    (3,4,5,6,8,9,10,2,12,13,16),

    (3,4,5,9,10,2,12,13,14,15),

    (3,4,5,9,11,2,12,13,14,15),

    (3,4,5,9,10,2,12,13,16),

    (3,4,5,9,10,2,12,13,16),

    (3,4,5,6,8,9,11,2,12,13,14,15),

    (3,4,5,6,8,9,11,2,12,13,16),

    (6,7,5,9,10,2,12,13,14,15),

    (6,7,5,9,10,2,12,13,16),

    (6,7,5,9,11,2,12,13,14,15),

    (6,7,5,9,11,2,12,13,16),

    (14,15,13,16),

    (13,14,15,13),

    (5,6,7,5),

    (2,3,4,5,6,8,9,10,2),

    (2,3,4,5,6,8,9,11,2),

    (2,3,4,5,9,10,2)

    (2,3,4,5,9,11,2)}

     

     

    Another:第一次上机实验 判断三角形程序

    由于三角形的种类有三种,外加一种判断输入参数是否为正整数的返回值,因此主路径测试需求有四个,测试四组用例(2,2,2),(2,3,3),(2,3,4),(-2,5-6)。即可完整覆盖,覆盖率达到100%

     

     

     

     


    展开全文
  • 最小路径覆盖 Description 定义: 一个不含圈的有向图G中,G的一个路径覆盖是一个其结点不相交的路径集合P,图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束,且长度也为任意值,包括0。请...

    最小路径覆盖

    Description

    定义: 一个不含圈的有向图G中,G的一个路径覆盖是一个其结点不相交的路径集合P,图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束,且长度也为任意值,包括0。请你求任意一个不含圈的有向图G的最小路径覆盖数。

    提示:最小路径覆盖数=G的定点数-最小路径覆盖中的边数
    最小路径覆盖数=原图G的顶点数-二分图的最大匹配数

    Input

    t 表示有t组数据;n 表示n个顶点(n<=120);m 表示有m条边;
       接下来m行,每行有两个数 i,j表示一条有向边。

    Output

    最小路径覆盖数

    Sample Input

    2
    4
    3
    3 4
    1 3
    2 3
    3
    3
    1 3
    1 2
    2 3

    Sample Output

    2
    1

    解题思路

    这题就是一道最小路径覆盖模板题目

    最小路径覆盖
    在这里插入图片描述

    定义:在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。 最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。 最小不相交路径覆盖:每一条路径经过的顶点各不相同。如图,其最小路径覆盖数为3。即1->3>4,2,5。 最小可相交路径覆盖:每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1->3->4,2->3>5。 特别的,每个点自己也可以称为是路径覆盖,只不过路径的长度是0。

    什么是有向图G的最小路径覆盖?首先,图G必须是有向无环的。路径覆盖就是在图G中找出一些路径,每条路径从起点走到终点并且标记中间经过的点。最后,每个点只被标记一次。选出的这些路径组成路径覆盖。如果找出最少的路径成为一个路径覆盖,则称为最小路径覆盖。

    在这里插入图片描述

    在上图中,以下两个均是路径覆盖: a、<1,2> <4,6> <3> <5> b、<1,2,4,6> <3> <5> 在上面两个覆盖中b为最小覆盖,|b|=3,而|a|=4。(注意一个单独的节点也是一个路径)

    由原图G构造对应的二分图S,将原图G中的每个点i拆成两个点i1和i2,i1和i2属于S。i1组成二分图的X集合,i2组成Y集合。若原图G中有边<i,j>,则在S中有边<i1,j2>,则上面的图可以得到如下二分图: 法:把原图的每个点V拆成Vx和Vy两个点, 如果有一条有向边A->B,那么就加边Ax−>By 。这样就得到了一个二分图。 那么最小路径覆盖=原图的结点数-新图的最大匹配数。
    在这里插入图片描述
    证明:一开始每个点都是独立的为一条路径,总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径,也就相当于路径数减少了1。所以找到了几条匹配边,路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。 因为路径之间不能有公共点,所以加的边之间也不能有公共点,这就是匹配的定义。

    AC代码

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    long long n,m,T,x,y,tot,answer,head[1005],cover[1005],father[1005];
    struct node//结构体
    {
    	long long to,next;
    }a[1000005];
    void add(long long x,long long y)//邻接表
    {
    	a[++tot]=(node){y,head[x]};
    	head[x]=tot;
    }
    bool dfs(long long x)//dfs
    {
    	if(x==0)return true;
    	for(long long i=head[x];i;i=a[i].next)
    	 if(cover[a[i].to]==0)
    	 {
    	 	cover[a[i].to]=1;
    	 	long long sum=father[a[i].to];
    		father[a[i].to]=x;
    	 	if(sum==0||dfs(sum))return true;
    	 	father[a[i].to]=sum;
    	 }
    	return false;
    }
    int main()
    {
    	scanf("%lld",&T);
    	while(T--)
    	{
    		tot=answer=0;//清零
    		memset(head,0,sizeof(head));
    		memset(father,0,sizeof(father));
    		scanf("%lld%lld",&n,&m);
    		for(long long i=1;i<=m;i++)
    		{
    			scanf("%lld%lld",&x,&y);
    			add(x,y);//建边
    		}
    		for(long long i=1;i<=n;i++)//匈牙利算法
    		{
    			memset(cover,0,sizeof(cover));
    			dfs(i);
    		}
    		for(long long i=1;i<=n;i++)
    	 	 if(father[i]!=0)answer++;
    		printf("%lld\n",n-answer);
    	}
    	return 0; 
    }
    

    谢谢

    展开全文
  • 最小路径覆盖

    千次阅读 多人点赞 2018-08-24 10:37:48
    花了好长时间,用于找了几篇能看懂的最小路径覆盖。 定义:通俗点将,就是在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。 最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。 最小不...

    花了好长时间,用于找了几篇能看懂的最小路径覆盖。

     

    定义:通俗点将,就是在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。

    最小路径覆盖分为最小不相交路径覆盖最小可相交路径覆盖

    最小不相交路径覆盖:每一条路径经过的顶点各不相同。如图,其最小路径覆盖数为3。即1->3>4,2,5。

    最小可相交路径覆盖:每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1->3->4,2->3>5。

    特别的,每个点自己也可以称为是路径覆盖,只不过路径的长度是0。

     

    大家要仔细想想上面的解释啊,这已经是我找到的最浅显的了。

    而且一定要知道有这两种最小路径覆盖。

    然后如果大家不知道匈利亚算法的,一定要去看看,还是比较简单的,就是一个dfs,连我都看的懂。

    下面地址是关于匈利亚算法的详解,带图解,易懂

    https://blog.csdn.net/Arabic1666/article/details/79824390

    DAG的最小不相交路径覆盖

    算法:把原图的每个点V拆成VxVx和VyVy两个点,如果有一条有向边A->B,那么就加边Ax−>ByAx−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。

    证明:一开始每个点都是独立的为一条路径,总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径,也就相当于路径数减少了1。所以找到了几条匹配边,路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。

    因为路径之间不能有公共点,所以加的边之间也不能有公共点,这就是匹配的定义。

    说的拆点这么高深,其实操作起来超级超级简单,甚至没有操作。

    简单的来说,每个顶点都能当成二分图中作为起点的顶点。

    至于为什么答案是 n-ans,我谈谈我的理解

    用dfs求的ans表示的意思是匹配数,换句话说,就是一条路连着的路径上的点的个数-1

    比如说这个图,我们用匈牙利算法,遍历每个点,发现1、3点可行,可匹配,而2、4、5都不能行。

    如果我们单纯考虑1->3->5这条路径,有三个点,然后有两个点匹配了,我们用3减去2,就得到了1,这个1就是一个路径数,需要用1条路径来覆盖,再对剩下的2、4考虑,分别都需要一条路径来覆盖,因为2-0=0,2是顶点个数,0是匹配数。

    所以,对于每条分路径,我们需要 v-cnt的路径来覆盖,最后将每个分路径合起来,我们得到n-cnt。

    例题:POJ1422

     

    //
    //  main.cpp
    //  POJ1422最小不想交路径覆盖
    
    
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <vector>
    using namespace std;
    const int N = 200 + 10;
    vector<int> g[N];
    int cy[N];
    bool vis[N];
    bool dfs(int u)
    {
        for(int i=0; i<g[u].size(); ++i)
        {
            int v = g[u][i];
            if(vis[v]) continue;
            vis[v] = true;
            if(cy[v]==-1 || dfs(cy[v])){
                cy[v] = u;
                return true;
            }
        }
        return false;
    }
    int solve(int n)
    {
        int ret = 0;
        memset(cy, -1, sizeof(cy));
        for(int i=1;i<=n;++i)
        {
            memset(vis, 0, sizeof(vis));
            ret += dfs(i);
        }
        return n - ret;
    }
    int main( )
    {
        int t,n,m;
        int u,v;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;++i)
                g[i].clear();
            for(int i=0;i<m;++i)
            {
                scanf("%d%d",&u,&v);
                g[u].push_back(v);
            }
            
            int ans = solve(n);
            printf("%d\n",ans);
        }
        return 0;
    }

     

     

    DAG的最小可相交路径覆盖

    算法:先用floyd求出原图的传递闭包,即如果a到b有路径,那么就加边a->b。然后就转化成了最小不相交路径覆盖问题。

    证明:为了连通两个点,某条路径可能经过其它路径的中间点。比如1->3->4,2->4->5。但是如果两个点a和b是连通的,只不过中间需要经过其它的点,那么可以在这两个点之间加边,那么a就可以直达b,不必经过中点的,那么就转化成了最小不相交路径覆盖。

    上面的解释很不错,点个赞!

    题目POJ2594

    //
    //  main.cpp
    //  POJ2594最小可相交路径覆盖
    //
    //  Created by beMaster on 16/4/8.
    //  Copyright © 2016年 beMaster. All rights reserved.
    //
    
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <vector>
    using namespace std;
    const int N = 500 + 10;
    bool dis[N][N];
    bool vis[N];
    int cy[N];
    void floyd(int n){
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                for(int k=1;k<=n;++k)
                    if(dis[i][k] && dis[k][j])//传递可达性
                        dis[i][j] = true;
    }
    bool dfs(int u, int n){
        for(int i=1;i<=n;++i){
            if(!vis[i] && dis[u][i]){
                vis[i] = true;
                if(cy[i]==-1 || dfs(cy[i], n)){
                    cy[i] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int solve(int n){
        int cnt = 0;
        memset(cy,-1,sizeof(cy));
        for(int i=1;i<=n;++i){
            memset(vis,0,sizeof(vis));
            cnt += dfs(i, n);
        }
        return n - cnt;
    }
    int main( ) {
        int n,m;
        int a,b;
        while(scanf("%d%d",&n,&m),n+m){
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    dis[i][j] = false;
            for(int i=1;i<=m;++i){
                scanf("%d%d",&a,&b);
                dis[a][b] = true;
            }
            floyd(n);
            int ans = solve(n);
            printf("%d\n",ans);
        }
        return 0;
    }

     

    做完这两道例题,可以做做我拉的题目啊,欢迎欢迎

    https://vjudge.net/contest/249592#problem

     

    展开全文
  • 最小路径覆盖详解

    千次阅读 2019-08-07 11:14:12
    而最小路径覆盖又分为:最小不相交路径覆盖 和 最小可相交路径覆盖。 最小不相交路径覆盖 : 就是我们找到的每条路径不能相交,就是每条路径不能有同一个点。 最小可相交路径覆盖 : 这个与上面相对应,就是可以相交...

    定义:通俗点讲,就是在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。

    而最小路径覆盖又分为:最小不相交路径覆盖最小可相交路径覆盖。

    最小不相交路径覆盖 : 就是我们找到的每条路径不能相交,就是每条路径不能有同一个点。
    最小可相交路径覆盖 : 这个与上面相对应,就是可以相交。

    注意:每个点被自己覆盖,路径长度为0


    求解最小不相交路径覆盖: 我们把每个点都拆成两个点,分为入点和出点,如果 u 到 v 有边,那么我们就让 u 的入点连向 v 的出点 , 最后跑一下最大流或者匈牙利 算出最大匹配。答案就是 点的数目 - 最大匹配数

    求解最小可相交路径覆盖: 和上面很相似,但是我们再跑最大匹配时,我们先对原图进行一次闭包传递(通过Warshell传递闭包算法),然后过程就一样了。


    最小不相交路径覆盖题目:POJ - 1422

    AC代码:

    #pragma GCC optimize(2)
    #include<cstring>
    #include<iostream>
    #define int long long
    using namespace std;
    const int N=250;
    int T,n,m,mat[N],vis[N],res;
    int head[N],nex[N*N],to[N*N],tot;
    void add(int a,int b){
    	to[++tot]=b; nex[tot]=head[a]; head[a]=tot; 
    }
    bool find(int x,int id){
    	for(int i=head[x];i;i=nex[i]){
    		if(vis[to[i]]!=id){
    			vis[to[i]]=id;
    			if(!mat[to[i]]||find(mat[to[i]],id)){
    				mat[to[i]]=x;	return 1;
    			}
    		}
    	}
    	return 0;
    }
    signed main(){
    	cin>>T;
    	while(T--){
    		memset(head,0,sizeof head);	res=tot=0;
    		memset(mat,0,sizeof mat);	memset(vis,0,sizeof vis);	
    		cin>>n>>m;
    		while(m--){
    			int a,b;	cin>>a>>b;	add(a,b);
    		}
    		for(int i=1;i<=n;i++)	res+=find(i,i);
    		cout<<n-res<<endl;
    	}
    	return 0;
    }
    

    最小可相交路径覆盖题目:POJ - 2594

    AC代码:

    #pragma GCC optimize(2)
    #include<cstring>
    #include<iostream>
    #define int long long
    using namespace std;
    const int N=510;
    int n,m,mat[N],vis[N],g[N][N],res;
    void Warshell(){
    	for(int k=1;k<=n;k++)
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=n;j++)
    				if(g[i][k]&&g[k][j])	g[i][j]=1;
    }
    bool find(int x,int id){
    	for(int i=1;i<=n;i++){
    		if(g[x][i]&&vis[i]!=id){
    			vis[i]=id;
    			if(!mat[i]||find(mat[i],id)){
    				mat[i]=x;	return 1;
    			}
    		}
    	}
    	return 0;
    }
    signed main(){
    	while(cin>>n>>m,n||m){
    		memset(g,0,sizeof g);	memset(vis,0,sizeof vis);
    		memset(mat,0,sizeof mat);	res=0;
    		while(m--){
    			int a,b;	cin>>a>>b;	g[a][b]=1;
    		}
    		Warshell();
    		for(int i=1;i<=n;i++)	res+=find(i,i);
    		cout<<n-res<<endl;
    	}
    	return 0;
    }
    
    展开全文
  • Z路径覆盖

    千次阅读 2014-11-05 15:28:00
    Z路径覆盖路径覆盖的一个变体。路径覆盖是白盒测试最为典型的问题。着眼于路径分析的测试可称为路径测试。完成路径测试的理想情况是做到路径覆盖。对于比较简单的小程序实现路径覆盖是可能做到的。但是如果程序中...
  • 基于turtlesim小乌龟实现的ROS 扫地机器人路径覆盖算法,及差速控制。 使用方法: 1、下载源码 cd catkin_ws/src catkin_create_pkg turtlesim_cleaner cd catkin_ws catkin_make 2、运行 roscore //ROS Master ...
  • 为解决云化SCADA在线测试问题,依托消息掩码认证技术设计以业务组件为最小粒度的路径覆盖测试方法:构建探针类的消息掩码认证组件,插装到业务组件中;解析测试用例,实时推送测试消息给测试通讯总线;设计包含测试...
  • 基本路径覆盖

    万次阅读 多人点赞 2018-01-22 20:49:45
    白盒测试的测试方法有代码检查法、静态结构分析法、静态质量度量法、逻辑覆盖法、基本路径测试法、域测试、符号测试、Z路径覆盖、程序变异。  其中运用最为广泛的是基本路径测试法。  基本路径测试法是在...
  • 白盒测试之路径覆盖

    千次阅读 2020-04-27 10:20:13
    白盒测试之路径覆盖 路径覆盖 路径覆盖的含义 选取足够多的测试数据,使程序的每条可能路径都至少执行一次(如果程序图中有环,则要求每个环至少经过一次)。 链 连续的边。也被称作一条路径 圈复杂度: 圈复杂度...
  • 基于节点概率的路径覆盖测试数据进化生成
  • 融入神经网络的路径覆盖测试数据进化生成
  • 为提高路径覆盖测试效率,提出采用融入自适应迁移的生物地理学优化算法自动生成满足目标路径覆盖的测试用例。首先,根据路径覆盖难易,在分支距离法中引入加权因子并转换为栖息地适应指数;然后,综合最优栖息地和...
  • 路径覆盖 语句覆盖 基本思想:设计用例,使程序中的每个可执行语句至少执行一次。 每个可执行语句:每个语句,那么下图中执行为:1->2->3->4 优点:可以很直观的从源代码获得用例,无需细分每条判定...
  • 复杂软件大规模路径覆盖测试数据生成问题普遍存在, 但缺乏有效的解决方法, 为此提出一种基于自适应 分组的大规模路径覆盖测试数据进化生成方法. 在进化过程中, 通过合并满足条件的组, 将测试数据生成问题转化为...
  • 该框架基于嵌入式软件测试的特点及路径覆盖的相关理论,包括被测试程序的静态分析、插桩技术和数据处理分析等部分。以静态分析指导插桩库的建立,通过插桩技术在程序分支或重要位置点植入探针,执行已插桩程序,获得...
  • 面向多路径覆盖的演化测试,韦庆杰,李呓瑾,对面向多路径覆盖的演化测试基本参数进行实验,并首次针对多路径覆盖测试给出了基本参数对方法效率的影响规律以及参数的建议设置
  • 用例设计方法-路径覆盖;语句覆盖判定覆盖条件覆盖判定条件覆盖这四种覆盖方法都在一定程度上进行测试路径的覆盖但每种方法都无法做到100%路径覆盖都存在漏测的风险而被测对象要得到正确的结果按照预期的行为去运行就...
  • 语句覆盖 条件覆盖 判定覆盖 判定条件覆盖 条件组合覆盖 路径覆盖
  • 行业分类-物理装置-一种路径覆盖率反馈的模糊测试方法及装置.zip
  • 最近在复习软件测试的考试,每次...根据覆盖目标的不同和覆盖源程序语句的详尽程度,逻辑覆盖又可分为:语句覆盖,判定覆盖,条件覆盖,条件/判定覆盖,条件组合覆盖,路径覆盖 这里以一个题目引入: if (a&gt;...
  • (1)掌握逻辑覆盖和路径覆盖测试的基本方法 二、实验要求 (1)完成程序的编写 (2)运用逻辑覆盖和基本路径覆盖测试的覆盖准则设计被测程序的测试用例,并运行测试用例检查程序的正确与否 三、实验内容 (1)...
  • 基于路径覆盖的测试数据生成方法研究,姜光柱,姜淑娟,为了解决目前结构性演化测试缺乏面向路径覆盖标准的问题,提出了基于路径距离和节点分支相结合的适应度函数构造方法,以用于生成
  • 定义: 运行所测程序,要覆盖程序中所有可能的路径。...eg:代码案例里面共有4条路径,设计测试用例执行了3条路径,则路径覆盖率就为3/4=75%。 测试用例: 以下图为例: 依照上图:我们要想覆盖率为百分之百 判定条...
  • 水下传感网中实现多个移动目标的协同追踪任是一个技术难题,针对这个问题论文提出了一种分布式的多目标有向路径覆盖增强算法。在实际的三维水下传感网中,水下传感器节点会随着水流运动而移动,被追踪的目标具有自主...
  • 白盒测试---基本路径覆盖

    万次阅读 多人点赞 2019-04-29 16:45:59
     ...白盒测试的测试方法有代码检查法、静态结构分析法、静态质量度量法、逻辑覆盖法、基本路径测试法、域测试、符号测试、Z路径覆盖、程序变异。  其中运用最为...
  • 本文研究消息传递并行程序多路径覆盖测试数据生成问题,并提出基于分组的测试数据进化生成方法。首先根据并行程序包含的进程数、可用的计算资源以及路径相似度,将目标路径分成若干组,并基于每组目标路径,建立多...
  • 用C++解决最小生成树与最短路径覆盖问题 VC++ 6.0下编译通过
  • 行业分类-物理装置-结合关键点概率与路径相似度的多路径覆盖方法及系统.zip

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 504,038
精华内容 201,615
关键字:

路径覆盖