算法分析与设计实验4：部落卫队问题

1、算法分析与设计课程实验实验题目:部落卫队问题实验题目? 题目描述 原始部落Byteland 中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何两个人都不是仇敌。? 输入说明 第一行给出居民数n和仇敌关系数mi下面的m行给出每一个仇敌关系，仇敌关系u 和v表示居民u和v是仇敌。？? 输出说明 第一行给出部落卫队人数第二行是卫队组成，1 代表对应居民在卫队中，0 代表对应居民不在卫队中？ 实验要求1. 至少运行3 组不同的输入数据；2. 用回溯法或分支限界法求解.实验实现编程语言:Pyth

2、on分支限界法证明把部落的每个人看作是无向图的一个顶点，敌对关系看作是无向图的一条边，因此，该问题可以转化为求一个无向图顶点数最多的独立集。而分支限界法是基于广度优先的搜索算法，根据广度优先算法的最优性可知，分支限界法一定可以得出一个无向图顶点数最多的独立集。实验说明，包括输入、输出、结果截图输入1：部落人数：7敌对关系数：10敌对关系为：1, 2 1,4 2,3 2,4 2,5 2,6 3,5 3,6 4,5 5,6：.二输出1 ：输入2:-RESTART: C: JstrsAdmi请输入部落人数：了清输入存在部对关系数：10请输入蓟对关系双方，用逗号隔开：1.21,42,22,42百2,6

3、3,53,65,6卫队人物为：3卫队成员为；1, 口 L4口，1 1 部落人数：10敌对关系数：12敌对关系为：1,2 2,3 5,9 7,8 6,9 10,15 8,6 4,9 9,10 10,12输出2:-=MM-=- RESLAKT: C: UsersAdjninistratorDesktoi)E 请输入部落入数：15请输入存在敌对美系数：1。请输入敌对关系双方，用逗号犒开1,22. 35, 97,06. 91115丸64, 9乳1010, 12卫队人数为：11卫队成员为:1. 0，1,】，h h L凡工口，L L L L 11输入3:部落人数：10敌对关系数：15 敌对关系为：1,2

4、1,3 1,5 1,8 2,3 2,5 2,6 2,8 3,6 3,8 4,5 4,85,6 5,9 6 , 8- - EESTART: C: UssrsAdmmistr a请输入部蔻人数：1口 请输入存在敌对美系数；15 请输入敌对美系溷方，用返号隔开；235835686CW58698输出3:卫队人数为；6卫队成员为：IX O,11. 0，L h 0, 1, 1? 4.算法复杂性计算过程算法中主要有下面两个循环:it：_t teajnnujn.1 or i ii. range CL Jian+l):bi=l ii.J enery_ifcat x Ei = 1; return 0niuntea

5、iili i in range(1,nan+1):retiara 1If循环有2个分支，for循环复杂度为指数形式，并且循环量为部落的人数n,因此，该算法的复杂度为0(2?)。小结和心得这次的实验算法思想本身不难，主要困难在于限制条件在编程转化为代码 的时候相当困难，好在Python的矩阵以及列表的运算非常简便，因此在 实现的过程中比起其他语言简单许多，除外， Python本身向量索引的值 是从0开始的，这导致在创建列表和矩阵时需要多创建一个向量，最后还 要把n+1维的向量化为n维的源程序清单主程序：def enter_team(x):global enemy_mat,b,manfor i i

6、n range(1,man+1):if bi=1 and enemy_matxi=1:return 0return 1def search(x,team):global num,lif(x=man+1):if teamnum:num=teamfor i in range(1,man+1): li=bireturnif team+man-xnum:returnif enter_team(x)=1:bx=1search(x+1,team+1)bx=0search(x+1,team)man=eval(input(”请输入部落人数：) enemy=eval(input(”请输入存在敌对关系数：) enemy_mat=0*(man+1) for i in range(man+1)l=list(0*(man+1)b=list(0*(man+1)team=list(0*man)print(”请输入敌对关系双方，用逗号隔开:)for i in range(enemy):t,c=eval(input()enemy_mattc=1enemy_matct=1num=0s