找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 17965|回复: 30
收起左侧

[刷题心得] [算法扫盲帖]NP-Hard和NP-Complete 贪心法 递归法 穷举法 迭代法 动态规划

  [复制链接]

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 1-21-2016 02:16 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 3-14-2016 05:29 PM 编辑

本文转载自王振华的日志。
我添加了一些我的消化理解。原文版权属于原作者,我的消化理解版权属于meetqun网。如果有什么理解的不对的或者原文写的就不对的,大牛们请指正啊。
=====================================================
NP-Hard和NP-Complete的区别
对NP-Hard问题和NP-Complete问题的一个直观的理解就是指那些很难(很可能是不可能)找到多项式时间算法【MengMa注:多项式时间就是用一个多项式表示的时间】的问题. 因此一般初学算法的人都会问这样一个问题: NP-Hard和NP-Complete有什么不同? 简单的回答是根据定义, 如果所有NP问题都可以多项式归约【MengMa: 归约是使用解决其它问题的"黑盒"来解决另一个问题. 这个技术我们刷LeetCode会用到。
】到问题A, 那么问题A就是NP-Hard; 如果问题A既是NP-Hard又是NP, 那么它就是NP-Complete. 从定义我们很容易看出, NP-Hard问题类包含了NP-Complete类. 但进一步的我们会问, 是否有属于NP-Hard但不属于NP-Complete的问题呢? 答案是肯定的. 例如停机问题, 也即给出一个程序和输入, 判定它的运行是否会终止. 停机问题是不可判的, 那它当然也不是NP问题. 但对于SAT【MengMa: 下文有写啥是SAT】这样的NP-Complete问题, 却可以多项式归约到停机问题. 因为我们可以构造程序A, 该程序对输入的公式穷举其变量的所有赋值, 如果存在赋值使其为真, 则停机, 否则进入无限循环. 这样, 判断公式是否可满足便转化为判断以公式为输入的程序A是否停机. 所以, 停机问题是NP-Hard而不是NP-Complete.
NP:全称Non-deterministic polynomial time,指可以在多项式时间内可验证问题。经常有人误把NP理解为non-polynomial time。
NP 是 Non-deterministic Polynomial 的缩写,NP 问题通俗来说是其解的正确性能够被很容易检查的问题, 这里"很容易检查"指的是存在一个多项式检查算法.

例如, 著名的推销员旅行问题(Travel Saleman Problem or TSP):假设一个推销员需要从香港出发, 经过广州, 北京, 上海,....., 等 n 个城市, 最后返回香港。 任意两个城市之间都有飞机直达, 但票价不等。现在假设公司只给报销 $C 块钱, 问是否存在一个行程安排,使得他能遍历所有城市,而且总的路费小于 $C ?

推销员旅行问题显然是 NP 的. 因为如果你任意给出一个行程安排, 可以很容易算出旅行总开销. 但是, 要想知道一条总路费小于 $C 的行程是否存在, 在最坏情况下, 必须检查所有可能的旅行安排! 这将是个天文数字.

NP-complete 问题是所有 NP 问题中最难的问题. 它的定义是, 如果你可以找到一个解决某个 NP-complete 问题的多项式算法, 那么所有的 NP 问题都将可以很容易地解决. 【类似于:擒贼先擒王??】

通常证明一个问题 A 是 NP-complete 需要两步, 第一先证明 A 是 NP 的, 即满足容易被检查这个性质; 第二步是构造一个从某个已知的 NP-complete 问题 B 到 A 的多项式变换, 使得如果 B 能够被容易地求解, A 也能被容易地 解决. 这样一来, 我们至少需要知道一个 NP-complete 问题.

第一个 NP complete 问题是 SAT 问题, 由 COOK 在 1971 年证明. SAT 问题指的是, 给定一个包含 n 个布尔变量(只能为真或假) X1, X2, .., Xn 的逻辑析取范式【析取范式见baidu】, 是否存在它们的一个取值组合, 使得该析取范式被满足? 可以用一个具体例子来说明这一问题, 假设你要安排一个 1000 人的晚宴, 每桌 10 人, 共 100 桌. 主人给了你一张纸, 上面写明其中哪些 人因为 江湖恩怨不能坐在同一张桌子上, 问是否存在一个满足所有这些约束条件的晚宴安排? 这个问题显然是 NP 的, 因为如果有人建议一个安排方式, 你可以很容易检查它是否满足所有约束. COOK 证明了这个问题是 NP-complete 的, 即如果你有一个好的方法能解决晚宴安排问题, 那你就能解决所有的 NP 问题.

