数据结构与算法分析读书笔记系列10-算法设计技巧

今有作业j₁ ,j₂ ,…,j_N ,已知对应的运行时间分别为t₁ ,t₂ ,…, t_N ,为了把作业平均完成的时间最小化，调度这些作业最好的方式是什么？（假设使用非预占调度（nonpreemptive scheduling））：一旦开始一个作业，就必须把作业运行到完成。

单处理器情况下，按照最短的作业最先进行安排，我们总会产生一个最优的调度。这个结果指出操作系统调度程序为什么一般把优先权赋于那些更短作业的原因。

多处理器情况下，解决多处理器情形的算法是按顺序开始作业，处理器之间轮换分配作业。

如果要将最后完成时间最小化，这个问题实际上是NP-完全的；它恰是背包问题或装箱问题的另一种表述方式，因此将最后完成时间最小化显然比要把平均完成时间最小化困难得多。

应用于文件压缩（file compression）。在现实中，文件可能是相当大的，而在使用频率最大和最小的字符之间通常存在很大的差别。我们希望提供一种更好的编码降低总的所需比特数。一种简单的策略就是让代码的长度从字符到字符是变化不等的，同时保证经常出现的字符代码短。注意，如果所有的字符都以相同的频率出现，那么节省空间是不可能的。

代表字母的二进制代码可以用二叉树来表示，只有在树叶上有数据。每个字符通过从根节点开始用0指示左分支，用1指示右分支以记录路径的方法表示出来。这种数据结构有时叫做trie树。

如果字符都只放在树叶上，那么任何比特序列总能够毫无歧义地译码。这样一种编码叫做前缀码（character code）。相反，如果一个字符放在非树叶节点上，那么就不再能够保证译码没有二义性。

因此，基本的问题在于找到总价值最小的满二叉树，其中所有的字符都位于树叶上。解决如何构造编码树，1952年Huffman给出了一个算法，因此这种编码系统通常称为哈夫曼编码（Huffman code）。

哈夫曼算法 描述：

假设字符的个数为C，算法对一个由数组组成的森林进行。一棵树的权等于它的树叶的频率的和。任意选取最小权的两棵树T₁ 和T₂ ，并任意形成以T₁ 和T₂ 为子树的新树，将这样的过程进行C-1次。在算法的开始，存在C棵单节点树-每个字符一棵。在算法结束时得到一棵树，这棵树就是最优哈夫曼编码树。

可以通过反证法证明，树必定是满的，以及两个频率最小的字符是最深的节点（其它节点可以同样深度）。

该算法是贪婪算法的原因在于，在每一个阶段我们都进行一次合并而没有进行全局的考虑。我们指示选择两棵最小的树。

如果我们依权排序将这些树保存在一个优先队列中，那么，由于元素个数不超过C的优先队列将进行一次BuildHeap、2C-2次DeleteMin和C-2次Insert，因此运行时间为O(ClogC)。使用一个链表简单实现该队列将给出一个O(C²)算法。优先队列实现方法的选择取决于C有多大。在ASCII字符集的典型情况下，C是足够小的，这使得二次的运行时间是可以接收的。

要考虑的两个细节：

1. 压缩文件的开头必须要传送编码信息，因为否则将不可能译码。
2. 该算法是一个两躺扫描算法。第一遍搜素频率数据，第二遍进行编码。

设给定N项物品，大小为s₁, s₂ ,…,s_N ,所有的大小都满足0<s_i <= 1。问题是要把这些物品装到最小数目的箱子中去，已知每个箱子的容量是1个单位。

有两个版本的装箱问题。第一种是联机(on-line)装箱问题。在这种问题中，必须将每一件物品放入一个箱子之后才处理下一件物品。第二种是脱机(off-line)装箱问题。在一个脱机装箱算法中，我们做任何事都需要等到所有的输入数据全被读入之后才进行。

有三种简单的联机算法保证所用的箱子树不多于二倍的最优装箱数。

1. 下项适合算法（next fit）
   • 当处理任何一项物品时，我们检查看它是否还能装进刚刚装进物品的同一个箱子中去。如果能够装进去，那么就把它放入该箱中；否则，就开辟一个新的箱子。
2. 首次适合算法（first fit）
   • 依序扫描这些箱子但把新的一项物品放入足能装下它的第一个箱子中。因此，只有当先前放置物品的结果已经没有再容下当前物品余地的时候，我们才开辟一个新箱子。
3. 最佳适合算法（best fit）
   • 该法不是把一项新物品放入所发现的第一个能够容纳它的箱子，而是放到所有箱子中能够容纳它最满的箱子中。

对于脱机算法，如果我们能够观察全部物品以后再算出答案，那么我们应该会做得更好。

