文章目录
  1. 1. 算法(2) 有效问题&困难问题
    1. 1.1. 高效算法
    2. 1.2. 搜索问题
      1. 1.2.1. SAT
      2. 1.2.2. 搜索问题VS优化问题
      3. 1.2.3. 欧拉路径VS汉密尔顿路径
      4. 1.2.4. 最小割
      5. 1.2.5. 线性规划
      6. 1.2.6. 3D-匹配
      7. 1.2.7. 独立集
      8. 1.2.8. 最长路径
      9. 1.2.9. 背包问题

算法(2) 有效问题&困难问题


第二节算法课,内容很广,涉及了很多的问题,但是老师都没有详细展开,这给我课余学习和写博客提供了很多的素材啊!在本科学习中,我们学到的问题基本都是有高效的算法可以解决,但实际上还有很多问题是暂时没有找到高效算法,在多项式时间内无法求解。这堂课就是对这些问题进行了一个总述,为之后将NP问题进行铺垫。

高效算法


本科中我们遇到过下面的问题,他们都已经有高效算法来求解了。

这些问题都可以利用现有的高效算法进行求解,在多项式时间内即可解出。

其实这些问题都可以通过在指数级的范围内搜索得到解决方法。人们在这些指数搜索空间下不断探索得到了许多有效的算法,但是有些搜索问题我们却始终得不到多项式时间内的算法,它们最快的算法也是指数级的。

最小生成树的概念大家都知道,目的是为了得到一颗权值和最小,连通图中所有节点的树,求解MST问题存在有效算法。那么如果我们修改下限制条件,如果这棵树不允许有分支,那么这个问题的求解方法还一样吗?这时这个问题就变成了旅行商问题,它是没有多项式的解法的。

这里我们还要提到(为什么会提到有点忘记了…课件里就是这样的)可满足问题(Satisfiability or SAT)。所谓可满足问题就是说给定一个布尔方程式,是否存在一组解使得这个问题可满足。当然这个布尔方程式需要符合一定条件,是由几组析取(∨)式子通过合取(∧)组合在一起,比如:

(x∨y∨z)(x∨¬y)(y∨¬z)(z∨¬x)(¬x∨¬y∨¬z),其中每个由括号组成的析取式子中省略了∧。

那么可满足也就是是否存在一组(x,y,z)的布尔取值,使得这个布尔方程式的值为1。这个问题最简单的办法就是将所有的布尔取值可能代入到方程式中,这就是上面提到的指数搜索空间,但它的复杂度也是指数级的,那么有没有更好的方法?

这里我们再将问题变得简单点,每个合取范式只能有两个文字(变量或者变量的非),我们把这样的问题称为2-SAT问题。

比如:
(x1∨x2)(¬x1∨x3)(x1∨¬x2)(x3∨x4)(¬x1∨¬x4)

我们可以针对有n个变量和m个合取范式的2-SAT构建一个有向图G(V,E),其中V为2n,E为m。这里需要用到一个性质:对一个析取¬x1∨x3,那么x1->x3(若x1为1的话,那么x3只能取1,才能满足¬x1∨x3)。

那么对上面这个2-SAT方程式得到这样的有向图为:

只要上方的点和下方的点不在同一个强连通分量中,那么这个布尔方程式是可满足的。如果上面的点经过某种路径可以访问到下面的点,也就是在同一个连通分量中,那么这个布尔方程式是不可满足的,存在矛盾的情况。

这样2-SAT问题就有多项式时间的方法了。那么3-SAT呢?或者更高的SAT呢?老师说随着课程的深入,在之后我们可以将大于3的SAT规约到3-SAT,而3-SAT是没有多项式时间的方法的。

搜索问题


SAT


研究者花费了50年来探索SAT问题的有效算法,但是都没有获得成功。不过SAT满足下面两种情况的1个,人们发现了有效的算法:

  1. 2-SAT
  2. 每个析取符合Horn Formula

搜索问题VS优化问题


搜索问题(Decision Problem)和优化问题(Optimization Problem)其实可以相互转化,如何转化呢?

DP->OP,如果OP有解,通过DP来判断一下,即可将OP转化为DP

OP->DP,可以先随意找个大点的数来进行判断,然后二分的来趋向于OP问题的解。

那么为什么要进行转化呢?因为有时候求最优解很困难,这时我们可以转化为判断问题来进行求解

欧拉路径VS汉密尔顿路径


欧拉路径是指在图中找到一条路径,这个路径包含图中所有的边,但不能包含两次。如果是回路的话,就是回到原点。

哈密尔顿路径(也被称为Rudrata)是指在图中找到一条路径,这个路径包含图中所有的点。

这两个问题都非常好,可以单独开一篇来讲。下面的问题单独来讲都可以写一篇博文,老师上课只是稍微的提了下,在以后我会逐步地补上博文的。(内容好广啊…)

最小割


割是指一个边集,这些边从图中挪走可以使图不连通。那么最小割是指给定图和花费b,找到一个割至多包含b条边。

线性规划


线性规划

3D-匹配


3D-匹配

独立集


独立集

最长路径


最长路径

背包问题


背包问题

文章目录
  1. 1. 算法(2) 有效问题&困难问题
    1. 1.1. 高效算法
    2. 1.2. 搜索问题
      1. 1.2.1. SAT
      2. 1.2.2. 搜索问题VS优化问题
      3. 1.2.3. 欧拉路径VS汉密尔顿路径
      4. 1.2.4. 最小割
      5. 1.2.5. 线性规划
      6. 1.2.6. 3D-匹配
      7. 1.2.7. 独立集
      8. 1.2.8. 最长路径
      9. 1.2.9. 背包问题