算法设计与分析-变治法-171主机测评

预排序

高斯消去法

平衡查找树

AVL树

2-3树

堆和堆排序

霍纳法则和二进制幂

霍纳法则

二进制幂

问题化简

最小公倍数

计算图中路径数量

优化问题的化简

线性规划

简化为图问题

和减治法、分治法类似，变治法也有两个阶段，第一阶段“变”通常会把实例变得更容易求解，第二阶段“治”负责求解问题。根据对问题实例的变换方式，变治法有3种主要的类型：

实例化简：变换为同样问题的一个更简单的或者更方便的实例；

改变表现：变换为同样问题的不同表现；

问题化简：变换为已知解法的另一种问题的实例。

预排序

预排序指的是在解决问题之前先对给定实例进行排序，以提升求解效率的过程。选择排序、冒泡排序、插入排序的效率在最坏和平均情况下都是Θ( $n^{2}$ )，合并排序效率是Θ( nlogn )、快速排序平均效率是Θ(nlogn)，基于比较的排序算法的理论最高效率是Θ( nlogn )。下面给出几个例子：

预排序元素唯一性判断：蛮力求解的最差效率是Θ( $n^{2}$ )，预排序之后，相同元素会相邻。

PresortElementUniqueness(A[0..n-1])
//先对数组排序来解元素唯一性问题
//输入：n个可排序元素构成的一个数组A[0..n-1]
//输出：如果A没有相等的元素，返回true,否则返回false
对数组A排序
for i←0 to n-2 do
if A[i]=A[i+1]
return false
return true

用于排序的时间加上用于检验连续元素的时间就是该算法的总运行时间，前者至少需要nlogn次比较，后者最多n−1次比较，所以排序部分决定了算法的总效率。因此，如果这里使用平方级的排序算法，总效率不升反降，所以一个好的排序算法（例如归并排序）可以将该算法的效率从Θ( $n^{2}$ )提升到Θ( nlogn )。

模式计算：

在给定数字列表中最常出现的一个数字叫模式。蛮力法需要一个辅助数组存储出现的数字和频率，最坏情况下一个列表中没有重复元素，则创建频率列表时的比较次数 $C(n) = \\sum_{i=1}^{n}i-1\\epsilon \\theta \\left ( n^{2} \\right )$ ，除此之外还要遍历频率列表以Θ(n)的效率得到一个最大值，但这不会改变总体Θ( $n^{2}$ )的最差效率。预排序之后，相同元素会相邻。

PresortMode(A[0..n-1]) //先对数组排序来计算它的模式
//输入：可排序元素构成的数组A[0..n-1]
//输出：该数组的模式对数组A排序 i ← 0
//当前一轮从位置i开始
modefrequency ← 0 //目前为止求出的最高频率
while i <= n-1 do
runlength ← 1;
runvalue ← A[i]
while i + runlength <= n-1 and A[i+runlength] = runvalue
runlength ← runlength+1
if runlength > modefrequency modefrequency ← runlength;
modevalue ← runvalue
i ← i+runlength
return modevalue

该算法的运行时间受限于排序时间，因为该算法的剩余部分只需要线性的时间（为什么？

当遍历时，效率仅有 $\\theta \\left ( n \\right )$ 是远小于排序算法的平均效率的。

）。因此，如果使用一个 $\\theta \\left ( nlogn \\right )$ 的排序，这个方法的最差效率的渐进类型就会好于蛮力法的最差效率。

除此之外，查找、最近点对问题、凸包问题中，都有预排序的应用。

高斯消去法

对于一个包含n个方程的n元联立方程组：

$\\begin{cases} & a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=b_{1}\\\\ & a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}=b_{2} \\\\ &. \\\\ & . \\\\ & a_{n1}x_{1}+a_{n2}x_{2}+...+a_{nn}x_{n}=b_{n} \\end{cases}$

当且仅当某一行的系数和另一行不成比例时矩阵存在唯一解（ rank(A)=n ）。如何解这样的方程组？高斯消去法的思路是把n个线性方程构成的n元联立方程组变换为一个等价的方程组（解相同）：

$\\begin{cases} & a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=b_{1}\\\\ & a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}=b_{2} \\\\ &. \\\\ & . \\\\ & a_{n1}x_{1}+a_{n2}x_{2}+...+a_{nn}x_{n}=b_{n} \\end{cases} \\Rightarrow$ $\\begin{cases} & a{}'_{11}x_{1}+a{}'_{12}x_{2}+...+a{}'_{1n}x_{n}=b{}'_{1}\\\\ & a_{22}x_{2}+...+a{}'_{2n}x_{n}=b{}'_{2} \\\\ &. \\\\ & . \\\\ & a{}'_{nn}x_{n}=b{}'_{n} \\end{cases}$