这听起来很困难, 因为你必须面对所有的 NP 问题, 而且现在你并不知道任何的 NP-complete 问题可以利用.COOK 用非确定性图灵机( Non-deterministic Turing Machine ) 巧妙地解决了这一问题.

正式地, NP 问题是用非确定性图灵机来定义的, 即所有可以被非确定性图灵机在多项式时间内解决的问题. 非确定性图灵机是一个特殊的图灵机, 它的定义抓住了"解容易被检查" 这一特性. 非确定性图灵机有一个"具有魔力的"猜想部件, 只要问题有一个解, 它一定可以猜中. 例如, 只要存在哪怕一个满足约束的晚宴安排方式, 或是一个满足旅行预算的行程安排, 都无法逃过它的法眼, 它可以在瞬间猜中. 在猜出这个解以后,检查确认部分和一台普通的确定性图灵机完全相同,也即是等价于任何一个实际的计算机程序.

COOK 证明了,任意一个非确定性图灵机的计算过程,即先猜想再验证的过程, 都可以被描述成一个 SAT 问题,这个 SAT 问题实际上总结了该非确定性图灵机在计算过程中必须满足的所有约束条件的总和(包括状态转移, 数据读写的方式等等), 这样, 如果你有一个能解决该 SAT 问题的好的算法, 你就可以解决相应的那个非确定性图灵机计算问题, 因为每个 NP 问题都不过是一个非确定性图灵机计算问题, 所以, 如果你可以解决 SAT , 你就可以解决所有 NP 问题. 因此, SAT 是一个 NP-complete 问题.

有了一个 NP-complete 问题, 剩下的就好办了, 我们不用每次都要和非确定性图灵机打交道, 而可以用前面介绍的两步走的方法证明其它的 NP-complete 问题. 迄今为止, 人们已经发现了成千上万的NP-complete 问题, 它们都具有容易被检查的性质, 包括前面介绍的推销员旅行问题. 当然更重要的是, 它们是否也容易被求解, 这就是著名的 P vs NP 的问题.

本帖被以下淘专辑推荐:

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 1-21-2016 02:20 PM | 显示全部楼层
本帖最后由 MengMa 于 10-31-2014 10:23 AM 编辑

回溯法
  回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

        在回溯法中,上述引入的树被称为问题P的状态空间树;树T上任意一个结点被称为问题P的状态结点;树T上的任意一个叶子结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解
  用回溯法解题的一般步骤:
  (1)针对所给问题,定义问题的解空间;(Leetcode里通常是ArrayList<T>,或ArrayList<ArrayList<T>>)
  (2)确定易于搜索的解空间结构;
  (3)以深度优先方式(DFS)搜索解空间,并在搜索过程中用剪枝避免无效搜索。(helper(level n, other params) -> helper(level n +1 , other params))

英文的详细的介绍还可以看这个文章。
http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf

台湾的一个ACM教程
http://acm.nudt.edu.cn/~twcourse/Backtracking.html

MengMa小结:
回溯法是有模板的。大家可以自行建立。
回溯法既可以用递归来实现,也可以用迭代来实现。
回溯法的时间和空间复杂度一般来说会达到指数级别,特别是对于求“全部””所有组合“的一类问题。


下面这段文字比较抽象, 有兴趣的可以研究一下。
  回溯法的一般描述
  可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈Si ,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域,且 |Si| 有限,i=1,2,…,n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
  解问题P的最朴素的方法就是枚举法,即对E中的所有n元组逐一地检测其是否满足D的全部约束,若满足,则为问题P的一个解。但显然,其计算量是相当大的。
  我们发现,对于许多问题,所给定的约束集D具有完备性,即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束意味着j(j<i)元组(x1,x2,…,xj)一定也满足D中仅涉及到x1,x2,…,xj的所有约束,i=1,2,…,n。换句话说,只要存在0≤j≤n-1,使得(x1,x2,…,xj)违反D中仅涉及到x1,x2,…,xj的约束之一,则以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)一定也违反D中仅涉及到x1,x2,…,xi的一个约束,n≥i>j。因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束,就可以肯定,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解,因而就不必去搜索它们、检测它们。回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。
  回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树,它可以这样构造:
  设Si中的元素可排成xi(1) ,xi(2) ,…,xi(mi-1) ,|Si| =mi,i=1,2,…,n。从根开始,让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边,按从左到右的次序,分别带权xi+1(1) ,xi+1(2) ,…,xi+1(mi) ,i=0,1,2,…,n-1。照这种构造方式,E中的一个n元组(x1,x2,…,xn)对应于T中的一个叶子结点,T的根到这个叶子结点的路径上依次的n条边的权分别为x1,x2,…,xn,反之亦然。另外,对于任意的0≤i≤n-1,E中n元组(x1,x2,…,xn)的一个前缀I元组(x1,x2,…,xi)对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为x1,x2,…,xi,反之亦然。特别,E中的任意一个n元组的空前缀(),对应于T的根。
  因而,在E中寻找问题P的一个解等价于在T中搜索一个叶子结点,要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1,x2,…,xn满足约束集D的全部约束。在T中搜索所要求的叶子结点,很自然的一种方式是从根出发,按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组(x1i)、前缀2元组(x1,x2)、…,前缀I元组(x1,x2,…,xi),…,直到i=n为止。
  
