精华内容
下载资源
问答
  • 化学反应优化算法求解最小顶点覆盖问题
  • 针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以...
  • 通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法。该算法消除了邻接度数的概念,直接...
  • 最小顶点覆盖的混合贪心算法

    千次阅读 2018-01-11 20:10:27
    NP问题:基于无向图的最小顶点覆盖的混合贪心算法(MGA) #include #include #include #include #include #include #include #define MAX 100 using namespace std; int n,m; struct Edge { int u,v; }; struct...
    NP问题:基于无向图的最小顶点覆盖的混合贪心算法(MGA)
    #include<cstdio>
    #include<cstring>
    #include<vector>
    #include<algorithm>
    #include<math.h>
    #include<iostream>
    #include<set>
    
    #define MAX 100
    
    using namespace std;
    
    int n,m;
    struct Edge
    {
        int u,v;
    };
    struct Point
    {
        int id;
        int degree,adj_degree;
    } point[MAX];                   //点集
    vector<Edge> E;                 //边集
    vector<int> G[MAX];             //每个点的相邻点集(相当于一个二维变长数组)
    int degree[MAX],adj_degree[MAX];//每个点的度数和邻接度数
    bool del[MAX],vis[MAX];         //已删除的点集、已访问过的点集
    int V_cnt,Vv_cnt,E_cnt;         //统计已经覆盖的顶点和边
    
    void init_edge()
    {
        E.clear();
        for(int i=1; i<=n; i++) G[i].clear();
    }
    void add_edge(int u,int v)
    {
        E.push_back((Edge) {u,v} );
        E.push_back((Edge) {v,u} );
        int _size=E.size();
        G[u].push_back(_size-2);
        G[v].push_back(_size-1);
    }
    bool cmp(Point a,Point b)
    {
        return a.adj_degree>b.adj_degree;
    }
    void pretreat()                 //预处理:计算每个顶点的度数和邻接度数
    {
        for(int i=1; i<=n; i++)
        {
            point[i].degree=0;
            if(del[i]) continue;
            for(int j=0,_size=G[i].size(); j<_size; j++)
            {
                Edge& e=E[G[i][j]];
                if(!del[e.v]) point[i].degree++;
            }
            //cout<<"第"<<i<<"个点的度数为:"<<point[i].degree<<endl;
            if(point[i].degree==0) del[i]=1;
        }
        for(int i=1; i<=n; i++)
        {
            if(del[i])
            {
                point[i].adj_degree=0;
                continue;
            }
            point[i].adj_degree=point[i].degree;
            for(int j=0,_size=G[i].size(); j<_size; j++)
                point[i].adj_degree+=point[E[G[i][j]].v].degree;
            //cout<<"第"<<i<<"个点的邻接度数为:"<<point[i].adj_degree<<endl;
        }
        sort(point+1,point+n+1,cmp);
    }
    void MinVC_MGA(bool ans[])          //最小顶点的混合贪心算法
    {
        memset(del,0,sizeof(del));
        for(int i=1; i<=n; i++) point[i].id=i;
        E_cnt=0;
        //int flag=1;   //测试子图划分次数
        while(E_cnt<m)
        {
            memset(vis,0,sizeof(vis));  //每次选取最大度点删除后都需要还原访问数组
            pretreat();                 //重新计算每个点的度数
            V_cnt=0;
            Vv_cnt=0;
            for(int i=1; i<=n; i++) if(!del[i]) Vv_cnt++;
            for(int i=1; i<=n; i++)
            {
                if(del[point[i].id]) continue;
                if(vis[point[i].id]) continue;
                //cout<<point[i].id<<endl;
                ans[point[i].id]=1;             //加入到最小顶点覆盖集中
                del[point[i].id]=1, Vv_cnt--;
                for(int j=0,_size=G[point[i].id].size(); j<_size; j++)
                {
                    Edge& e=E[G[point[i].id][j]];
                    if(del[e.v]) continue;
                    E_cnt++;
                    if(!vis[e.v])
                    {
                        vis[e.v]=1;
                        V_cnt++;
                    }
                }
                if(V_cnt>=Vv_cnt) break;        //该子图中的点全部被访问过了
            }
            //flag++;
        }
        //cout<<flag<<endl;
    }
    void fileInput(){                           //从文件中读取网络信息
        int countN=0,countM=0;
        set<int> s;
        FILE *fp;
        int u,v;
        char fname[100];
    
        cout<<"\n请输入顶点网络(文件名):";
        gets(fname);
        while((fp=fopen(fname,"r"))==NULL) {cout<<"文件名输入错误,请重新输入!\n";break;}
        while(fscanf(fp,"%d %d\n",&u,&v)!=EOF){
            if(s.count(u)==0){s.insert(u);countN++;}
            if(s.count(v)==0){s.insert(v);countN++;}
            add_edge(u,v);
            countM++;
        }
        m=countM;
        n=countN;
        fclose(fp);
    }
    int main()
    {
        /*
        cout<<"请输入图中顶点个数:";
        cin>>n;
        cout<<"请输入图中边数:";
        cin>>m;
        cout<<"请输入边(u,v):"<<endl;
        for(int i=1,u,v; i<=m; i++)
        {
            cin>>u>>v;
            add_edge(u,v);
        }
        */
        //int maxNum=(int)ceil(log(m)/log(2));
     while(1){
        init_edge();
        fileInput();
        bool ans[n];                        //记录最小顶点覆盖集
        memset(ans,0,sizeof(ans));
        MinVC_MGA(ans);
        cout<<"最小控制顶点集为:";
        for(int i=1; i<=n; i++)
        {
            if(ans[i]==true) cout<<i<<" ";
        }
     }
        return 0;
    }
    

    展开全文
  • 竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来达到优化...采用竞争决策算法原理,利用竞争决策算法的通用模型,求解图的最小顶点覆盖问题。
  • 题意:一个n*n的网格中,有k个大小为1*1的小行星,现在可以用...简单的二分图匹配求最小顶点覆盖. 最小顶点覆盖=最大匹配. 然后考虑如何建图:我们考虑将横纵坐标看成点,将星球位置看成边,这样就行了 #include...

    原题地址:http://poj.org/problem?id=3041

    题意:一个n*n的网格中,有k个大小为1*1的小行星,现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。

    思路;简单的二分图匹配求最小顶点覆盖.
    最小顶点覆盖=最大匹配.
    然后考虑如何建图:我们考虑将横纵坐标看成点,将星球位置看成边,这样就行了

    #include <cmath>
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <stack>
    #include <set>
    #include <cctype>
    #define eps 1e-8
    #define INF 0x3f3f3f3f
    #define MOD 1e9+7
    #define PI acos(-1)
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    #define CLR(x,y) memset((x),y,sizeof(x))
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 1e5 + 5;
    int  n, k;
    struct node {
        int u, v, nxt;
    } e[maxn];
    int head[maxn], tot;
    void add_edge(int u, int v) {
        e[tot].u = u;
        e[tot].v = v;
        e[tot].nxt = head[u];
        head[u] = tot++;
    }
    int vis[maxn], linker[maxn];
    bool dfs(int u) {
        for(int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            if(!vis[v]) {
                vis[v] = 1;
                if(linker[v] == -1 || dfs(linker[v])) {
                    linker[v] = u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int solve() {
        int ans = 0;
        CLR(linker, -1);
        for(int i = 1; i <= n; i++) {
            CLR(vis, 0);
            ans += dfs(i);
        }
        return ans;
    }
    int main() {
        tot = 0;
        CLR(head, -1);
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= k; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            add_edge(x, y + n); //连接点的标号
        }
        printf("%d\n", solve());
        return 0;
    }
    
    展开全文
  • 在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的...
  • 有课程文档 有代码 你要的都有。 最小顶点覆盖问题 ...G的最小顶点覆盖是指G中所含顶点权之和最小顶点覆盖。 编程任务: 对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小顶点覆盖
  • 算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间。实验结果表明了该算法的可行性...
  • 思路:你按照当(x,y)上有点的时候建一条连接x与y+n的边,这样的话因为是把一行或者一列删除掉,所以就是求最少有多少个点可以连通整个图,这样就转变为最小顶点覆盖的题目了,根据下面的转换就直接用匈牙利算法的...

    题目地址
    题意:你有一个n*n的棋盘,棋盘上有m个棋子,你有一种技能可以把一行或者一列的棋子全部清掉,问你要把棋盘上所有的棋子清掉最少要使用多少次技能
    思路:你按照当(x,y)上有点的时候建一条连接x与y+n的边,这样的话因为是把一行或者一列删除掉,所以就是求最少有多少个点可以连通整个图,这样就转变为最小顶点覆盖的题目了,根据下面的转换就直接用匈牙利算法的模板就好了。

    最小顶点覆盖数=最大匹配数
    最小路径覆盖=|N|-最大匹配数
    二分图最大独立集=顶点数-二分图最大匹配

    邻接表存储

    #include <iostream>
    #include <cstring>
    #include <string>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <stack>
    #include <cmath>
    #include <cstdio>
    #include <algorithm>
    #define N 1010
    #define LL __int64
    #define inf 0x3f3f3f3f
    #define lson l,mid,ans<<1
    #define rson mid+1,r,ans<<1|1
    #define getMid (l+r)>>1
    #define movel ans<<1
    #define mover ans<<1|1
    using namespace std;
    const LL mod = 1e9 + 7;
    int n, m;
    struct Hungarian {
        vector<int> mapp[N];
        bool vis[N];//是否为匹配点
        int mark[N];//该边与哪个点构成的边为匹配边
        void init() {
            for (int i = 0; i <= n; i++) {
                mapp[i].clear();
            }
            memset(mark, -1, sizeof(mark));
        }
        void add(int a, int b) {
            mapp[a].push_back(b);
            mapp[b].push_back(a);
        }
        bool dfs(int u) {
            for (int i = 0; i < mapp[u].size(); i++) {
                int v = mapp[u][i];
                if (!vis[v]) {
                    vis[v] = true;
                    if (mark[v] == -1 || dfs(mark[v])) {
                        mark[u] = v;
                        mark[v] = u;
                        return true;
                    }
                }
            }
            return false;
        }
        int solve() {
            int sum = 0;
            for (int i = 1; i <= n; i++) {//枚举非匹配点
                if (mark[i] == -1) {
                    memset(vis, false, sizeof(vis));
                    if (dfs(i)) {
                        sum++;//最大匹配的个数
                    }
                }
            }
            return sum;
        }
    }hungarian;
    int main() {
        int a, b;
        cin.sync_with_stdio(false);
        while (cin >> n >> m) {
            hungarian.init();
            for (int i = 0; i < m; i++) {
                cin >> a >> b;
                hungarian.add(a, n + b);
            }
            cout << hungarian.solve() << endl;
        }
        return 0;
    }
    展开全文
  • 最小顶点覆盖:假如选了一个点就相当于覆盖了以它为端点的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。 贪心法思想:贪心法是只顾局部利益,由顶向下,一步一步做出贪心选择。抓住重点看它贪什么。在用...

    最小顶点覆盖:假如选了一个点就相当于覆盖了以它为端点的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。
    贪心法思想:贪心法是只顾局部利益,由顶向下,一步一步做出贪心选择。抓住重点看它贪什么。在用贪心法解决最小顶点覆盖问题中,它贪的是覆盖的边最多的顶点。用邻接矩阵存储无向图,矩阵中每行的和即为顶点的出度。出度最多的顶点即为最优量度标准。
    最小顶点覆盖其一般特性:
    (1)找覆盖边最多的顶点
    (2)已选中的顶点和未选中的顶点
    (3)判断解函数,检查邻接矩阵中元素是否都为0,若不是则继续寻找顶点
    (4)如果已找到的顶点集合没有覆盖所有的边,则该集合是可行的
    (5)选择函数:从未选的顶点集中找到出度最多的顶点
    (6)目标函数:计算顶点个数
    在这里插入图片描述

    这是本次贪心算法选择的一个无向图,用二维数组将其存储

    在这里插入图片描述

    在此代码中,方法wei0()用来判断邻接矩阵中是否每个值都为0,如果不是则继续执行。
    如果是则说明最小顶点都已找到,退出循环。
    方法 findMax()用来找到出度最多的顶点
    方法reFresh()用来刷新邻接矩阵,每次找出一个局部最优解后,将其顶点所对应的行和列元素置为0,进行刷新。
    输出结果:
    在这里插入图片描述

    符合最优解,由局部最优选择得到整体最优选择。`package suanfahomework;

    /**
    *无向图的邻接矩阵每行元素和为这个顶点的出度

    • @author lenovo
      */
      public class TanXin {

      public static void main(String args[]){
      int a[][]={{0,0,1,1,1,0,0},
      {0,0,0,1,0,1,0},
      {1,0,0,1,0,1,0},
      {1,1,1,0,0,0,0},
      {1,0,0,0,0,1,0},
      {0,1,1,0,1,0,1},
      {0,0,0,0,0,0,0},
      };
      int yuansu=0;
      int b[]=new int[a.length];//用来存储邻接矩阵中每个顶点的出度
      int count=0;
      while(wei0(a)) {//邻接矩阵中如果还有元素,就去找候选对象
      yuansu=findMax(a,b);//存储用findMax找出顶点出度最大的点
      System.out.println(“依次取出来的是”+yuansu);
      reFresh(a,yuansu);//对取出来的顶点所在的出入度化为0,得到新的矩阵
      count++;
      }
      System.out.println(“最小顶点覆盖个数为”+count);
      }
      public static boolean wei0(int[][] a){//判断矩阵中元素是否都为0
      for(int i=0;i<a.length;i++){
      for(int j=0;j<a[0].length;j++){
      if(a[i][j]!=0){ return true;
      }
      }
      }return false;
      }
      public static int findMax(int a[][],int b[]){
      int max=0;
      int dingdian=0;
      for(int i=0;i<a.length;i++){
      int sum=0;//计算每行的和
      for(int j=0;j<a[0].length;j++){
      sum+=a[i][j];
      }b[i]=sum;//数组b来存储每行的最大值,最后以判断取出哪一个顶点。
      // System.out.println(b[i]+“aaaa”);
      max=max>sum?max:sum;
      }// System.out.println(max);
      for(int k=0;k<b.length;k++){//用来找到出度最多的顶点,即覆盖边最多的顶点
      if(max==b[k]){ dingdian=k; break;}
      }
      //System.out.println(dingdian);
      return dingdian;
      }
      public static int[][] reFresh(int a[][],int yuansu){
      //将取出的顶点的对应行和列的元素置为0
      for(int i=0;i<a.length;i++){
      a[i][yuansu]=0;
      }
      for(int i=0;i<a[0].length;i++){
      a[yuansu][i]=0;
      }
      return a;
      }
      }`

    展开全文
  • 仅仅用于自己理解,若有共鸣,别太吐槽就行哈~ 首先是匈牙利算法的本质:(图...理解到这里其实才只是个开始,我想解决的是最大匹配与最小顶点覆盖数、最小边覆盖数、最大点独立集之间的关系是怎么得来的。首先是结论
  • #include using namespace std; #define N 10 //是否存在连线 bool edge[N][N]; //配对集,-1表示为配对,其他为配对下标 int y[N]; //配对元素是否已访问 bool visited[N]; void init() { ... edge[0]
  • 最小覆盖= 最大独立集 = |V| - 最大匹配数 这个是在原图是二分图上进行的 最小路径覆盖最小覆盖不同,不要求给的图是二分图,而是要求是N x N的有向图,不能有环,然后根据原图构造二分图,构造方法是将点...
  • 形成顶点集合,利用INM噪声预测软件计算各顶点在每个噪声事件发生时的噪声值,根据单个飞机噪声事件的限值确定各顶点监测到的噪声事件,从而建立最小顶点覆盖模型,然后采用改进的贪心算法求得近似最优解,使得顶点能覆盖...
  • ADT: 1 const int maxn = 150; //表示集合x,y中顶点个数的最大值 2 ... // n,m分别表示 x,y中顶点个数 ...//最大匹配中,与x集合中x[i]匹配的y集合中顶点的索引 6 int cy[maxn]; 7 ...
  • 最小覆盖 = 最大独立集 = |V| - 最大匹配数 这个是在原图是二分图上进行的 最小路径覆盖最小覆盖不同,不要求给的图是二分图,而是要求是N x N的有向图,不能有环,然后根据原图构造二分图,构造方法是将点...
  • HDU1054Strategic Game(最小顶点覆盖数)

    千次阅读 2013-08-18 17:32:07
    我们来先了解一下什么是最小顶点覆盖; 图G的顶点覆盖是一个顶点集合V,使得G中的每一条边都接触V中的至少一个顶点。我们称集合V覆盖了G的边。最小顶点覆盖是用最少的顶点来覆盖所有的边。顶点覆盖数是最小顶点...
  • 6-3 最小顶点覆盖问题 问题描述 给定一个赋权无向图 G=(V,E),每个顶点 v∈V 都有一个权值 w(v)。如果 U⊆VU⊆VU\subseteq V,且对任意(u,v)∈E 有 u∈U 或 v∈U,就称 U 为图 G 的一个顶点覆盖。G 的最小权...
  • poj1325最小顶点覆盖

    2015-08-12 20:06:16
    //因为要完成所有的任务每个任务是一条线 ...//那么就是最小顶点覆盖问题 //注意机器开始就在0上所有跟0的边可以删除 #include #include #include #include using namespace std; #define MAX_N 1010 static ve
  • 树的最小顶点覆盖

    千次阅读 2013-08-26 12:58:12
    最小顶点覆盖问题是算法设计中一个非常著名的NP完全问题,下面给出顶点覆盖问题的描述:   给定一个无向图:G=(V, E)和一个正整数k,判定是否存在一个顶点子集,其中=k,使得对于任意有u∈V' 或 v ∈V' 。如果...
  • 求给定无向图的最小顶点覆盖是一个NP困难问题,只能通过研究此问题的近似算法来求解。本文从基本圈出发,定义了一个次模函数,利用次模函数理论来得到一个最小顶点覆盖问题的近似解,且近似度为1+ In(d-1),其中...
  • 顶点覆盖问题的NP完全证明和近似算法求解》由会员分享,可在线阅读,更多相关《顶点覆盖问题的NP完全证明和近似算法求解(5页珍藏版)》请在人人文库网上搜索。1、顶点覆盖问题的NP完全证明和顶点覆盖优化问题的近似...
  • 竞赛图上的弱顶点覆盖问题是一个NP困难问题,本文先定义了竞赛图上的势加权函数,然后利用分层技术给出了一个求解竞赛图最小顶点覆盖问题的近似算法,并证明了此近似算法的近似度为3。
  • 最小覆盖 = 最大独立集 = |V| - 最大匹配数 这个是在原图是二分图上进行的 最小路径覆盖最小覆盖不同,不要求给的图是二分图,而是要求是N x N的有向图,不能有环,然后根据原图构造二分图,构造方法是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,373
精华内容 3,749
关键字:

最小顶点覆盖算法