用矩阵的符号，可以写成Ax=b⟹A ′ x=b ′ 。得到上三角矩阵时，可以应用反向替代依次解出x n ,x n−1 ,⋯,x 1 。如何从A得到A ′ ？需要通过矩阵的初等变换来实现：

交换方程组中两个方程的位置；

把一个方程组替换为它的非零倍；

把一个方程替换为它和另一个方程倍数之间的和或差。

也就是线性代数的矩阵初等变换

具体而言，首先以 $a_{11}$ 为主元素，使得第一个方程后面的所有方程中x 1 的系数为0：用第二个方程和第一个方程乘以 $a_{21}$ / $a_{11}$ 之后的差来替代第二个方程；用第三个方程和第一个方程乘以 $a_{31}$ / $a_{11}$ 之后的差来替代第二个方程……以此类推。然后，以 $a{}'_{22}$ 为主元素，乘以 $a_{32}$ / $a_{22}$ ,⋯, $a_{n2}$ / $a_{22}$ 之后与相应方程做差以使得后面的所有方程中 $x_{2}$ 的系数为0。重复以上操作直到最后一个方程中只剩下 $x_{n}$ 。下面给出该过程的伪代码，称为前向消去：

ForwardElimination(A[1..n,1..n], b[1..n])
//对一个方程组的系数矩阵 A 应用高斯消去法
//用该方程组右边的值构成的向量 b 来扩展该矩阵
//输入：矩阵 A[1..n,1..n]和列向量 b[1..n]
//输出：一个代替 A 的上三角形等价矩阵图，相应的右边的值位于第(n+1)列中
for i ← 1 to n do
A[i,n+1] ← b[i] //扩展该矩阵
for i ← 1 to n−1 do
for j ← i+1 to n do
for k ← n+1 downto i do
A[j,k] ← A[j,k]−A[i,k]*A[j,i]//A[i,i]

需要注意的是，这段代码并不总是正确的，例如某一步对角线为0时会导致除0错误，此时应当认为该行不能作为接下来的迭代基点，需要用下面的某行和该行进行交换（前提是方程有唯一解）。与此同时，对角线元素也可能会非常小，导致 A[j,i] / A[i,i] 结果很大，进而导致舍入误差。为了避免这个问题，每次尝试消去一个未知数时，可以选择当前列中最大的系数换到当前行（主元法），它保证比例因子的绝对值永远不会大于1。除此之外，该算法的最内层循环效率特别低。综合以上两个原因，提出如下改进算法：

BetterForwardElimination(A[1..n,1..n], b[1..n])
//用部分选主元法实现高斯消去法
//输入：矩阵 A[1..n,1..n]和列向量 b[1..n]
//输出：一个代替 A 的上三角形等价矩阵，相应的右边的值位于第(n+1)列中
for i ← 1 to n do
A[i,n+1] ← b[i] //把 b 作为最后一列添加到 A 中
for i ← 1 to n−1 do
pivotrow ← i
for j ← i+1 to n do
if |A[j,i]|>|A[pivotrow,i]|
pivotrow ← j
for k ← i to n + 1 do
swap(A[i,k], A[pivotrow,k])
for j ← i+1 to n do
temp ← A[j,i]/A[i,i]
for k ← i to n + 1 do
A[j,k] ← A[j,k]−A[i,k]*temp

该算法实际上是对高斯消元法的二次计算

最内层的乘法操作次数 $C(n) = \\sum_{i=1}^{n-1}\\sum_{j=i+1}^{n}\\sum_{k=i}^{n+1}1=\\frac{n*(n-1)*(2n+5)}{6}\\approx \\frac{1}{3}n^{3}\\epsilon \\Theta (n^{3})$ 。高斯消去法的第二步反向替代法的效率属于Θ( $n^{2}$ )。

高斯消去法有一个有用的副产品，被称为矩阵的LU分解。举例说明：

在用A[1,1]消去A[2,1]和A[3,1]时，分别有乘数2和1/2（此时A[2,2]变为3，A[3,2]变为3/2 ），接着用A[2,2]消去A[3,2]时，有乘数1/2 ，据此可以写出下三角矩阵L，它是由主对角线上的1以及在高斯消去过程中行的乘数所构成的。

对应的上三角矩阵U是消去的结果：

可以看出，LU=A。所以解方程组 Ax =b 等价于解方程组 LUx=b ，若令 Ux=y ，则方程组变为 Ly=b 。值得一提的是，如果已知矩阵的LU分解，则求解方程组的效率是Θ( $n^{2}$ )，但是求解LU分解的效率是Θ( $n^{3}$ )。

除此之外，高斯消去法还可以用来求解矩阵的逆和行列式。

根据矩阵逆的定义 $AA^{-1} = I$ ，设 $X=A^{-1}$ ，即有：

也就是说要求解n个n元方程组，共解出 $n^{2}$ 个未知数。