回复 支持 反对

使用道具 举报

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 1-21-2016 02:16 PM | 显示全部楼层
本帖最后由 MengMa 于 10-21-2014 01:30 AM 编辑

贪心法
 贪心法(Greedy algorithm)是一种在每一步选择中都采取在当前状态下最好/优的选择,从而希望导致结果是最好/优的算法。比如在旅行推销员问题中,如果旅行员每次都选择最近的城市, 那这就是一种贪心算法。
  贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
  贪心算法与动态规划的不同在于它每对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。【MengMa: 在Best Time to Buy and Sell Stock对这个局部最优和全局最优有撒狗血一样的解释。】
  贪心法可以解决一些最优性问题,如:求图中的最小生成树、求哈夫曼编码……对于其他问题,贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决,那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
  贪心法解题特点
  贪心法有一个共同的点就是在最优求解的过程中都采用一种局部最优策略,把问题范围和规模缩小最后把每一步的结果合并起来得到一个全局最优解。
  贪心法解题的一般步骤
  (1)从问题的某个初始解出发;
  (2)采用循环语句,当可以向求解目标前进一部时,就根据局部最优策略,得到一个部分解,缩小问题的范围和规模;
  (3)将所有部分解综合起来,得到问题最终解。
  该算法存在问题:
  1. 不能保证求得的最后解是最佳的;
  2. 不能用来求最大或最小解问题;
  3. 只能求满足某些约束条件的可行解的范围。


回复 支持 反对

使用道具 举报

91

主题

47

精华

1916

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1916

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 1-21-2016 02:17 PM | 显示全部楼层
本帖最后由 MengMa 于 10-21-2014 01:35 AM 编辑

穷举法
  穷举法,或称为暴力破解法,是一种针对于密码的破译方法,即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码,其可能共有10000种组合,因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码,问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率,有些人辅以字典来缩小密码组合的范围。【MengMa: 实际面试和刷题中:穷举法一般作为男二号出现,用于衬托“优化解法”的伟光正】

破译方法
  穷举法是一种针对于密码的破译方法。这种方法很像数学上的“完全归纳法”并在密码破译方面得到了广泛的应用。简单来说就是将密码进行逐个推算直到找出真正的密码为止。比如一个四位并且全部由数字组成其密码共有10000种组合,也就是说最多我们会尝试10000次才能找到真正的密码。利用这种方法我们可以运用计算机来进行逐个推算,也就是说用我们破解任何一个密码也都只是一个时间问题。
  当然如果破译一个有8位而且有可能拥有大小写数字、字母、以及符号的密码用普通的家用电脑可能会用掉几个月甚至更多的时间去计算,其组合方法可能有几千万亿重种组合。这样长的时间显然是不能接受的。其解决办法就是运用字典,所谓“字典”就是给密码锁定某个范围,比如英文单词以及生日的数字组合等,所有的英文单词不过10万个左右这样可以大大缩小密码范围,很大程度上缩短了破译时间.【MengMa: 带字典的穷举法:hmm...】

字符类型
  字符类型一般可以分为一下5种
  1.数字型0、1、2、...9等(10个)
  2.大写字母A、B、C、...Z等(26个)
  3.小写字母a、b、c、...z等(26个)
  4.特殊字符~、$、#、@、&、*等(33个)一般较少用
  5.用户自定义字符。
  如果一个多位数并且有可能包含以上所有字符的密码的组合方法一定多的惊人,相对来讲破译的时间也会长的没法接受,有时可能会长达数年之久。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表