By Zhang, Cheng

更新日期:

文章目录
  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. 背包问题