算法分析实践环节习题集-2016

信息工程学院算法分析实践环节习题集-2016 年序号 项目名称任务描述 设计要求 指导教师人数1搜索图中最小控制顶点集合给定一个无向连通子图 G=(V, E)，其中 V 表示图中顶点集合，E 表示边的集合。G 的最小控制顶点集合为 V 的一个子集， S；假设集合 R 表示 V 排除集合 S 后剩余顶点集合，即,= V； 则最小控制顶点集合 S 满足约束条件: R 中任意一个顶点至少与 S 的一个顶点直接相连。 例如下图中红色顶点集合 MDset 表示一个最小控制顶点集合，任意一个绿色的顶点至少与一个红色顶点直接相连。读取文件(网络)，设计算法求解最小控制顶点集合。文件中数据格式如下：A BB C C DB D每一行表示图的两个顶点，且两个顶点之间有一条边。算法：Input：图文件Output:最小控制顶点集合刘全中 12求解最大的双边聚类的子矩阵给定一个 n 行 m 列的矩阵 E，单元格中数值 1 或者 0，例如下图 12 行 12 列的矩阵中，灰色单元格表示 1，白色单元格表示 0。矩阵中一个双边聚类子矩阵(G, C), ,，满足以下条件：(1) 矩阵(G, C)的每个单元格中值都为 1(2) 不存在另一个子矩阵(G, C), 满足下面两个条件：(a) (G, C)中的每一个单元格值都为 1(b) 例如：下图左边的矩阵中其中 2 个双边聚类矩阵分别为(1,3,1,3)， (1,8,2,3,4)算法输入：存放矩阵的文件，例如图所示的文件为：1 1 1 1 1 0 0 0 0 0 0 01 1 0 1 0 0 0 0 0 0 0 01 0 1 0 0 0 0 1 0 0 1 00 0 0 0 1 0 1 0 1 0 1 11 0 0 1 0 0 0 0 0 0 0 00 0 0 0 0 0 1 1 0 1 0 00 0 0 0 0 0 1 0 0 1 1 00 1 1 1 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 0 0 0 00 1 0 0 0 0 0 0 1 1 0 00 1 0 0 1 0 0 0 0 0 0 01 1 0 1 1 0 0 0 0 0 0 0输出所有的双边聚类矩阵刘全中 13图聚类的贪心算法实现一个子图 G = (v, E)的内聚性定义如下：，其中表示子图 G 中边的权重之和， 表示子图 G 与周围顶点连接边的权重之和。注：如果图是无权图，边的权重设置为 1.例如：如下图中，假设子图 G 表示包含 A, B, D,E 四个顶点， G = (A, B, D, E)，则， = 5. 则 f(G) = 10/(10+5).如果一个子图 G 满足内聚性最大时，即局部最优时，则这个子图 G 就是一个聚类。寻找内聚行最大的子图，用贪心算法，分以下三个步骤：(1) 对于 G 的每一个直接邻居顶点 (外围的直接邻居) ，例如 G=A,B,D,E，则 G 的直接邻居顶点为 C, F, G. 找到具有最大值的顶点,如果,则.(2) 对于 G 的每一个内部顶点，找到具有最大值的,其中表示集合 G 排除顶点算法输入：存放图的文件，例如图的文件格式如下：A BB C C DB D每一行表示图的两个顶点，且两个顶点之间有一条边.后的集合；，则.(3)重复步骤 1 和 2，直到集合 G 不发生变化，即收敛，算法结束。算法：Input:图文件Output:图中所有的内聚性最大的 cluster.4最大匹配率算法设计与实现两个图 A 和 B 之间的匹配率计算公式：，其中|A|表示图 A 中顶点个数，表示图 A 和图 B 共同顶点组成的子图。例如下图中 R1和 P1 的匹配率为：(4*4)/(4*5) = 0.8.给定两组子图 R, P, 例如，如下图 R = R1, R2，P=P1, P2, P3, 图中的边上的权值表示两个图之间的匹配率。R 和 P 之间最大匹配率计算方法如下：1. 找出一组边，使得 P 和 R 中的每一个顶点最多出现一条边上，而且边的权重累加和最大。2. 最大匹配率为：第 1 步选择边的权重之和除以 R 中子图的个数例如: 下图中最大匹配率为： (0.8+0.75)/2Input： 两组图Output：输出最大匹配率两个图文件格式如下：A B C D EF G H I每一行表示一个子图5图合并算法的设计与实现给定若干个子图，如果两个子图的重复度大于等于 0.8，需要合并这两个子图。两个子图A 和 B 重复度计算公式为：, 例如：X=A, B, C, D, E, Y = B, C, D,E,则 = (4*4)/(4*5) = 0.8，则子图 x 和 y 需要合并。合并算法有两种方法:方法一、从文件逐行扫描每一个子图，如果后面的子图于前面的子图重复度超过 0.8，则把这两个子图合并为一个新的子图。方法二、把每一个子图抽象为一个顶点，如果两个子图的重复度超过 0.8,则把对应的两个顶点连一条边，这样构造一个新的图。然后从新的图中搜索连通子图，每一个连通子图中所有的顶点进行合并。Input: 子图文件，文件的格式如下：A B C D EF G H I每一行表示一个子图Output，合并后的子图，输出到一个新的文件中。要求：用两种方法分别实现，并比较两种方法的时间复杂度6 简单数据集跳跃显露模式挖掘算法设计与实现跳跃显露模式是指在样本的一个类别上发生次数为 0，在另外一个类别上发生次数大于等于一个支持度计数阈值 的模式。例如下表中数据，假定 。那么在类别为 上的跳跃显露模式有： ，21D,eb,dc利用 Java 语言或者 C 语言实现给定数据集、给定支持度阈值的所有跳跃显露模式。刘全中 17 简单数据集频繁关闭模式挖掘算法设计与实现频繁模式是指在数据集中，出现的次数大于等于给定阈值 的项集。如下表所示的数据集，假设 。频繁模式： ， ， , ., 等2abc,mfca对于模式 ，如果不存在模式 , . 使得包含 的事物和包含 的事物相同。那pppp么 就是一个关闭频繁模式。利用 Java 语言或者 C 语言实现给定数据集、给定支持度阈值的所有的频繁关闭刘全中 1例如，假设 ， 就是一个关闭频繁模式。2,mfca8 工作分配问题设有 n 件工作分配给 n 个人。将工作 i 分配给第 j 个人所需的费用为 cij 。试设计一个算法，为每一个人都分配 1 件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。刘全中 19 无分隔符字典问题设 是 n 个互不相同的符号组成的符号集。)(,.21k是 中字符组成的长度为 k 的字符串全体。1,|,.21kiLikk 是 的 1 个无分隔符字典是指对任意 和 ，则kS Sak.,21 Sbk.,21设计一个算法，对于给定的正整数 n 和 k,编程计算 的最kL大无分隔符字典数据输入：有文件 input.txt 给出输入数据。文件第 1 行有 2个正整数 n 和 k结果输出：刘全中 1S.ba,.b.a,b.a 1-k21k21431k32 无分隔符字典问题要求对给定的 n 和 以及正整数 k,编程计算 的最大无分隔符字典。 kL将计算出的 的最大无分隔kL符字典的元素个数输出到文件output.txt.输入文件示例：2 2输出：2.10 最少个数运算符求解算法的设计与实现关于整数的二元运算#定义为(X # Y) = 十进制整数 X 的各位数字之和 * 十进制整数 Y 的最大数字+Y 的最小数字 例如，(9 # 30)=9*3+0=27.对于给定的十进制 X 和 K,由 X 和#运算可以组成各种不同的表达式.试设计一个算法，计算由 X 和#运算组成的值为 k 的表达式最少需要用多少个 #预算。利用 Java 实现所要求的算法，开发一个 GUI 界面，接受两个数据 X 和 K, 然后在界面上输出需要#的个数。刘全中 111 放行路线选择算法的设计与实现设有 n 个城市(或者景点),今从某市出发遍历各城市，使之旅费最少 (即找出一条旅费最小的路径)输入：各城市间的旅费表有输入文件提供输出：旅费最少的一条路径及总费用。利用 Java, C 实现所要求的算法。时间充分，设计一个图形化界面，读入文件后把 N 个城市的带权(花费) 显示在界面上，经过求解后把旅费最小的路径求出来，并显示在界面上刘全中 112 N 色方柱问题设有 n 个立方体，每个立方体的每一面用红、黄、蓝、绿等 n 种颜色之一染色。要把这 n个立方体叠成一个方形柱体，使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。试设计一个回溯算法，计算出 n 个立方体的一种满足要求的叠置方案。编程任务：对于给定的 n 个立方体以及每个立方体各面的颜色，计算出 n 个立方体的一种叠置方案，使得柱体的 4 个侧面的每一侧均有 n 中不同的颜色。数据输入：由文件 input.txt 给出输入数据。第 1 行有 1 个正整数 n，0n27,表示给定的立方体个数和颜色均为 n。第 2 行是 n 个大写英文字母组成的字符串。该字符串的第 k 个字n0符代表第 k 种颜色。接下来的 n 行中，每行有 6 个数，表示立方体各面的颜色。立方体各面的编号如图 1 所示：TL F R BD刘全中 150 2 1 34图 1图 1 中 F 表示前面，B 表示背面，L 表示左面，R 表示右面，T 表示顶面，D 表示底面。相应地，2 表示前面，3 表示背面，0 表示侧面，1 表示右面，5 表示顶面，4 表示底面。例如，在示例输出文件中，第 3 行的 6 个数 0, 2 , 1, 3, 0, 0 分别表示第 1 个立方体的左面的颜色为 R，右面的颜色为，前面的颜色为，背面的颜色为，底面的颜色为，顶面的颜色为结果输出：将计算的个立方体的一种可行的叠置方案输出到文件 output.txt。每行 6 个字符，表示立方体个面的颜色。如果不存在所要求的叠置方案，输出“No Solution”输入文件示例 输出文件示例Input.txt output.txt4 RBGYRRRGBY YRBGRG0 2 1 3 0 0 BGRBGY3 0 2 1 0 1 GYYRBB2 1 0 2 1 31 3 3 0 2 213 猜比赛名次问题的求解算法设计与实现五个学生 A、B、C、D、E 参加某一项比赛。甲、乙两人在猜测比赛的结果。甲猜的名次顺序为 A、B、C、D、E，结果没有猜中任何一个学生的名次，也没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上