专注Java领域技术
我们一直在努力

(Java实现) 最大团问题 部落卫队

原文始发于:(Java实现) 最大团问题 部落卫队

首先介绍下最大团问题

问题描述:给一个无向图G=(V,E) ,V是顶点集合,E是边集合。然后在这顶点集合中选取几个顶点,这几

个顶点任意两个之间都有边在E中。求最多可以选取的顶点个数。这几个顶点就构成一个最大团。

注:最大团可能不唯一。

问题求解思想:这个问题的本质是一个子集选取问题,就是有集合包括n个元素{1,2,…,n}选取其中一个子

集,这个子集满足某种性质(对于最大团问题,就是任意两个顶点之间有边),求这个子集的最大元素数。

每个元素(对应顶点编号)有2种选择,加入或不加入。所以子集个数为2^n个。

这里用回溯的思想求解。

回溯的概念如是理解:在包含所有问题的所有解的解空间树中,从根节点进行深度优先搜索,搜索空间树中

的任一节点的时候,首先判断是否可能包含最优解,如果不包含,就跳过改节点为根的子树的搜索,向其上

一层祖先节点回溯。入包含,则进入该子树,进行深度优先搜索。

部落卫队问题描述:

原始部落中的居民为了争夺资源,常发生冲突。几乎每个居民都有仇敌。酋长为了组织一个部落卫队,希望

从部落居民中选出最多的居民入伍,并保证队伍中任何2个人都不是仇敌。

编程任务:

根据给定的居民间的仇敌关系,编程计算出部落卫队的最佳方案。

数据输入:

第1行2个整数n,m表示部落中居民个数,居民中有m个仇敌关系。居民编号1,2,…,n。接下来m行,每行2

个整数u,v表示居民u和v是仇敌。

数据输出:

第1行是最佳方案中部落卫队的人数,第2行是卫队组成xi, 1=<i<=n,

import java.util.Scanner;   public class buluoweidui { 	public static int N=100;          //默认定义数组大小 	static int[][] a=new int[N][N];   //图用邻接矩阵表示 	static int [] x=new int[N];       //是否将第i个节点加入团中 	static int [] bestx=new int[N];   //记录最优解 	static int bestn;                 //记录最优值 	static int cn;                    //当前已放入团中的节点数量 	static int n,m;                   //n为图中节点数  m为图中边数 	 	public static void main(String [] args) { 		Scanner sc=new Scanner(System.in); 		System.out.println("请输入部落的人数n(节点数):"); 		n=sc.nextInt(); 		System.out.println("请输入人与人的友好关系(边数):"); 		m=sc.nextInt(); 		System.out.println("请依次输入有友好关系的两个人(有边相连的两个节点u,v)用空格分开:"); 		int u,v;                      //有边相连的两个节点u,v 		for(int i=1;i<=m;i++) { 			u=sc.nextInt(); 			v=sc.nextInt(); 			a[u][v]=a[v][u]=1;        //边数为1 		} 		 		 		bestn=0;                     //初始最优值为0 		cn=0;                        //初始的团中节点也为0 		backTrack(1);                //从第一个节点进行深度搜索 		System.out.println("国王护卫队的最大人数为:"+bestn); 		System.out.println("国王护卫队的成员:"); 		for(int i=0;i<=n;i++) { 			if(bestx[i]==1)          //打印最优解中记录为1的节点标号 				System.out.print(i+" "); 		} 	}   	/*进行深度搜索*/ 	private static void backTrack(int t) { //t:当前扩展节点在第t层 		if(t>n) {    //达到根节点  记录可行解 并记录此时节点数目 			for(int i=1;i<=n;i++)  				bestx[i]=x[i];  			bestn=cn; 			return; 		} 		 		if(place(t)) {       //判断是否满足约束条件(边是否连通)-->左子树-->把节点加入团中 			x[t]=1;          //左子树 标记为1 			cn++;            //当前节点数+1 			                   			backTrack(t+1);  //继续搜索t+1层 			cn--;            //回溯   加多少就减多少   回退 		} 		 		if(cn+ n-t> bestn) {  //满足限界条件  -->右子数 			x[t]=0; 			backTrack(t+1);   		} 	} 	private static boolean place(int t) {  //判断是否可以把节点t加入团中 		boolean ok=true; 		for(int j=1;j<t;j++) { 			if(x[j]==1 && a[t][j]==1) { 				ok=false; 				break; 			} 		} 		return ok; 	}   }  

赞(0) 打赏
未经允许不得转载:Java小咖秀 » (Java实现) 最大团问题 部落卫队
免责声明

抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专注Java技术 100年

联系我们联系我们

你默默的关注就是最好的打赏~

支付宝扫一扫打赏

微信扫一扫打赏