根据矩阵行列式的定义，如果矩阵的阶数n=1，那么 $detA = a_{11}$ ；如果n>1，那么

$detA = \\sum_{j=1}^{n}s_{j}a_{1j}detA_{j}$ ,其中 $s_{j} = \\begin{cases} & +1,j=2i+1\\\\ & -1,j=2i \\end{cases}$ , $A_{j}$ 是一个n−1阶矩阵，它是从矩阵A中删去了第1行和第j列后得到的。但如果要计算一个大矩阵的行列式，显然该定义没什么用，因为需要计算n!项的和。此时，如果用高斯消去法将一个矩阵转化为上三角矩阵，那么其行列式等于对角线元素乘积，显然效率被缩减到Θ(n)，总效率为Θ( n^3 )。

平衡查找树

二叉查找树节点所包含的元素来自可排序项的集合，每个节点大于它的左子树中的元素，小于它的右子树中的元素。这种将集合变换为一棵二叉查找树节点的元素，是改变表现技术的一个实例。通过这种变换，将查找、插入和删除操作变为对数效率Θ(logn)。但这仅仅在平均情况下成立，在最差情况下，这些操作仍属于Θ(n)。

如何避免出现最坏情况的？有两种方案：

实例化简的类型：把一棵不平衡的二叉查找树转变为平衡的形式。因此，我们说这类树是自平衡的。这个思想的特定实现之间的区别在于它们对平衡的定义是不同的。一棵AVL树要求它的每个节点的左右子树的高度差不能超过1。一棵红黑树能够容忍同一节点的一棵子树的高度是另一棵子树的两倍。此外，如果一棵节点的插入或删除产生了一种不满足平衡要求的树，我们就从一系列称为旋转的特定变换中选择一种，重新构造这棵树，使得这棵树重新满足平衡要求。

改变表现的类型：它允许一棵查找树的节点中不止包含一个元素。这种树的典型代表是2-3树，2-3-4树以及一般和更重要的B树。它们的区别在于查找树的单个节点中能够容纳的元素个数，但它们都达到了很好的平衡。

AVL树

定义：一棵AVL树是一棵二叉查找树，其中每个节点的平衡因子定义为该节点左子树和右子树的高度差，这个平衡因子要么为0，要么为+1或者−1。

如果插入的一个新节点使得一棵AVL树失去了平衡，需要用旋转对这棵树做一个变换。AVL树的旋转，是以某节点为根的子树的一个本地变换，该节点的平衡因子要么变成了+2，要么变成了−2。如果有若干个这样的节点，我们先找出最靠近新插入的叶子的不平衡节点（最小不平衡子树的根），然后旋转以该节点为根的子树。只存在4种类型的旋转，实际上，其中两种又是另外两种的镜像

第一种旋转类型被称为向右单向旋转或者右单转，是在一个新的键插入树的左子女的左子树后发生的。在插入以前，这棵树的根的平衡因子是+1。和右单转相对应的是向左单向旋转或者左单转，它是右单转的镜像，是在一个新的键插入树的右子女的右子树后发生的。在插入以前，这棵树的根的平衡因子是−1。

第二种旋转类型被称为双向左右旋转或者左右双转，它是两个旋转的组合：对根的左子树进行左旋，再对这棵以r为根的新树进行右旋。旋转是在一个新的键插入树的左子女的右子树后发生的。在插入以前，这棵树的根的平衡因子是+1。与之对应的是双向右左旋转或者右左双转，是左右双转的镜像。

下图给出了对给定的一个数字列表5,6,8,3,2,4,7构造AVL树的例子。需要注意，如果有若干个节点的平衡因子为±2，先找出最靠近新插入的叶子的不平衡节点，然后旋转以该节点为根的子树。

就像所有的查找树一样，衡量AVL树效率最关键的特性是树的高度。所有包含n个节点的AVL树的高度h都满足下列不等式： $\\left \\lfloor log_{2}n \\right \\rfloor\\leq h\\leq 1.4405log_{2}(n+2)-1.3277$ 。这个不等式指出，在最差情况下，查找和插入操作的效率属于Θ(logn)。对于一棵针对“随机”键的列表构造的AVL树来说，得到它的平均高度的精确公式被证明是有难度的，但是大量的实验表明，除非n比较小，否则这个高度大概是 $1.01log_{2}n+0.1$ 。因此，在平均情况下，查找一棵AVL树需要的比较次数和用折半查找查找一个有序数组几乎是相同的。在AVL树中，删除的操作相对插入来说要复杂不少，但幸运的是，事实表明，它的效率也是Θ(logn)。然而，这些令人印象深刻的效率特性是有代价的。AVL树的缺点是频繁的旋转、需要维护节点的平衡因子以及总体上的复杂性，尤其是删除操作。这些缺点阻碍了AVL树成为实现字典的标准方法。

