算法定义与设计思想

算法的定义

算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列，满足以下性质：

  1. 输入：有外部提供的量作为算法的输入
  2. 输出：算法产生至少一个量作为输出—算法必须有结果
  3. 确定性：组成算法的每条指令是清晰，无歧义的
  4. 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的

算法设计的重要思想

  1. 边界思想：算法的设计需要首先满足边界条件（一般指输入数据的范围限制，包括一些特殊情况以及异常等，都要考虑在内，以提高算法的健壮性）
  2. 覆盖思想：算法要考虑到问题中所有的可能性，以确保各种情况下算法都能正常工作
  3. 奥卡姆剃刀：如无必要，勿增实体。（优先选择最为简单且基本的解决方案，本质上是复杂度）
  4. 没有免费的午餐：不存在一个通用的最优算法能够在所有可能的问题上表现最佳。（空间和时间的交换？）

问题分类

多项式时间

复杂度的问题规模n出现在底数的位置，就是多项式级复杂度。
而例如O(a^n)和O(n!)等，就是非多项式级复杂度，计算机往往无法接受。

确定性与非确定性算法

确定性算法

设A是求解问题B的一个解决算法，在算法的整个执行过程中，每一步都能得到一个确定的解，这样的算法就是确定性算法。

非确定性算法

设A是求解问题B的一个解决算法，它将问题分解成两部分，分别为猜测阶段和验证阶段，其中

  1. 猜测阶段：在这个阶段，对问题的一个特定的输入实例x产生一个任意字符串y，在算法的每一次运行时，y的值可能不同，因此，猜测以一种非确定的形式工作。
  2. 验证阶段：在这个阶段，用一个确定性算法（有限时间内）验证。
    1. 检查在猜测阶段产生的y是否是合适的形式，如果不是，则算法停下来并得到no；
    2. 如果y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。它是验证所猜测的解的正确性。

规约/约化

问题A可以约化为问题B，称为“问题A可规约为问题B”。

可以理解为问题B的解一定就是问题A的解，因此解决A不会难于解决B。由此可知问题B的时间复杂度一定 >= 问题A。

问题分类

  1. P类问题：能在多项式时间内可解的问题。
  2. NP类问题：在多项式时间内“可验证”的问题。
    也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的，而对其某一个解的验证则能够在多项式时间内完成。P类问题属于NP问题，但NP类问题不一定属于P类问题。
  3. NPC问题：存在这样一个NP问题，所有的NP问题都可以约化成它。
    换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：
    1. 它是一个NP问题
    2. 所有NP问题都能规约到它
  4. NP-hard问题：NP-hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-hard问题要比 NPC问题的范围广，NP-hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是他不一定是一个NP问题。NP-hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

通常的计算机，都是确定性（deterministic）的。它们在同一个时刻，只有一种行为。如果用程序来表示，那么它们遇到一个条件判断（分支）的时候，只能一次探索其中一条路径。
P = “确定性计算机”能够在“多项式时间”解决的所有问题
NP = “非确定性计算机”能够在“多项式时间”解决的所有问题

五大算法

包括分治算法、动态规划算法、贪心算法、回溯算法、分支界限法。

注：本文参考自课程ppt