部落卫队问题.pptVIP

部落卫队问题 数据输入: 由文件input.txt或键盘给出输入数据。第1行2个正整数n、m分别表示有n个居民，m个仇敌。居民编号为1，2，…，n。接下来m行中，每行2个整数u、v，表示居民u和居民v是仇敌 部落卫队问题 输入文件示例： 输出文件示例： 7 10 3 1 2 1 0 1 0 0 0 1 1 4 2 4 2 3 2 5 2 6 3 5 3 6 4 5 5 6 问题分析 首先介绍下最大团问题： 问题描述： 给一个无向图G=(V,E) ，V是顶点集合，E是边集合。然后在这顶点集合中选取几个顶点，这几个顶点任意两个之间都有边在E中。求最多可以选取的顶点个数。这几个顶点就构成一个最大团。 注：最大团可能不唯一。 问题分析 问题分析 算法分析 问题分析 问题分析 * 部落卫队问题 姓名：张思洋 学号：201422172227 专业：软件工程 * 问题描述：原始部落byteland中的居民为了争夺资源，常发生冲突。几乎每个居民都有仇敌。酋长为了组织一个部落卫队，希望从部落居民中选出最多的居民入伍，并保证队伍中任何2个人都不是仇敌 部落卫队问题 算法设计：给定byteland部落中居民间的仇敌关系，计算组成部落卫队的最佳方案。 结果输出；将计算的部落卫队的最佳方案输出到文件output.txt。 文件的第一行是部落卫队的人数；第二行是部落卫队组成Xi 1≤i≤n。Xi=0表示居民i不在卫队中，Xi=1表示居民在卫队中 问题求解思想： 这个问题的本质是一个子集选取问题，就是有集合包括n个元素 {1,2,...,n}选取其中一个子集，这个子集满足某种性质（对于最大团 问题，就是任意两个顶点之间有边求这个子集的最大元素数。每个 元素（对应顶点编号）有2种选择加入或不加入。 所以子集个数为2^n个。 回溯的概念理解： 在包含所有问题的所有解的解空间树中从根节点进行深度优先 有哪些信誉好的足球投注网站空间树中的任一节点的时候，首先判断是否可能包含最优解 如果不包含，就跳过该节点为根的子树的有哪些信誉好的足球投注网站，向其上一层祖先节 点回溯。如果包含，则进入该子树，进行深度优先有哪些信誉好的足球投注网站。 这里用回溯的思想求解 本问题为组织一只队伍保卫部落，并且卫队中互不为仇敌因而实际可考虑在居民中选择一个在最大独立团问题。 构建一个无向图Gv,e,居民为图G的顶点，而居民间关系为图G中的无向边。用1表示两个居民不为仇敌，用0表示两个居民互为仇敌，这样最大独立集问题就成为图G顶点集的子集选取问题。可用子集树表示问题的解空间。设当前考察节点Z位于解空间树的第i层，先考虑从节点i到已选入独立团的所有结点都要相连，然后进入左子树，否则进入右子树。 Thank YOU !