2-3树

2-3树是一种可以包含两种类型节点的树：2-节点和3-节点。一个2-节点只包含一个键K和两个子女：左子女作为一棵所有键都小于K的子树的根，而右子女作为一棵所有键都大于K的子树的根(一个2-节点和一棵经典二叉查找树的节点类型是相同的)。一个3-节点包含两个有序的键 K_1 和 K_2 （ K_1 < K_2 ）并且有3个子女。最左边的子女作为键值小于 K_1 的子树的根，中间的子女作为键值位于 K_1 和 K_2 之间的子树的根，最右边的子女作为键值大于 K_2 的子树的根。2-3树的最后一个要求是，树中的所有叶子必须位于同一层，也就是说，一棵2-3树总是高度平衡的：对于每个叶子来说，从树的根到叶子的路径长度都是相同的。为了这个特性，需要允许查找树的一个节点包含不止一个键。

查找从根开始，如果根是一个2-节点，我们就把它当作一个二叉查找树来操作：如果K等于根的键值，算法停止；如果K小于或大于根的键值，我们分别在左子树或右子树中继续查找。如果根是一个3-节点，在不超过两次比较之后，就能知道是停止查找（K等于根的某个键值），还是应该在根的3棵子树的哪一棵中继续查找。

在2-3树中插入一个新键的做法如下：首先，除非空树，否则我们总是把一个新的键K插入一个叶子里（通过查找K来确定一个合适的插入位置）。如果找到的叶子是一个2-节点，根据K是小于还是大于节点中原来的键，我们把K作为第一个键或者第二个键插入。如果叶子是一个3-节点，我们把叶子分裂成2个节点：3个键（2个原来的键和1个新键）中最小的放到第一个叶子中，最大的键放到第二个叶子中，同时中间的键提升到原来叶子的父母中（如果这个叶子恰好是树的根，我们就创建一个新的根来接纳这个中间键）。注意，中间键提升到父母中可能会导致父母的溢出，并且因此会导致沿着该叶子的祖先链条发生多个节点的分裂。下图给出了对给定的一个数字列表9,5,8,3,2,4,7构造2-3树的例子。

一个具有最少节点的高度为h的2-3树是一棵全部由2-节点构成的满树。对于任何n个节点的2-3树， $n\\geq 1+2+...+2^h=2^{h+1}-1$ ，并且因此 $h\\leq log_2(n+1)-1$ 。一个具有最多节点的高度为h的2-3树是一棵全部由3-节点构成的满树，每个节点都包含2个键和3个子女，对于任何n个节点的2-3树， $n\\leq 2*1+2*3+....+2*3^h=3^{h+1}-1$ 并且因此 $h\\geq log_3(n+1)-1$ 。所以高度h的上下界是： $log_3(n+1)-1\\leq h\\leq log_2(n+1)-1$ 。这意味着，无论在最差情况还是在平均情况下，查找、插入和删除的时间效率都属于Θ(logn)。

堆和堆排序

堆是一种灵巧的、部分有序的数据结构，它尤其适合用来实现优先队列。优先队列是元素的一个集合，其中每个元素都包含一个被称为元素优先级的可排序属性。优先队列支持下面的操作：

找出一个具有最高优先级的元素（即最大元素）；

删除一个具有最高优先级的元素；

添加一个元素到集合中。

优先队列也常常出现在一些重要的算法中，例如Prim算法，Dijkstra算法，哈夫曼编码，还有在分支界限中的应用。

堆可以定义为一棵二叉树，树的节点中包含键（每个节点一个键），并且满足下面两个条件：

1.树的形状要求：这棵二叉树是基本完备的（或者称为完全二叉树），这意味着树的每一层都是满的，除了最后一层最右边的元素有可能缺位。

2.父母优势要求：又称为堆特性，每一个节点的键都要大于或等于它子女的键（对于任何叶子我们认为这个条件都是自动满足的）。

在堆中，键值是从上到下排序的。也就是说，在任何从根到某个叶子的路径上，键值的序列是递减的（如果允许相等的键存在，则是非递增的）。然而，键值之间并不存在从左到右的次序。也就是说，在任何同一层的节点之间，不存在任何关系，更一般地来说，在同一节点的左右子树之间也没有任何关系。下面列出堆的重要特性：

只存在一棵n个节点的完全二叉树。它的高度等于⌊ log_2n ⌋。

堆的根总是包含了堆的最大元素。

堆的一个节点以及该节点的子孙也是一个堆。

可以用数组来实现堆，方法是用从上到下、从左到右的方式来记录堆的元素。为了方便起见，可以在这种数组从1到n的位置上存放堆元素，留下H[0]要么让它空着，要么在其中放一个限位器，它的值大于堆中的任何一个元素。在这种表示法中：

