回溯

题目：在原始部落中,由于食物缺乏,部落居民经常因为争夺猎物发生冲突,几乎每个居民都 有自己的仇敌。部落酋长为了组织一支保卫部落的卫队,希望从居民中选出最多的居民加入 卫队,并保证卫队中任何两个人都不是仇敌。假设已给定部落中居民间的仇敌关系图,编程计算构建部落护卫队的最佳方案。

输入：n人数（人员编号1~n），m对关系数，接下来m行xi 与yi为仇敌。

示例：

      输入：5 8                 1 2                 1 3                 1 4                 1 5                 2 3                 3 4                 3 5                 4 5

     输出：

国王护卫队最大人数为: 4

国王护卫队成员为: 1 3 4 5

解题思路：回溯法

问题转化： 从无向图G=(V,E)，顶点集由n个节点组成的集合{1,2,...n},  *           选择一部分节点集V',即节点集合的一个子集，此子集中任意两点均有边相连  *           且包含节点个数是节点集合中所有同类子集中节点数目最多的。  *             * 算法设计： 1 定义问题的解空间 {x1,x2,x3...xn}  xi=0/1  *          2 解空间是组织结构： 一棵子集树  *          3 搜索解空间： 约束条件-->判断是否将第t个节点放入团中（只要第t个节点和前t-1个节点中被选中的节点均有边相连，     则x[t]=1)  *                       限界条件-->cn+n-t>bestn(当前已放入团中节点个数+之后可能的所有剩余节点个数约束条件（左）-->限界条件（右）      以及t>n 就记录此时的可行解        

*          团：G的完全子图g是G的团，当且仅当g不包含在更大的完全子图中。

*          最大团：G的所有团中含节点数最多的团。