《毕业设计指导书》由会员分享，可在线阅读，更多相关《毕业设计指导书（4页珍藏版）》请在金锄头文库上搜索。
1、本科毕业设计指导书稠密k子图问题的算法设计与实现一、毕业设计内容1 研究问题和背景介绍本次毕业设计考虑图上的一个最大优化问题，即稠密k子图问题(The Dense k-Subgraph Problem，简称为DkS问题)，对该问题设计并实现求解算法。稠密 k 子图问题实例：无向图G = (V, E),以及一个正整数k。询问：G的一个子图G, G上的顶点数目k,使得G上的边的数目最大。对于无向图，若其任意两个顶点之间都有边，则这样的图成为完全图。因此，一个 n 个顶点的完全图含有n(n-l)/2条边(不考虑重边和自环)。显然，顶点数目为k的子图G， 若含有 k(k-1)/2 条边,则这样的子图是
2、最稠密的。本身是完全图的子图,通常成为“团”。 判断一个图上是否存在大小为k的团，称为团问题，是经典的6个NP难(NP完全)问题 之一GJ79。稠密k子图问题，是团问题的一种变形。长期以来，稠密k子图吸引了算法研 究领域众多研究人员的关注Pap10。经典的团问题已经有很好的理论分析。而对于稠密k子图问题，许多方面的研究目前仍 是未解决的(open)。正的方面，稠密k子图问题现在已知的最好的近似比为。坍田。*】。 负的方面，现在仅证明了稠密k子图问题不存在多项式时间近似方案(PTAS) Kho04。因 此，在正负两种结果之间尚未距离很大的Gap。缩小这一差距是目前算法研究人员关注的热 点问题之一
3、。2 若干基本概念可行解：满足问题要求的解。如，任意的一棵生成树是“最小生成树”问题的一个可 行解。最优解：解的费用是对问题可行解的度量。在所有可行解中，费用最优的一个可行解 称为最优解。优化的目标通常有两个，即求最大或求最小。问题的最优解一般不是唯一的。优化问题：寻求最优解的问题。优化问题(指单目标优化问题)从总体上可分为最小 优化问题和最大优化问题两大类。前者如最短路问题，最小生成树问题等，后者如最大流问 题、最大匹配问题、最大满足问题等。求解优化问题，常用的方法有启发式算法、随机化算法、近似算法等。启发式算法(Heuristics)：通过设计启发策略求解问题。启发策略包括局部搜索、分枝
4、定界、贪心等。近似算法：一个近似算法A,对某个优化问题P在多项式时间内给出一个可行解。衡 量近似算法的最重要指标为近似比(approximation ratio)。假设P为某个最大优化问题，A 为求解P的一个近似算法。算法A的近似比Q指对问题P的任意实例I，A在实例I输出的 可行解的解值A(I)与实例I的最优解值OPT(I)之比的下确界，即a := infiA(I) / OPT(I)。例 如，若处理问题P的算法A的近似比为1/3，则表明对问题P的任意实例I,算法A输出的 解值A(I)至少为最优解值OPT(I)的1/3。显然，由于P为最大优化问题，算法的近似比总是 1o注意，处理最大优化问题的算
5、法的近似比a也定义为a := supIOPT(I) / A(I)o因此，算 法A的近似比为1/3,也可以说成是算法A的近似比为3,两种说法是等价的。设计近似算法有很多途径，但并没有固定的解决问题的“灵丹妙药”近似算法的设计 方法，在很大程度上依赖于它所处理的问题。设计启发式策略也是设计近似算法的一种方法, 但只有对启发式算法给出一个分析能够证明其近似比时，一个启发式算法才称为近似算法。许多优化问题是NP困难的，这意味着在P #NP的假设之下，这些优化问题不存在能 够求得其最优解的多项式时间算法。因此，对于这样的问题，人们寻求设计近似算法。3 稠密 k 子图问题的几种算法本次毕业设计的内容即为稠
6、密k子图问题设计并实现算法。考虑如下几种策略：1) 贪心策略1AITT00：不断地从图上去掉具有最小度的顶点及其关联的边，直到图 上剩下 k 个顶点；2) 贪心策略2FKP01：在图上挑选出顶点度最大的前k/2个顶点。然后再从剩下的顶 点中挑选出和这k/2个顶点拥有邻居数最多的前k/2个顶点。3) 基于行走的策略FKP01。4) 局部搜索策略：设c为一个整数常数。任选图上k个顶点。在这k个顶点之外挑选 c个顶点和k个顶点之内的c个顶点对换，直到这样的对换不能增加所得子图的边数为止。二、基本要求和主要技术指标1 编程环境本毕业设计对编程语言和运行平台不做要求。请选用自己熟悉的一种语言(如Java
7、、 C+等)，选择自己熟悉的一种运行平台(如Windows/Linux/Web等)。2 图的可视化GraphViz是一款很优秀的图的可视化软件。给定图的顶点和边的文本表示(符合一定 格式)，GraphViz软件能够以可视化的方式将图绘制出来。GraphViz软件具有交互式操作窗 口和编程接口，生成的图形可在屏幕上显示或保存成JPG等图像文件。3 程序的输入以GraphViz的格式(gv文件)保存输入图G。要求编写的程序能够读入gv文件并识 别出其中保存的图。4 进一步的要求设计并实现自己想到的任何一种算法。你所设计的算法是否总是比上面提到的已有算法 好？或在什么情况下比已有算法好？5、主要技术
8、指标1) 认真阅读参考文献AITTOO和FKP01,编写程序实现AITT算法和FKP算法。2) 设计并实现局部搜索算法(策略4)。3) 设计并测试至少5个实例，比如稠密图、稀疏图、完全图、随机图(G(n, p)模型等)、 非连通图等,对比这几种算法在这些实例上运行性能的输出结果。4) 对每种算法，构造使该算法输出的解很差的一些实例。三、特色本毕业设计课题是算法设计与分析方面的基础理论课题。课题以求解一个著名的稠密 k 子图问题为目标，使学生掌握问题分析、算法设计、编写程序、调试运行的全过程，启发并 锻炼学生求解困难问题的思维和能力。四、成果形式编写程序实现稠密k-子图问题的几种算法，撰写毕业设
9、计论文。五、成果价值本课题属于基础理论课题，旨在进一步提高学生在计算机科学基础理论方面的能力。参考文献AITT00 Yuichi Asahiro, Kazuo Iwama, Hisao Tamaki, Takeshi Tokuyama. Greedily finding a dense subgraph. Journal of Algorithms, 34(2): 203-221, 2000.BCC+10 Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan. Detectin
10、g high log-densities: an O(n1/4) approximation for densest k-subgraph. In: Proceedings of the 42th Annual ACM Symposium on Theory of Computing (STOC), pages 201-210, 2010.FKP01 Uriel Feige, Guy Kortsarz, David Peleg. The Dense k-Subgraph Problem. Algorithmica 29(3): 410-421, 2001.GJ79 Michael Garey,
11、 David Johnson. Computers and Intractability. W. H. Freeman and Company, 1979.Kho04 Subhash Khot. Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of ComputerScience (FOCS,)pages 136-145, 2004.Pap10 Christos Papadimitriou. http:/www.eecs.berkeley.edu/christos/mads.htm
