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