所有联机算法的主要问题在于将大项物品装箱困难，特别是当它们出现在输入的晚期的时候。围绕这个问题的自然方法是将各项物品排序，把最大的物品放在最先。此时我们可以应用首次适合算法或最佳适合算法，分别得到首次适合递减算法（first fit decreasing）和最佳适合递减算法（best fit decreasing）。

输入是平面上的点列P，如果p₁ = (x₁ , y₁)和p₂ = (x₂ , y₂),那么p₁ 和p₂ 间的欧几里德距离为[(x₁ - x₂)² + (y₁ -y₂)²]^(1/2) 。我们需要找出一对最近的点。有可能两个点位于相同位置；在这种情形下这两个点就是最近的，它们的距离为零。解法：对点集按照x坐标排序，这样我们可以画一条想象的垂线，把点集分成两半：P_L 和 P_R 。我们得到的情形就几乎和最大子序列和问题的情形完全相同。最近的一对点或者都在P_L 中，或者都在P_R 中，或者一个在P_L 中而另一个在P_R 中。

选择问题要求我们找出含N个元素的表S中第k个最小的元素。通过把元素排序，选择可以容易地以O(NlogN)最坏情形时间解决。基本的算法是简单的递归策略。设N大于截止点（cutoff point），在截止点后元素将进行简单的排序，v是选出的一个元素，叫做枢纽元（pivot）。其余元素放在两个集合S₁ 和S₂ 中。S₁ 含有那些不大于v的元素，而S₂ 则包含那些不小于v的元素。最后，如果k<=｜S₁｜，那么S中第k个最小的元素可以通过递归计算S₁ 中第k个最小的元素而找到。如果k=｜S₁｜+1，则枢纽元就是第k个最小的元素。否则，在S中的第k个最小的元素是S₂ 中的第（k-｜S₁｜-1）个最小元素。这个算法和快速排序之间的主要区别在于，这里要求解的只有一个子问题而不是两个子问题。

基本枢纽元选择算法如下：

1. 把N个元素分成[N/5]组，忽略（最多4个）剩余的元素。
2. 找出每组的中项，得到[N/5]个中项的表M。
3. 求出M的中项，将其作为枢纽元v返回。

通过术语“五分化中项的中项”（median-of-median-of-five partitioning）给出枢纽元选择法则用于快速选择算法。

计算斐波那契数的自然递归程序是非常低效的。运行时间T（N）>= T（N-1）+T（N-2）。由于T（N）作为斐波那契数满足同样的递归关系并具有同样的初始条件，因此，事实上T（N）是以与斐波那契数相同的速度在增长，也就是说是指数级的。

另一方面，由于计算F_N 所需要的只是F_(N-1) 和F_(N-2) ,因此我们只需要记录最近算出的两个斐波那契数。自然递归程序做了重复的事情。

考虑下列输入：给定一列单次w₁，w₂，…，w_N 和它们出现的固定的概率p₁ ，p₂ ，…，p_N 。问题是要以一种方法在一棵二叉查找树中安放这些单词使得总的期望存放时间最小。

乍看有些奇怪，因为问题看起来很像构造Huffman编码树，正如我们已经看到的，它能够用贪婪算法求解。构造一棵最优二叉查找树更困难，因为数据不只限于出现在树叶上，树还必须满足二叉查找树的性质。

动态规划解由两个观察结论得到。再次假设我们想要把（排序的）一些单词w_Left ，w_(Left+1) ，…，w_(Right-1) ，w_(Right) 放到一棵二叉查找树中。设最优二叉查找树以w_i 作为根，其中Left<=i<=Right。此时左子树必须包含w_Left ，…，w_(i-1)，而右子树必须包含w_(i+1) ，…，w_(Right) （根据二叉查找树的性质）。再有，这两棵子树还必须是最优的，因为否则它们可以用最优子树代替，这将给出w_Left ，…，w_Right 更好的解。

利用动态规划计算有向图G=（V，E）中每一个点对间赋权最短路径的算法。

Dijkstra算法用于单出发点最短路径问题，该算法找出从任意一点s到所有其他顶点的最短路径。这个算法对稠密的图以O（｜V｜²） 时间运行，但是实际上对稀疏的图更快。我们将给出一个短小的算法解决对稠密图的所有点对的问题。这个算法的运行时间为O（｜V｜³） ，它不是对Dijkstra算法｜V｜次迭代的一种渐进改进但对非常稠密的图可能更快，原因是它的循环更紧凑。如果存在一些负的边值但是没有负值圈，那么这个算法也能正确运行；而Dijkstra算法此时是失败的。

Dijkstra算法的一些细节。算法在顶点s开始并分阶段工作。图中的每个顶点最终都要被选作中间顶点。如果当前所选顶点是v，那么对于每个w∊V，置d_w = min(d_w , d_v + c_(v,w))。这个公式是说，从s到w的最佳距离，或者是前面知道的从s到w的距离，或者是从s（最优地）到v然后再直接从v到w的结果。

从v_i 到v_j 只使用v₁ ，v₂ ，…, v_k 作为中间顶点的最短路径或者根本不使用v_k 作为中间顶点的最短路径，或者是由两条路径v_i –> v_k 和 v_k –> v_j 合并而成的最短路径，其中每条路径只使用前k-1个顶点作为中间顶点。得到下面的公式：D_(k,i,j) = min{D_(k-1,i,j),D_(k-1,i,k) + D_(k-1,k,j)}，时间界还是O（｜V｜³）。

因为第k阶段只依赖第（k-1）阶段，所以看来只有两个｜V｜x｜V｜矩阵需要保存。然而，在用k开始或结束的路径上以k作为中间顶点对结果没有改进，除非存在一个负的圈。因此只有一个矩阵是必须的，因为D_(k-1,i,k) = D_(k,i,k) 和D_(k-1,k,j) = D_(k,k,j) ，这意味着右边的项都不改变值且都不需要存储。

该算法可以并行执行，因此这个算法很适合并行计算。

动态规划是强大的算法设计技巧，它给解提供一个起点。它是求解一些更简单的问题的分冶算法的范例，重要的区别在于这些更简单的问题不是原问题的明确的分割。因为子问题反复被求解，所以重要的是将它们的解记录在一个表中而不是重新计算它们。

从某种意义上，如果你看出一个动态规划问题，那么你就看出所有的问题。

随机化的一个用途是以O(logN)期望时间支持查找和插入的数据结构。

最简单的支持查找的可能的数据结构是链表。执行一次查找的时间正比于必须考查的节点个数，这个个数最多是N。

在链表中，每隔一个节点附加一个指针指向它在表中前两个位置的节点。正因为如此，在最坏情形下，最多考查[N/2]+1个节点。

将这种想法扩展，每个序数是4的倍数的节点都有一个指针指向下一个序数是4的倍数的节点。只有[N/4]+2个节点被考查。

有这种跳跃幅度。每个2ⁱ 节点就有一个指针指向下一个2ⁱ 节点。总的指针个数仅仅是加倍，但现在在一次查找中最多考查[logN]个节点。一次查找总的时间消耗为O(logN)，这是因为查找由向前到一个新的节点或者在同一节点下降到低一级的指针组成。在一次查找期间每一步总的时间消耗最多为O(logN)。注意，在这种数据结构中查找基本上是折半查找（binary serch）。

我们将带有k个指针的节点定义为k阶节点（level k node）。当需要插入新元素的时候，我们为它分配一个新的节点。此时，我们必须决定该节点是多少阶的。最容易的方法是抛出一枚硬币直到正面出现并把抛硬币的总次数作为该节点的阶数。

费马小定理 ：如果P是素数，且0<A<P，A^P-1 ≡ 1(mod P)。

存在一些数，对于A的某些选择它们甚至可以骗过算法。一种这样的数集叫做Carmichael数，这些数不是素数，可是对所有与N互素的0<A<N却满足A^N-1 ≡ 1(mod P)。

有一个关于平方探测的定理。这个定理的特殊情况如下：

定理：如果P是素数且0<X<P，那么X² ≡ 1(mod P)仅有的两个解为X=1，P-1。

设给定N个点p₁，p₂，…，p_N，它们位于x轴上。x_i 是p_i 点的x坐标。进一步假设x₁ = 0以及这些点从左到右给出。这N个点确定在每一对点间的N(N-1)/2个（不必是惟一的）形如|x_i - x_j|(i≠j)的距离。显然如果给定点集，那么容易以O(N²)时间构造距离的集合。这个集合将不是排序的，但是如果我们愿意花O(N² logN)时间届整理，那么这些距离也可以被排序。 收费公路问题（turnpike reconstruction problem） 是从这些距离重新构造一个点集。它在物理学和分子生物学中都有应用。

一般的策略是使用一个赋值函数来给一个位置的“好坏”定植。能使计算机获胜的位置可以得到值+1；平局可得到0；使计算机输棋的位置得到值-1.通过考察盘面能够确定这居棋输赢的位置叫做终端位置（terminal position）。

如果一个位置不是终端位置，那么该位置的值通过递归地假设双方最优棋步而确定。这个叫做极小极大（minmax）策略，因为下棋的一方（人）试图使这个位置的值极小化，而另一方（计算机）却要使它的值极大。

对于计算机下棋，一个最重要的因素看来是程序能够向前看的棋步的数目。有时我们称之为层（ply）；它等于递归的深度。为了实现这个功能，需要给予搜索例程一个额外的参数。

人们一般能够取得的最重要的改进称为𝛼-𝛽裁剪（𝛼-𝛽 pruning）。