父母节点的键将会位于数组的前⌊n/2⌋个位置中，而叶子节点的键将会占据后n−⌊n/2⌋个位置。

在数组中，对于一个位于父母位置i（1≤i≤⌊n/2⌋）的键来说，它的子女将会位于2i和2i+1。相应地，对于一个位于i（2≤i≤n）的键来说，它的父母将会位于⌊i/2⌋。

因此，我们也可以把堆定义为一个数组H[1..n]，其中，数组前半部分中，每个位置i上的元素总是大于等于位置2i和2i+1中的元素，也就是说，

对于i=1,…,⌊n/2⌋，有 $H[i]\\geq max\\left \\{ H[2i],H[2i+1] \\right \\}$

虽然对于大多数处理堆的算法来说，把堆想象成二叉树可以更容易地理解它们所隐含的思想，但对于实际实现来说，使用数组会简单得多，效率也高得多。针对键的给定列表，如何来构造一个堆？

第一种是自底向上堆构造算法：在初始化一棵包含n个节点的完全二叉树时，我们按照给定的顺序来放置键，然后对树进行“堆化”。从最后的父母节点开始，到根为止，该算法检查这些节点的键是否满足父母优势要求。如果该节点不满足，该算法把节点的键K和它子女的键进行交换，然后检查新位置上的键K是不是满足父母优势要求。这个过程一直继续到对K的父母优势要求满足为止（最终它必须满足，因为对于每个叶子中的键来说，这个条件是自动满足的）。对于以当前父母节点为根的子树，在完成它的“堆化”以后，该算法对于该节点的直接前驱（列表中的前一个元素）进行同样的操作。在对树的根完成这种操作以后，该算法就停止了。

HeapBottomUp(H[1..n]) // 用自底向上算法，从给定数组的元素中构造一个堆
// 输入：一个可排序元素的数组 H[1..n]
// 输出：一个堆 H[1..n]
for i ← floor(n/2) downto 1 do
k ← i
v ← H[k]
heap ← false
while not heap and 2*k ≤ n do
j ← 2*k
if j < n // 存在两个子女
if H[j] < H[j+1]
j ← j+1
if v ≥ H[j]
heap ← true
else
H[k] ← H[j]
k ← j
H[k] ← v

在最坏情况下，假设 n=2^k-1 是满树，也就是说，在每一层上，节点的数量都达到了最多。这棵树的高度是 $h=\\left \\lfloor log_2(n) \\right \\rfloor=\\left \\lceil log_2(n+1) \\right \\rceil -1=k-1$ ，且每个位于树的第i层的键都会移动到叶子层中，又因为移动到下一层需要进行两次比较（一次找出较大的子女，另一次确定是否需要交换），位于第i层的键共需要 $2^{(h-i)}$ 次键值比较。综上所述，

$C_{worst} (n)=\\sum_{i=0}^{h-1}2^i*2(h-i)=2\\sum_{i=0}^{h-1}2^i*(h-i)=2(n-log_2(n+1))$

因此，使用了这个自底向上算法，一个规模为n的堆只需要不到2n次比较就能构造完成。

另一种算法称为自顶向下堆构造，通过把新的键连续插入预先构造好的堆，来构造一个新堆。首先，把一个包含键K的新节点附加在当前堆的最后一个叶子后面，然后按照下面的方法把新键送到它的适当位置：拿它和父母的键做比较，如果大于等于它，算法停止（该键已经在一个堆中了）；否则，又把这两个键进行交换，把它的新父母做比较。这个交换一直持续到，它大于它的最后一个父母，或者它到达了树的根为止。

显然，这个插入操作所需的键值比较次数不可能超过堆的高度。因为包含n个节点的堆的高度是 $\\left \\lfloor log_2n \\right \\rfloor$ ，所以插入的时间效率属于O(logn)。

从堆中删除最大的键（根中的键）和插入的方式非常相似：

第一步，将根的键和堆的最后一个键K做交换；

第二步，堆的规模减1；

第三步，重新按照自底向上堆构造算法中的做法，把K沿着树向下筛选，来对堆进行“堆化”。

既然它所需要的键值比较次数不可能超过堆的高度的两倍，所以删除的时间效率也属于O(logn)。

现在我们可以描述堆排序:

第一步：构造堆，即把输入的数组转化为一个堆。

第二步：删除最大键，即对剩下的堆应用n−1次删除根的操作。

最终结果是按照降序删除了该数组的元素。但是对于堆的数组实现来说，一个正在被删除的元素是位于最后的，所以结果数组将恰好是按照升序排列的原始数组。

在把堆的规模从n削减到2的过程中，为了消去根键，所需要的键值比较次数记为C(n)。对于C(n)，有下面的不等式：

