精确算法与参数算法


精确算法与参数算法 肖鸣宇 电子科技大学计算机科学与工程学院 1 * 第二部分 精确算法和参数算法思想在大数 据中的思考 * 第一部分 精确算法和参数算法简单介绍 2 精确算法与参数算法 • 计算机科学中“最核心”的问题是算法 • 计算机以超快速度和超强的记忆力帮人类进 行计算 • 一类重要的计算方式:穷举搜索 • 很多问题容易获得简单的O(2n)时间的穷举 搜索算法 3 精确算法与参数算法 • 事实上,很多问题可能并不存在比穷举搜索 明显更快的算法,O(2n)这样的指数运行时 间可能不能避免。 • 比如说NP难问题。 • 精确算法主要关注在指数运行时间下,怎样 改进运算时间。 如: 2n  1.2n  1.0001n 4 • 独立集:一组顶点两两之间都没有 边 图算法问题在精 确算法中最为重 要的问题举例: 最大独立集问题 旅行商(TSP) 精确算法与参数算法 5 • TSP:访问每个城市一次再回到原 点的最短路径 图算法问题在精 确算法中最为重 要的问题举例: 最大独立集问题 旅行商(TSP) 精确算法与参数算法 6 代表性图问题的最佳精确算法: 最大独立集问题 1.1996n [Xiao, Nagamochi, ISAAC 2013] 旅行商(TSP) (2-a)n [Bjorklund et al., TALG 2012] 3度图:1.2312n P-space [X&N, TAMC 2013] 1.2186n E-space [Bodlaender et al.,ICALP 2013] 4度图:1.6920n [X&N, COCOON 2012] 精确算法与参数算法 7 参数算法:给出某个参数k,设计精确算法使得指数 部分只和参数相关,和问题输入n无关。 精确算法与参数算法 传统精确算法 5nn2 2nn 参数算法 k!n3 2kk2+kn 参数算法的性质:还是指数时间求得最优解,但是 当参数k比较小的时候(哪怕输入n还是很大)问题 可能可以很快被解决。 8 最为重要的参数问题之一: 最小点覆盖问题,参数k为解集的大小。 1.2738k +n1/2m [Chen et.al., TCS 2010] 3度图:1.1616kk + n1/2m [Xiao. COCOON 2010] 现在的算法在n=100000,k=600左右都能几个小时 内完成。 精确算法与参数算法 9 参数算法的思想: 精确算法与参数算法 精确算法 2nn2 2nn 参数算法 4kk2+k2n2 2kk2+kn 参数算法里主要关注指数算法;对于多项式算法的 态度呢? n4 n2k2 10 大数据时代的思考 参数算法里主要关注指数算法;对于多项式算法的 态度呢? n4 n2k2 多项式可解的问题里参数算法真的不重要? 11 大数据时代的思考 多项式算法中的参数算法 n4 n2k2 n2 k3+nk 当参数k和n是同一个级别的时候,算法可能没有改 进,甚至更差,但是当k很小的时候却可能非常有用。 12 大数据时代的思考 参数算法的思想 整个问题 难的部分 参数算法讲究将问题难的和容易的部分区分开来, 将容易的部分用容易的算法对待,难部分用难的算 法对待。 13 大数据时代的思考 • 大数据下,很多问题在平方时间都超时。 • 线性时间能解决的问题极少。 • 剩下难的问题又如何解决? • 参数算法或许能派上用途? 14 大数据时代的思考 • 一个例子:排序问题,运行时间为nlogn. • 如果只是在n个数中找出最大的数,或者最 大的前60个数,或者第50大的数,是否需要 将n个数先排序? • nlogk的算法可以找出前排名前k的数,当k 为常数的时候,算法是线性的。 • 注意在最坏的情况k=n,算法没有改进。 15 大数据时代的思考 • 哪些问题有小参数性质: • 一些例子: VLSI中电路板分割,分割块数不会很大; 某些社交网络中,俱乐部(club)的个数不 会太多; 论文合作者关系网中,一篇论文的合作者一 般不会很多;等等。 • 多观察问题性质,建立参数模型。 16 大数据时代的思考 • 好的参数算法在参数k为常数时是线性时间 的,是否能做到亚线性时间? • 对一般求精确解的问题,亚线性时间算法不 太可能。 • 亚线性时间算法因为没有将所有有效数据读 完,因此一般只是近似算法和随机算法,不 能保证最优解。 17 大数据时代的思考 • 在大数据里,亚线性时间的近似算法和随机 算法已经有一些研究基础。 • 线性或接近线性时间的参数算法研究较少。 • 参数算法中的核心化算法等预处理方法在大 数据中的应用也提得少。 18 大数据时代的思考 • 对大数据里的参数算法和亚线性时间算法有 兴趣? • 欢迎联系 myxiao@gmail.com 19
还剩18页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

bdb4

贡献于2015-02-15

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf