To All Of You：

一个人在接受科技教育时能得到的最珍贵的收获是能够终身受用的通用智能工具。

在讨论算法的书籍中，一般会采用两种方案中的一种：

1.第一种方案是按照问题的类型对算法进行分类。这类教材安排了不同的章节分别讨论排序，查找，图等算法。这种做法的优点是，对于解决同一问题的不同算法，它能够立即比较这些算法的效率。其缺点在于，由于过于强调问题的类型，它忽略了对算法设计技术的讨论。

2.第二种方案围绕着算法设计技术来组织章节。在这种结构中，即使算法来自于不同的计算领域，如果它们采用相同的设计技术，就会被编成一组。

第一章：绪论

1.1什么是算法

为了阐明算法的概念，本节将以三种方法为例来解决同一个问题，即计算两个整数的最大公约数。这些例子会帮助我们阐明以下要点：

1.算法的每一个步骤都必须没有歧义，不能有半点儿含糊
2.必须认真确定算法所处理的输入的值域
3.同一算法可以用几种不同的形式来描述
4.同一问题，可能存在几种不同的算法
5.针对同一问题的算法可能基于完全不同的解题思路，而且解题速度也会有显著不同

用于计算gcd(m,n)的欧几里得算法：
1.如果n=0，返回m的值作为结果，同时过程结束；否则进入第二步
2.m除以n，将余数赋给r
3.将n的值赋给m，将r的值赋给n，返回第一步

1.2算法问题求解基础

对于一些算法，证明正确是非常简单的，对于一些复杂的算法，一般采用的正确方法是数学归纳法。

我们希望算法具有一些好的特性：

1.正确性
2.时间效率
3.空间效率
4.简单性
5.一般性

一般性包含两层意思：1.算法所解决问题的一般性2.算法所接受输入的一般性。

第四章：减治法

减治（decrease-and-conquer）技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。一旦建立了这种关系，我们既可以从顶到下（递归），也可以从底向上（迭代）来运用这种关系。

减治法有三种主要的变化形式：

1.减去一个常量
2.减去一个常量因子
3.减去的规模是可变的

在减常量（decrease-by-a-constant）变化形式中，每次迭代总是从实例中减去一个相同的常量。一般来说，这个常量等于1（T(n)变为T(n-1)），但减其他的常量也偶尔出现。

减常因子（decrease-by-a-constant-factor）意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子。在大多数情况下，常数因子等于2（T(n)变为T(N/2)）。

减可变规模（variable-size-decrease）变化形式中，每次迭代时，规模减小的模式是不同的。例如：gcd(m,n) = gcd(n,m mod n)。

4.1插入排序

如何利用减一技术对一个数组排序？假设前面n-1个数已经有序，然后构造出n个有序的数。插入排序啊！

4.2拓扑排序

复习图：邻接矩阵和邻接链表仍然是两种表示图的主要手段。

用这两种方法表示时，无向图和有向图只有两个显著的差异：

1.有向图的邻接矩阵不一定表现出对称性
2.有向图的一条边在图的邻接表中只有一个相应的节点（不是两个）

一个五门必修课的集合{c1,c2,c3,c4,c5}，学生必须在某个阶段修完这几门课程。可以按照任何次序学习这些课程，只要满足下面的条件：c1,c2没有任何条件，修完c1和c2才能修c3，修改c3才能修c4，而修完c3和c4才能修c5.应该按照什么顺序来学习这些课程呢？

这种状况可以用一个图来建模，它的节点代表课程，有向边表示先决条件。如图：

问题转换：就上面的问题，其实是说，是否可以按照一种序列列出它的顶点，使得对于图中每一条边来说，边的初始起点总是排在边的结束顶点之前。这个问题叫拓扑排序！

为了使拓扑排序成为可能，无环有向图不仅是必要条件，而且是充分条件。也就是说，如果一个图没有回路，对它来说，拓扑排序是有解的。

1.第一种算法是深度优先查找的一个简单应用：执行一次DFS遍历，并记住顶点变成死端（即退出）的顺序。将该次序反过来就得到拓扑排序的一个解，当然，在拓扑排序时不能遇到回边。

这个算法为什么有效呢？当一个顶点v退出DFS栈时，在比v更早出栈的顶点中，不可能存在顶点u拥有一条从u到v的边（否则，(u,v)是一条回边）。所以，在退栈的队列中，任何这样的顶点u都会排在v的后面，并且在逆序队列中会排在v的前面。

2.第二种算法基于减一技术的一个直接实现：不断地做这样一件事，在余下的有向图中求出一个源（source），它是一个没有输入边的顶点，然后把它和所有从它出发的边都删除。（如果有多个源，可以任意选择一个。如果这样的源不存在。算法停止，因为该问题无解）。顶点被删除的次序就是拓扑排序问题的一个解。

4.3生成组合对象的算法

组合对象中最重要的类型就是排列，组合和给定集合的子集。

1.生成排列：

通过使用移动元素（务必了解这个概念）这个概念，我们可以给出所谓的Johnson-Trotter算法的描述，它算是用来生成排列最有效的方法了。伪代码如下：

算法  Johnson-Trotter(n)
    //实现用来生成排列的Johnson-Trotter算法
    //输入：一个正整数
    //输出：{1,2,...,n}的所有排列的列表

    将第一个排列初始化为1,2,...,n（头部箭头都向左）
    while 存在一个移动元素 do
    求最大的移动元素k
    把k和它箭头指向的相邻元素互换
    调转所有大于k的元素的方向
    将新排列添加到列表中

有人说Johnson-Trotter算法生成的排列的次序不是非常自然。例如排列n,n-1,…1的自然位置应该是列表的最后一个。将排列按照升序排列，这样被称为字典序。下面是实现字典序的伪代码：

算法  LexicographicPermute(n)
    //以字典序生成排列
    //输入：一个正整数n
    //输出：{1,2,...,n}的所有排列的列表

    初始化第一个排列为1,2,...,n
    while 最后一个排列有两个连续升序的元素 do
    找出使得a(i)<a(i+1)的最大的i //a(i+1)>a(i+2)>...>a(n)
    找到使得a(i)<a(j)的最大索引j //j>=i+1,因为a(i)<a(i+1)
    交换a(i)和a(j) //a(i+1)到a(n)仍保持降序
    将a(i+1)到a(n)的元素反序
    将这个新排列添加到列表中

2.生成子集：

有一个直接解决该问题的简洁方法，它是基于这样一种关系：n个元素集合A={a1,a2,…,an}的所有2的n次方个子集和长度为n的所有2的n次方个位串之间的一一对应关系。

下面是递归生成二进制反射格雷码的伪代码：

算法 BRGC(n)
    //递归生成n位的二进制反射格雷码
    //输入：一个正整数n
    //输出：所有长度为n的格雷码位串列表
    if n=1 ,表L包含位串0和1
    else 调用BRGC(n-1)生成长度为n-1的位串列表L1
    把表L1倒序后复制给表L2
    把0加到L1中每个位串的前面
    把1加到L2中每个位串的前面
    把表L2添加到表L1后面得到表L
return L

要注意的是，二进制反射格雷码是循环的：它的最后一个位串与第一个位串只相差一位；对于中间的生成码，之间也只相差一位。

4.4减常因子算法

1.折半查找
2.假币问题
3.俄式乘法
该乘法的思想：

//n为偶数
n*m = (n/2)*2m
//n为奇数
n*m = (n-1)/2*2m+m

这样递归的调用就可以算出结果。该算法只包括折半，加倍和相加这几个简单的操作。使用移位就可以完成二进制数的折半和加倍，在机器层次上，这些都属于最基本的操作。

4.5减可变规模算法

1.计算中值和选择问题

选择问题是求一个n个数列表的第k个最小元素的问题。这个数字被成为第k个顺序统计量。对于k=1或k=n，问题退化为最小和最大元素问题。

显然，为了找出第k个最小的元素，我们可以先对数组排序，然后再从输出中找出第k个元素。但是，杀鸡需用牛刀？只是找第k个最小元素，我们并不需要排序（除非查询的次数很多，并且每次k都不一样，但那是属于预排序优化的内容了，后面会讲），我们可以采用划分（partitioning）的思路，使左边包含所有小于p的元素，紧接着是中轴（pivot）p本身，再接着是所有大于或等于p的元素。中轴的选择可以随机选，也可以简单指定为第一个元素。实现划分的一种算法的伪代码：

算法 LomutoPartition(A[l,...,r])
    //采用Lomuto算法，用第一个元素作为中轴对子数组进行划分
    //输入：数组A[0,...,n]的一个子数组A[l,...,r]，它由左右的索引l和r(l<=r)定义
    //输出：A[l,...,r]的划分和中轴的新位置
    p<-A[l] //中轴元素
    s<-l
    for i<-l+1 to r do
        if(A[i]<p){
        s<-s+1；swap[A[s],A[i]]
        }
    swap[A[l],A[s]]
    return s;

用索引s来记录for循环到目前为止，最后一个小于p的元素的位置，那么s+1就是大于或等于p的第一个位置，如果遇到小于p的元素，每次与之交换。

那么我们如何来寻找第k个最小元素呢？先划分，如果s>k-1，就是数组左边部分第k小的元素，如果s

算法 Quickselect(A[l,...,r],k)
    //用基于划分的递归算法解决选择问题
    //输入：可排序数组A[l,...,r]和整数k（1<=k<=r-l+1）
    //输出：A[l,...,r]中第k小元素的值
    s<-LomutoPartition(A[l,...,r])//或者另一个划分算法
    if s=l+k-1 return A[s]
    else if s>l+k-1 Quickselect(A[l,...,s-1],k)
    else Quickselect(A[s+1,...,r],l+k-1-s)  

快速选择的效率如何？对一个n元素数组进行划分总是要n-1次键值比较。如果不需要更多迭代就能得到分割位置而使问题得解，在这种最好情况下，Cost(best) = n-1 = O(n)。但是，算法也可以产生极度不平衡的划分，这个划分一部分为空，另一部分包含n-1个元素，这意味着在最坏情况下，Cost(worst) = (n-1)+(n-2)+…+1 = (n-1)*n/2 = O(n^2)。

2.二叉查找树的查找和插入

第五章：分治法

分治法是按照以下方案工作的：

1.将一个问题划分为同一类型的若干子问题，子问题最好规模相同
2.对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）
3.有必要的话，合并这些子问题的解，以得到原始问题的答案

分治法对于并行计算是非常理想的，因为各个子问题都可以由各自的CPU同时计算。

主定理：

假设有递推关系式：T(n) = aT(n/b)+f(n),其中a>=1,b>1,f(n) = O(n^d)。其中，n为问题规模，a为递推的子问题数量，n/b为每个子问题的规模（假设每个子问题的规模基本一样），f(n)为递推以外进行的计算工作。

那么：T(n) =

1.O(n^d)，当a小于b^d时
2.O(n^d*log(n))，当a等于b^d时
3.O(n^(logb(a)))，当a大于b^d时

例如二叉树遍历中，T(n) = 2T(n/2)+1,a=2,b=2,d=0,属于情况三，那么T(n) = O(n)。
例如归并排序中，T(n) = 2T(n/2)+O(n),a=2,b=2,d=1,属于情况二，那么T(n) = O(nlogn)。

参考主定理-维基百科。

5.1合并排序

合并排序太熟了，可以参考Merge Sort。

合并排序的效率如何呢？合并排序的递推关系式为：当n>1时，C(n)=2C(n/2)+Cmerge(n),C(1)=0。
最坏情况下，Cmerge(n)=n-1
由主定理可以得到最坏情况下：Cworst(n)=O(nlogn)

合并排序在最坏情况下的键值比较次数十分接近基于比较的排序算法在理论上能够达到的最少次数。相比于两个高级排序算法-快速排序和堆排序，合并排序的一个显著优点在于其稳定性。合并排序的主要缺点就是该算法需要线性的额外空间。

合并排序有两类主要的变化形式（努力变得更好）：

1.算法可以自下而上合并数组的一个个元素对，然后再合并这些有序对，这就避免了使用堆栈处理递归调用时的时间和空间开销。

2.可以将数组划分为待排序的多个部分，再对他们递归进行排序，最后将其合并在一起。，这个方案尤其适合对存放在二级存储空间的文件进行排序，也被称为多路合并排序。（想想一个含有20亿个数的文件，如何排序嘛，用这个方法还是比较可以的）

5.2快速排序

不像合并排序是按照元素在数组中的位置对它们进行划分，快速排序按照元素的值对它们进行划分。注意它与合并排序的不同之处：

在合并排序算法中，将问题划分为两个子问题是很快的，算法的主要工作在于合并子问题的解。
在快速排序算法中，算法的主要工作在于划分阶段，而不需要再去合并子问题的解。

快速排序的伪代码：

算法 Quicksort(A[l,...,r])
    //用Quicksort对数组排序
    //输入：数组A[0,...,n-1]的一个子数组A[l,...,r]，它由左右的索引l和r(l<=r)定义
    //输出：非降序的子数组A[l,...,r]
    if l<r
        s<-Partition(A[l,...,r]) //s是分裂位置
        Quicksort(A[l,...,s-1])
        Quicksort(A[s+1,...,r])

对于划分算法，可以使用4.5节讨论的Lomuto划分。

快速排序在平均情况下，仅比最优情况多执行39%的比较操作。此外，它的最内层循环效率非常高，使得在处理随机排列的数组时，我们的速度要比合并排序快（对于堆排序也是如此）。

一些快速排序的改进：

1.更好的中轴选择方法。例如随机快速排序，使用随机元素作为中轴；三平均划分法，以最左边，最右边，中间元素的中位数最为中轴。

2.在数组足够小时（对大多数计算机而言，元素数为5-15），改用插入排序方法。或者根本就不再对小数组进行排序，而是在快速排序结束后再使用插入排序对整个近似有序的数组进行排序。

3.一些划分方法的改进。例如三路划分，将数组分为三段，每段元素分别为小于，等于，大于中轴的元素。

二叉树遍历及其相关特性

分治思想：

算法 Height(T)
    //递归计算二叉树的高度
    //输入：一颗二叉树T
    //输出：T的高度
    if T=null return -1
    else return max{Height(T(left),Height(Tright))}+1

对于A(n(T))，我们有下面的递推式：当n(T)>0时，A(n(T))=A(n(Tleft))+A(n(Tright))+1,A(0)=0。

在上面的算法中，加法运算并不是该算法中执行最频繁的操作。检查树是否为空，才是该算法的典型操作。例如，对于一颗单节点的树来说，执行比较T=null的次数和加法运算的次数分别为3和1。

很容易发现，对于扩展树的每一个内部节点，Height算法都要执行一次加法运算，而且不论对外部节点还是内部节点，该算法都要执行因此比较运算。

对于任何非空的完全二叉树，设n和x分别表示父母节点和叶节点的数量。
有下列的关系：2n+1=x+n==>x=n+1。

回到Height算法中，检查树是否为空的比较操作为2n+1，加法操作为n。

显然，并不是所有关于二叉树的算法都需要遍历左右两颗子树。例如，二叉树的查找，插入，和删除操作只需要遍历两颗子树中的一颗。因此，我们并没有将它们作为分治技术的应用，而是作为减可变规模技术的一个例子。

一个关于递推式解复杂度的技巧：

反向替换法：
递推式为：当n>1时，M(n)=3M(n/2),M(1)=1，当n=2^k时，M(2^k)=3M(2^(k-1))=…=3^k。因为k=log2(n),所以，M(n)=3^(log2(n))=n^(log2(3))。

第六章：变治法

根据我们对问题实例的变换方式，变治思想有3种主要的类型：

1.变换为同样问题的一个更简单或者更方便的实例—称之为实例化简。
2.变换为同样实例的不同表现—改变表现。
3.变换为另一个问题的实例，这种问题的算法是已知的—称之为问题化简。

6.1预排序

实际上，对于排序算法的兴趣很大程度上是因为这样的一个事实：如果列表时有序的，许多关于列表的问题更容易求解。

合并排序和快速排序，前者总是属于O（nlogn），后者在平均情况下也是O（nlogn），但在最坏情况下是平方级的。

当我们要在同一个列表中进行多次查找（在非排序下很耗时的操作），在预排序上花费的时间应该是值得的。

6.3平衡查找树

二叉查找树—一种实现字典的重要数据结构。二叉树节点所包含的元素来自可排序项的集合，每个节点一个元素，使得所有左子树中的元素都小于树根节点的元素，而所有右子树中的元素都大于树根节点的元素。

请注意，把一个集合变换为一颗二叉查找树，是改变表现技术的一个实例。这种变换与字典的简单实现（例如数组）相比，有什么优势呢？我们赢得了查找，插入和删除的时间效率，这些都属于O(logn)。但这仅仅在平均情况下成立，在最差情况下，这些操作属于O(n)，因为这种树可能会退化成一种严重不平衡的树，树的高度等于n-1。所以，还要时刻地保持平衡。

为了既保留二叉查找树的好特性，有能够避免它退化成最差情况，主流的有两种方案：

1.第一种属于实例化简的类型：把一颗不平衡的二叉查找树转变为平衡的形式。一颗AVL树要求它的每个节点的左右子树高度差不能超过1。一颗红黑树能够容忍同一节点的一颗子树的高度是另一颗子树的两倍。如果一个节点的插入或者删除产生了一颗违背评分要求的树，我们从一系列称为旋转的特定变换中选择一种，重新构造这颗树，使得这棵树满足平衡的要求。

2.第二种属于改变表现的类型：它允许一颗查找树的单个节点中不止包含一个元素。这种树的特例是2-3树，2-3-4树，以及更一般和更重要的B树。它们的区别在于查找树的单个节点中能够容纳的元素个数。

AVL树：

定义：一颗AVL树是一颗二叉查找树，其中每个节点的平衡因子（balance factor）定义为该节点左子树和右子树的高度差，等于0，-1或1。一颗空树的高度定义为-1。

AVL树的旋转，是以某节点为根的子树的一个本地变换，该节点的平衡要么变成了+2，要么变成了-2。如果有若干个这样的节点，我们先找出最靠近新插入的叶子的不平衡节点，然后旋转以该节点为根的子树。只存在4种类型的旋转，实际上，其中两种又是另外两种的镜像。分别为：1.右单转2.左单转3.左右双转4.右左双转。

请注意，虽然旋转可以在常量时间内完成，但它并不是无足轻重的变换。

AVL树的效率如何？就像所有的查找树一样，最关键的特性是树的高度。

AVL树的缺点是频繁的旋转，需要维护树的节点的平衡以及总体上的复杂性，尤其是删除操作。这些缺点阻碍了AVL树成为实现字典的标准结构（总之一句话，AVL条件太苛刻）。

2-3树：

6.4堆和堆排序

它尤其适合用来实现优先队列。堆排序是一种理论上十分重要的排序算法，它的基础也依赖于堆这一数据结构。

堆的概念

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

1.树的形状要求：这棵二叉树是基本完备的，也就是完全二叉树。
2.父母优势要求：又称为堆特性—每一个节点的键都要大于或等于它子女的键。

堆的特性：

1.只存在一棵n个节点的完全二叉树，它的高度等于[log2 n]
2.堆的根总是包含了堆的最大元素
3.堆的一个节点以及该节点的子孙也是一个堆
4.可以用数组来实现堆，对于实际实现来说，使用数组会更简单，也跟容易实现

如何构造一个堆呢？两种：

1.自底向上构造
2.自顶向下构造

自底向上构造伪代码：

HeapBottomUp(H[1...n])
//用自底向上算法，从给定数组的元素中构造一个堆
//输入：一个可排序的数组H[1...n]
//输出：一个堆H[1...n]
for i<-[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//交换后要保证堆有效性

自顶向下构造，效率较低，通过把新的键连续插入预先构造好的堆，来构造一个新堆。

从堆中删除最大的键：

1.根的键和堆的最后一个键K做交换
2.堆的规模减1
3.严格按照在自底向上构造算法中的做法，把K沿着树向下筛选，来进行“堆化”。也就是，验证K是否满足父母优势要求：如果满足，就完成了；如果不满足，K就和较大子女做交换，然后重复这个操作，知道K在新位置中满足了父母优势要求为止。

堆排序

1.构造堆，即为一个给定的数组构造一个堆
2.删除最大键，即对剩下的堆应用n-1次根删除操作

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

时间复杂度：

堆构造阶段的时间效率属于O(n)（使用自底向上算法，一个规模为n的堆只需不到2n次比较就能构造完成。），删除阶段时间效率为O(nlogn)。
所以，无论是最差情况还是平均情况，堆排序的时间效率都属于O(nlogn)。而且堆排序是在位的，不需要额外的空间。

6.6问题化简

如果我们希望付出的努力有实际价值，目标问题的算法要比直接求解原始问题更高效。

求最小公倍数

lcm(m,n)=m*n/gcd(m,n)
//gcd(m,n)可以使用欧几里得计算出来

计算图中的路径数量

一个图，它的邻接矩阵A及其平方A^2。A和A^2分别指出了长度分别为1和2的路径的数量。

优化问题的化简

最大化问题可以转换为最小化问题。

线性规划

简化为图问题

图的顶点一般用来表示说讨论问题的可能状态，而边则表示这些状态之间的可能转变。

第七章：时空权衡

考虑一下在函数定义域的多个点上计算函数值的问题。如果运算时间非常重要的话，我们可以事先将函数值计算好存入在一张表中。用时直接查。更一般的表述是，这个思想是对问题的部分或者全部输入做预处理，然后将获得的额外信息进行存储，以加速后面问题的求解。我们将这个方法称为输入增强。比如下列算法以其为基础的：

1.计数法排序
2.Boyer-Moore字符串匹配算法

其他采用空间换时间权衡思想的技术简单地使用额外空间来实现更快和更方便的数据存取。这种方法称为预构造。比如下列算法以其为基础的：

1.散列法
2.以B树做索引

还有一种空间换时间的相关设计：动态规划。这个策略是把给定问题中重复子问题的解记录在表中，然后求得所讨论问题的解。

7.1计数排序

ComparisonCountingSort(A[0...n-1])
//用比较计数法对数组排序
//输入：可排序数组A[0...n-1]
//输出：升序排列数组S[0...n-1]
for i<-0 to n-1 do Count[i]<-0
for i<-0 to n-2 do
    for j<-i+1 to n-1 do
        if A[i]<A[j]
            Count[j]<-Count[j]+1
        else Count[i]<-Count[i]+1
for i<-0 to n-1 do S[Count[i]] <- A[i]

分布计数伪代码：

DistributionCountingSort(A[0...n-1],l,u)
//用分布计数法，对来自于有限范围整数的一个数组进行排序
//输入：数组A[0...n-1]，数组中的整数位于l和u之间(l<=u)
//输出：非降序数组S[0...n-1]
for j<-0 to u-l do D[j]<-0 //初始化频率数组
for i<-0 to n-1 do D[A[i]-l]<-D[A[i]-l]+1 //计算频率值
for j<-1 to u-l do D[j]<-D[j-1]+D[j] //重用于分布
for i<-n-1 downto 0 do
    j<-A[i]-l
    S[D[j]-1]<-A[i]
    D[j]<-D[j]-1
return S

算法的运行过程参考书上，很简单。假设数组值得范围是固定的，这显然是一个效率为线性的算法，因为它仅仅对输入数组A从头到尾处理两遍。除了空间换时间之外，分布计数排序的这种高效率是因为利用了输入列表独特的自然属性。就是很多数集中在一个相对很小的区间啦，如果特别分散的情况，这种算法显然不合适。

第八章：动态规划

动态规划，一种使用多阶段决策过程最优的通用方法。如果问题是由交叠的子问题构成的，我们可以使用动态规划来解决它。

8.1三个基本例子

币值最大化问题

给定一排n个硬币，其面值均为正整数c1,c2,…,cn，这些整数并不一定两两不同。如何选择硬币，使得在其原始问题互不相邻的条件下，所选硬币的总金额最大。可以得出符合初始条件的递推方程：

F(n) = max{cn+F(n-2),F(n-1)},n>1
F(0)=0,F(1)=c1

找零问题

找零问题的一般情形：需找零金额为n，最少要用多少面值为d1

F(n) = min{F(n-dj)}+1,n>=dj
F(0)=0

要求出最优解采用了哪些硬币，我们需要使用回溯上述计算来找出哪些面值的硬币产生了最小值。可以看出回溯和动态规划本身并不冲突。

硬币收集问题

在n*m格木板中放有一些硬币，每格硬币数目最多为一个。在木板左上方的一个机器人需要手机尽可能多的硬币并把它们带到右下方的单元格。每一步，机器人可以从当前位置向右或者向下移动。设计一个算法找出机器人能找到最大硬币数并给出相应的路径。

令F(i,j)为机器人截止到第i行第j列单元格(i,j)能够收集到的最大硬币数。于是有以下递推公式：

F(i,j) = max{F(i-1,j),F(i,j-1)}+cij,1<=i<=n,1<=j<=m
F(0,j)=0,1<=j<=m;F(i,0)=0,1<=i<=n

同样通过回溯计算过程可以得出最有路径。

8.2背包问题和记忆功能

背包问题

给定n个重量为w1,w2,…,wn，价值为v1,v2,…,vn的物品和一个承重量为W的背包，求这些物品中最有价值的一个子集，并且能够将它们装入包中。

考虑一个由前i个物品定义的实例，物品的重量分别是w1,w2,…,wi，价值分别为v1,v2,…,vi，背包的承重量为j(1<=j<=W)。设F(i,j)为该实例的最优解的物品总价值。那么可以推导出下列递推式：

F(i,j) = 1. max{F(i-1,j),vi+F(i-1,j-wi)},j-wi>=0
         2. F(i-1,j),j-wi<0
//初始条件：
当j>=0,F(0,j)=0;
当i>=0,F(i,0)=0;

记忆化

8.3最优二叉查找树

二叉查找树是很重要的数据结构之一。它的一种最主要的应用是实现字典，这是一种具有查找，插入和删除操作的元素集合。如果集合中元素的查找概率是已知的（例如从历史查找的统计数据中得出），那么很自然地引出了一个最优二叉树的问题：它在查找中的平均键值比较次数是最低的。

具体举例参考书上。

最优二叉查找树的动态规划算法的伪代码：

OptimalBST(P[1...n])
//用动态规划算法求最优二叉树
//输入：一个n个键的有序列表的查找概率数组P[1...n]
//输出：在最优BST中成功查找的平均次数，以及最优BST中子数的根表R
//维护了两个表，一个主表C，一个根表R
for i<-1 to n do
    C[i,i-1]<-0
    C[i,i]<-P[i]
    R[i,i]<-i
C[n+1,n]<-0
for d<-1 to n-1 do //对角线计数
    for i<-1 to n-d do
        j<-i+d
        minval<-无穷
        for k<-i to j do
            if C[i,k-1]+C[k+1,j]<minval
                minval<-C[i,k-1]+C[k+1,j];kmin<-k
        R[i,j]<-kmin
        sum<-P[i];for s<-i+1 to j do sum<-sum+P[s]
        C[i,j]<-minval+sum
    return C[1,n],R

该算法的空间效率显然是平方级的，时间效率是立方级的。

8.4Warshall算法和Floyd算法

用于计算有向图传递闭包的Warshall算法和计算全部最短路径的Floyd算法。

本质上，这两种算法都是基于相同的思想：利用目标问题和一个更简单问题而不是更小规模问题的关系。

Warshall算法

有向图的邻接矩阵是一个布尔矩阵，当且仅当从第i个顶点到第j个顶点之间有一条有向边时，矩阵第i行第j列的元素为1。我们还会关心这样一个矩阵：给定图的顶点之间是否存在任意长度的有向路径。这种矩阵，称为有向图的传递闭包，使我们能够在常数时间内判断第j个顶点是否可从第i个顶点到达。

前面我们还见过计算图中的路径数量，A和A^2什么的，还记得么？

关于Warshall算法的举例参见书上。

Warshall算法通过一系列n阶矩阵来构造传递闭包。R0,R1,R2…Rn

每一个这种矩阵都提供了有向图中有向路径的特定信息。具体来说，当且仅当第i个顶点到第j个顶点之间存在一条有向路径（长度大于0），并且路径的每一个中间顶点的编号不大于K时，矩阵Rk的第i行第j列元素r(k)ij的值等于1。R0就是有向图的邻接矩阵。

序列中的最后一个矩阵，反映了能够以有向图中的所有n个顶点作为中间顶点的路径，因此它就是有向图的传递闭包。

计算完全最短路径的Floyd算法

给定一个加权连通图（无向或者有向图），完全最短路径问题要求找到从每个顶点到其他所有顶点之间的的距离（最短路径的长度）。

可以用一种非常类似于Warshall算法的方法来生成这个距离矩阵。它被称为Floyd算法。这个算法对于无向或者有向加权图都适用。

关于Floyd算法的举例参见书上，跟Warshall确实非常相似。

第九章：贪婪技术

回到找零问题，如果d1=25,d2=10,d3=5,d4=1。我们之前用动态规划输出了最优解，实际上对于这个实例组合，用贪婪算法也会输出最优解。但是对于某些金额来说，贪婪算法无法给出一个最优解，例如d1=25,d2=10,d3=1,而n=30。

上面想表达的意思是，在找零问题中，有一些实例是可以用贪婪算法做的。我觉得在实际生活中，设计的硬币找零的基数应该是用贪婪算法可以解的，因为这样找零比较方便啊。

对于贪婪法必须满足以下条件：

1.可行的，必须满足问题的约束。
2.局部最优，它是当前步骤中所有可行选择中最佳的局部选择。
3.不可取消的，即选择一旦做出，在算法的后面步骤中就无法改变了。

最小生成树的两种经典算法：Prim算法和Kruskal算法。它们按照两种不同的思路应用贪婪方法来解同一个问题，并且它们两者都会产生一个最优解。

9.1Prim算法

9.2Kruskal算法

不相交子集和并查算法

有很多应用要求把一个n元素集合S动态划分为一系列不相交的子集S1,S2,…,Sk,Kruskal算法就是其中一种。在把它们初始化为n个单元素子集以后，每一个子集都包含了S中一个不同的元素，然后可以对这些子集做一系列求并集和查找的混合操作。

这种数据类型是由某个有限集的一系列不相交子集以及下面这些操作构成的：

1.makeset(x)生成一个单元素集合{x}。假设这个操作对集合S的每一个元素只能应用一次。
2.find(x)返回一个包含x的子集。
3.union(x,y)构造分别包含x和y的不相交子集Sx和Sy的并集，并把它们添加到子集的集合中，以替代被删除后的Sx和Sy。

比如S={1,2,3,4,5,6}。因为makeset(i)可以生成集合{i}，这个操作应用6次后得到6个单元素子集构成的结构：{1},{2},{3},{4},{5},{6}。

执行union(1,4)和union(5,2)产生出：{1,4},{5,2},{3},{6}

再执行union(4,5)和union(3,6)，则最后得到两个不相交的子集：{1,4,5,2},{3,6}。

这种抽象数据类型的大多数实现都会使用每一个不相交子集中的一个元素作为子集的代表。

实现这种数据结构的两种主要做法：

1.快速查找，其查找效率是最优的
2.快速求并，其求并集的效率是最优的

9.3Dijkstra算法

考虑单起点最短路径问题：对于加权连通图的一个称为起点的给定顶点，求出它到所有其他顶点之间的一系列最短路径。

有很多方法都可以对这种问题求解啦，比如我们在第8章中讨论的一个更通用的求解完全最短路径问题的Floyd算法（更全面）。

Dijkstra算法只能应用于不含有负权重的图。

Dijkstra算法的标记和结构与Prim算法的用法十分相似。它们两者都会从余下顶点的优先队列中选择下一个顶点来构造一颗扩展树。但千万不要把它们混淆了。它们解决的是不同的问题，因此，所操作的优先级也是以不同方式计算的：Dijkstra算法比较路径的长度，因此必须把边的权重相加，而Prim算法则直接比较给定的权重。

9.4哈夫曼树及编码

如果使用变长编码，则会遇到定长编码不曾有的一种问题，它要求对不同的字符赋予长度不同的代码字。为了防止问题复杂化，我们只讨论自由前缀码，在前缀码中，所有的代码字都不是另一个字符代码字的前缀。

哈夫曼编码是一种最重要的文件压缩方法。除了简单和通用性外，它生成的还是一种最优编码，也就是最小长度编码（条件是，字符出现的概率是独立的，也是事先知道的，在现实生活中字符之间肯定是有联系的啊，所以才有其他更先进的压缩算法），这种方案要求我们必须将编码树的信息包含在编码文本中，以保证成功解码。

第十二章：超越算法能力的极限

回溯法和分支界限法都是以构造一颗状态空间树为基础的，树的节点反映了对一个部分解所做的特定选择。如果可以保证，节点子孙所对应的选择不可能得出问题的一个解，两种技术都会立即停止处理这个节点。

12.1回溯法

通过对所做的选择构造一颗所谓的状态空间树，我们很容易实现这种处理。树的根代表了在查找解之前的初始状态。树的第一层节点代表了对解的第一个分量做出的选择，第二层类似等等。在大多数情况下，一个回溯算法的状态孔家树是按照深度优先的方式来构造的。

n皇后问题

非常典型。

哈密顿回路问题

子集和问题

求n个正整数构成的一个给定集合A={a1,a2,…,an}的子集，子集的和要等于一个给定的正整数d。

把集合元素按照升序排序带来不少的方便。然后可以通过决策树一样的东东，求解出来，具体参考书上。

一般性说明

从更一般的角度来看，大多数回溯算法都满足下面的描述。一个回溯算法会明确地或者隐含地生成一颗状态空间树，树中的节点代表了由算法的前面步骤所定义的前i个坐标所组成的部分构造元组。

the end

最后

以上就是自由手套为你收集整理的算法设计与分析基础1.1什么是算法1.2算法问题求解基础4.1插入排序4.2拓扑排序4.3生成组合对象的算法4.4减常因子算法4.5减可变规模算法5.1合并排序5.2快速排序二叉树遍历及其相关特性6.1预排序6.3平衡查找树6.4堆和堆排序6.6问题化简7.1计数排序8.1三个基本例子8.2背包问题和记忆功能8.3最优二叉查找树8.4Warshall算法和Floyd算法9.1Prim算法9.2Kruskal算法9.3Dijkstra算法9.4哈夫曼树及编码12.1回溯法的全部内容，希望文章能够帮你解决算法设计与分析基础1.1什么是算法1.2算法问题求解基础4.1插入排序4.2拓扑排序4.3生成组合对象的算法4.4减常因子算法4.5减可变规模算法5.1合并排序5.2快速排序二叉树遍历及其相关特性6.1预排序6.3平衡查找树6.4堆和堆排序6.6问题化简7.1计数排序8.1三个基本例子8.2背包问题和记忆功能8.3最优二叉查找树8.4Warshall算法和Floyd算法9.1Prim算法9.2Kruskal算法9.3Dijkstra算法9.4哈夫曼树及编码12.1回溯法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。