$C(n)\\leq 2\\left \\lfloor log_2(n-1) \\right \\rfloor+2\\left \\lfloor log_2(n-2) \\right \\rfloor+......+2\\left \\lfloor log_2(1) \\right \\rfloor\\leq 2\\sum_{i=1}^{n-1}log_2i\\leq 2\\sum_{i=1}^{n-1}log_2(n-1)=2(n-1)log_2(n-1)\\leq 2nlog_2n$

这意味着，堆排序的第二阶段 $C(n)\\epsilon \\Theta (nlogn)$ 。

对于两个阶段的总效率， O(n)+O(nlogn) = O(nlogn) 。一个更详细的分析说明了无论是最差情况还是平均情况，堆排序的效率都属于 $\\Theta (nlogn)$ 。因此，堆排序的时间效率和合并排序的时间效率属于同一类，而且堆排序是在位的，它不需要额外的存储空间。

霍纳法则和二进制幂

已知x，如何求多项式 $p(x)= a_nx^n+a_{n-1}x^{n-1}+.....+a_1x+a_0$ 的值？还有该问题的一个特例，如何计算 x^n 。

霍纳法则

霍纳法则是一个古老的计算多项式的算法，但却十分优雅和高效，其是一个很好的改变表现技术的例子： p(x)=(...((a_nx+a_n-1)x+...)+a_0 。例如，对于多项式 p(x)=2x^4-x^3-3x^2+x-5 ，我们有：

在上式中，可以把x替换为某个值，就是在这个值上对多项式求解的。为了得到上式，没有必要经过一些特定的变换，所需要的仅仅是该多项式系数的一个原始列表。可以方便地用一个两行的表来帮助笔算：第一行包含了该多项式的系数（如果存在等于0的系数，也都包含进来），从最高的 a_n 到最低的 a_0 ；第二行中，除了第一个单元格用来存储 a_n ，其他单元格都将用来存储中间结果。

在做了这样的初始化以后，用第二行的前一个单元格乘以x的值再加上第一行的下一个系数，来算出表格下一个单元格的值。以这种方式算出的最后一个单元格的值，就是该多项式的值。

例如，当x=3时，计算 p(x)=2x^4-x^3-3x^2+x-5 。

所以，p(3)=160。

Horner(P[0..n], x) // 用霍纳法则求一个多项式在一个给定点的值
// 输入：一个n次多项式的系数数组 P[0..n]（从低到高存储），以及一个数字 x
// 输出：多项式在 x 点的值
p ← P[n]
for i ← n-1 downto 0 do
p ← x * p + P[i]
return p

该算法乘法次数和加法次数相同， $M(0)=A(n)=\\sum_{i=0}^{n-1}1=n$ 。

为了搞清楚霍纳法则的效率有多高，我们只要考虑一个n次多项式的第一项： a_nx^n 。用蛮力算法仅仅计算这一项就会需要n次乘法，但霍纳法则除了计算这一项，还计算了其他n−1项，并且仍然只使用了相同的乘法次数。霍纳法则还有一些有用的副产品，该算法在计算p(x)在某些点 x_0 上的值时所产生的中间数字，恰好可以作为p(x)除以 x-x_0 的商的系数，而算法的最后结果，除了等于 p(x_0) 以外，还等于这个除法的余数。因此，对于上面的例子来说， p(x)=2x^4-x^3-3x^2+x-5 除以x−3的商和余数分别为 2x^3+5x^2+18x+55 和160。这种被称为综合除法的除法算法，要比所谓的“长除法”更方便。

二进制幂

当用霍纳法则计算 a^n 时，它退化成了一种对a自乘的蛮力算法，其中还夹杂着一些无用的加法。现在考虑两种计算 a^n 的算法，它们都是基于改变表现思想的。这两种算法都使用了指数n的二进制表示，但一个算法从左到右处理这个二进制串，而另一个从右到左处理。

设n= $b_lb_{l-1}.....b_i...b_0$ 是在二进制系统中，表示一个正整数n的位串。可以通过下面这个多项式的值来计算n的值： p(x)=b_lx_l+.....+b_ix_i+....+b_0 ，其中x=2。例如，如果n=13，它的二进制表示是1101： 13= 1*2^3+1*2^2+0*2^1+1*2^0 。现在让应用霍纳法则来计算这个多项式的值， $a^n=a^{p(2)}=a^{b_l2^l+....+b_i2^i+....b_0}$ 。

但是：

$a^{2p+b_i}=a^{2p}*a^{b_i}=(a^p)^2*a^{b_i}=\\begin{cases} & (a^p)^2 ,b_i=0\\\\ & (a^p)^2*a ,b_i=1 \\end{cases}$

因此，把这个累乘器的值初始化为a之后，可以扫描表示指数的位串，并总是对累乘器的最新值进行平方。而且，如果当前的二进制位是1，还要把存储变量乘以a。这便是用于计算 a^n 的从左至右二进制幂算法。

LeftRightBinaryExponentiation(a, b(n)) // 用从左至右二进制幂算法计算 a^n
// 输入：一个数字 a 和二进制位 b_l, …, b_0 的列表 b(n)，
// 这些位来自于一个正整数 n 的二进制展开式
// 输出：a^n 的值
product ← a
for i ← l-1 downto 0 do
product ← product * product
if b_i = 1
product ← product * a
return product

例如：从左至右二进制幂算法计算 $a^{13}$ ，这里n=13= 1101_2 。

因为该算法在每次重复它唯一循环时都要做一到两次乘法，所以它在计算a n 时，总的乘法次数M(n)有：

$(b-1)\\leq M(n)\\leq 2(b-1)$

其中，b是代表指数n的位串的长度。考虑到 $b-1=\\left \\lfloor log_2n \\right \\rfloor$ ，所以从左至右二进制幂算法的效率是对数级的。因此，该算法比蛮力幂算法具有更好的效率类型，因为蛮力算法总是需要n−1次乘法。

从右至左二进制幂算法使用了相同的二进制多项式p(2)来表示n的值。但它并不像前面那个方法那样对多项式运用霍纳法则，这个算法以一种不同的方式来使用这个多项式：

因此，可以用各项

$a^{b_i2^i}=\\begin{cases} & a^{2^i},b=1\\\\ & 1,b=0 \\end{cases}$

的积来计算 a^n ，也就是连续项 $a^{2^i}$ 的积，其中跳过了那些二进制位b i 为0的项。此外，我们可以只对前面项的计算结果进行平方来计算 $a^{2^i}$ ，因为 $a^{2^i} = (2^{i-1})^2$ 。所以，我们可以从最小值到最大值，计算a的所有这样的乘方（从右到左），但我们只把那些相应二进制位为1的项包括在累乘器中。

RightLeftBinaryExponentiation(a, b(n)) // 用从右至左二进制幂算法计算 a^n
// 输入：一个数字 a 和二进制位 b_l, …, b_0 的列表 b(n)
// 这些位来自于非负整数 n 的二进制展开式
// 输出：a^n 的值 term ← a //
初始化 a^1
if b_0 = 1
product ← a
else product ← 1
for i ← 1 to l do
term ← term * term
if b_i = 1
product ← product * term
return product

还是同样的例子：

显然，和从左至右二进制幂算法的理由相同，该算法的效率也是对数级的。由于这两种二进制幂算法都明确地依赖于指数n的二进制展开式，所以它们的有效性在某种程度上被削弱了。

问题化简

最小公倍数

两个正整数m和n的最小公倍数，记作lcm(m,n)，我们把它定义为能够被m和n整除的最小整数。例如，lcm(24,60)=120，而lcm(11,5)=55。给出了m和n的质因数，我们可以把m和n的所有公共质因数的积乘以m的不在n中的质因数，再乘以n的不在m中的质因数，来求得lcm(m,n)。例如， 24=2×2×2×3、60=2×2×3×5、lcm(24,60)=(2×2×3)×2×5=120。显然该算法缺乏效率，并且需要一个连续质数的列表。通过问题化简，可以设计一个更为有效的计算最小公倍数的算法。因为可以通过欧几里得算法求最大公约数，这是m和n的所有公共质因子的积。不难发现，lcm(m,n)和gcd(m,n)的积把m和n的每一个因子都恰好包含了一次，因此就等于m和n的积。这个观察结果可以得出下面的公式：

其中，gcd(m,n)可以用欧几里得算法非常高效地计算出来。

计算图中路径数量

用数学归纳法不难证明，从图中第i个顶点到第j个顶点之间，长度为k>0的不同路径的数量等于 A^k 的第(i,j)个元素，其中，A是该图的邻接矩阵。因此，我们可以用一个算法来计算图的邻接矩阵的相应幂，得出图中的路径数量。

上图的邻接矩阵A及其平方 A^2 ，分别指出了图中相应的顶点间长度为1和2的路径。具体来说，有三条长度为2的、起止于顶点a的路径：a−b−a，a−c−a和a−d−a。但从a到c，只有一条长度为2的路径：a−d−c。

优化问题的化简

求函数最大值和最小值的问题统称为优化问题。假设现在要求某个函数f(x)的最小值，并且已知一个求函数最大值的算法。我们如何利用后者呢？问题的答案就在这个简单的公式中： minf(x)=-max(-f(x))

换句话说，为了求一个函数的最小值，可以先求它的负函数的最大值。然后，为了得到正确的函数本身的最小值，改变答案的符号。

当然，公式 maxf(x)=-min(-f(x)) 也是成立的。它说明的是，一个最大化问题如何化简为一个等价的最小化问题。求函数极值点的标准微积分过程实际上也是以问题化简为基础的。它要求求出该函数的导数f ′ (x)，然后对方程f ′ (x)=0求解，来求出该函数的临界点。换句话说，它把最优化问题化简为一个求极值点的问题，新问题的主要部分是解方程。

线性规划

许多决策优化问题都可以简化为线性规划问题的一个实例，线性规划问题是一个多变量线性函数的最优化问题，这些变量所要满足的一些约束是以线性等式或线性不等式的形式出现的。

例如，假定有一个大学基金需要进行一亿美元的投资。这笔钱必须分成三种类型的投资：股票、债券和现金。基金经理们对他们的股票、债券和现金给出的预期年收益分别是10%，7%和3%。因为股票比债券的风险更高，该基金的规则要求投资在股票上的资金不能超过债券投资的1/3。此外，现金投资至少应相当于股票和债券投资总额的25%。基金经理们如何投资才能使收益最大化？我们先来为这个问题建立一个数学模型。设x，y和z分别是投资在股票、债券和现金上的金额（以100万美元为单位）。通过使用这些变量，我们可以提出下面这个最优化问题：

使0.10x+0.07y+0.03z最大化；

约束条件：

$\\begin{cases} & x+y+z=100 \\\\ & x\\leq \\frac{1}{3}y \\\\ & z\\geq 0.25(x+y)\\\\ & x\\geq 0,y\\geq 0,z\\geq 0 \\end{cases}$

再例如，如何把背包问题化简为线性规划问题：给定一个承重为W的背包和n个重量为 w_1.....w_n ，价值为 v_1.....v_n 的物品，求这些物品中最有价值的一个子集，并且要能够装到背包中。先考虑该问题的所谓连续或者小数版本，其中，我们可以把给定的任意物品按照任意比例放进背包。设 x_j ，(j=1,⋯,n)是一个变量，代表物品j放在背包中的比例。显然， x_j 必须满足不等式0≤ x_j ≤1。然后，所选物品的总重量可以表示为求和式 $\\sum_{j=i}^{n}w_jx_j$ ，而所选物品的总价值可以表示为求和式 $\\sum_{j=1}^{n}v_jx_j$ 。因此，背包问题的连续版本可以表示为下面这个线性规划问题：

使 $\\sum_{j=1}^{n}v_jx_j$ 最大化；

约束条件： $\\begin{cases} &\\sum_{j=i}^{n}w_jx_j\\leq W \\\\ & 0\\leq x_j\\leq 1,j=1,.....,n \\end{cases}$

在背包问题的所谓离散或者0-1版本中，我们只能，要么拿走一个物品的全部，要么一点都不拿。因此，对于这个版本，我们有下面这个整数线性规划问题：

使 $\\sum_{j=1}^{n}v_jx_j$ 最大化；

约束条件： $\\begin{cases} &\\sum_{j=i}^{n}w_jx_j\\leq W \\\\ & x_j\\epsilon \\left \\{ 0,1 \\right \\},j=1,.....,n \\end{cases}$

简化为图问题

对于许多谜题和游戏来说，图的顶点一般用来表示所讨论问题的可能状态，而边则表示这些状态之间的可能转变。图中的一个顶点代表初始状态，另一个顶点代表问题的目标状态（目标状态顶点可能会有若干个）。这种图被称为状态空间图。因此，这种变换把问题化简为一个求初始状态顶点到目标状态顶点之间路径的问题。

例如，一个农夫在河边带了一只狼、一只羊和一筐白菜。他需要把这三样东西用船带到河的对岸。然而，这艘船只能容下农夫本人和另外一样东西（要么是狼，要么是羊，要么是白菜）。如果农夫不在场的话，狼就会吃掉羊，羊也会吃掉白菜。请为农夫解决这个问题，或者证明它无解。

上图为这个问题的状态空间图。图中顶点上的标记指出了它们所代表的状态：P，w，g和c分别代表农夫、狼、羊和白菜；双直线∣∣表示河。为了简单起见，我们还对边做了标记，用来指出船在每次过河时的负载。就这个图来说，我们关心的是，找到一条从标为Pwgc∣∣的初始状态顶点到标为∣∣Pwgc的结束状态顶点之间的路径。显然图中存在两条这样的简单路径，且长度为7。

算法设计与分析-变治法

预排序

高斯消去法

平衡查找树

AVL树

2-3树

堆和堆排序

霍纳法则和二进制幂

霍纳法则

二进制幂

问题化简

最小公倍数

计算图中路径数量

优化问题的化简

线性规划

简化为图问题

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

预排序

高斯消去法

平衡查找树

AVL树

2-3树

堆和堆排序

霍纳法则和二进制幂

霍纳法则

二进制幂

问题化简

最小公倍数

计算图中路径数量

优化问题的化简

线性规划

简化为图问题

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发