Chris

算法课最后一节讲到了卡特兰数，总结和学到了很多以前不知道的东西。

卡特兰数的递推公式是F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}
一般性公式为F(n)=C(2n,n)/(n+1)

可以描述的问题有
1、n个元素的二叉查找树有多少种。
2、n*n棋盘从左下角走到右上角而不穿过主对角线的走法。
3、2n个人排队买票问题，票价50，n个人拿50元，n个人拿100元，售票处无零钱，能顺利卖票的所有排队方式。
4、n个元素全部入栈并且全部出栈的所有可能顺序。

这些问题的答案都是卡特兰数F(n)。但是很明显可以看出后三个问题是同质的。
都可以抽象成2n个操作组成的操作链，其中A操作和B操作各n个，且要求截断到操作链的任何位置都有：A操作（向右走一步、收到50元、元素入栈）的个数不少于B操作（向上走一步、收到100元找出50元、元素出栈）的个数。故问题2、3、4其实是同一个问题。

下面先证明问题2、3、4和问题1同解，再证明问题2、3、4的解是F(n)=C(2n,n)/(n+1)，从而证明问题1的解也是F(n)=C(2n,n)/(n+1)。 Continue reading »

看了《算法导论》上对动态规划的讲解，觉得自己对动态规划的理解又进了一步，之前在读到《算法之道》相关章节时就有这感觉，但是仍然不敢说自己已经完全掌握了动态规划，只是比以前又透彻了一些，说说自己新的理解，其实就是复述一下算法导论上的内容而已。

0.两个例子

装配线调度问题

一个产品要经过N道工序，有两条装配链提供着N道工序，在任何一道工序i时产品都可以选择在两条线上的一条进行加工，在装配线1上加工工序i的时间 为a[i][1]，装配线2上类似。在同一条装配线上前进不花时间，跳转到另一条装配线上需要一定的时间t[1][i]（从装配线1的工序i跳转到装配线 2的工序i+1所花费的时间）和t[2][i]（类似）。

问题是求解一个产品最快完成所有工序所需的时间。

动态规划解法：

我们用dp[i][j]存放在第j条装配线完成第i到工序所用的最少时间，其中i=1…N,j=1,2。因为要么是从同条装配线的上一道工序而 来，要么是从另一条装配线的上一道工序跳转而来，而最少时间应该是这两种情况里较少的那种。注意应该认为dp[i-1][1]和dp[i-1][2]已经 求解完毕，或者说不要关心它们，只要认为它们存放的是正确答案就可以了，为何可以如此，见后面。则有：

dp[i][1] = min(dp[i-1][1]+a[i][1],dp[i-1][2]+t[i-1][2]+a[i][1])

dp[i][2] = min(dp[i-1][1]+t[i-1][1]+a[i][2],dp[i-1][2]+a[i][2])

这样min(dp[N][1],dp[N][2])就是想要的答案。

矩阵链乘法问题

两个矩阵A(lxm)*B(mxn)相乘所需要的代价是O(lmn)，而相乘得到的矩阵式C(lxn)型的，l和n作为矩阵的行列数量仍然保存在了 矩阵链中，因此对于一个矩阵链的乘法来说，做乘法的顺序不同，所花费的时间就可能相差很多，矩阵链乘法问题就是对于一个给定的矩阵链相乘，求解最少的计算 时间（如何安排乘法的计算顺序）。

动态规划解法：

我们用dp[i][j]表示矩阵链中从第i个乘到第j个所需的最少时间，用r[i]和c[i]分别表示第i个矩阵的行数和列数。有：

dp[i][j]=min(k)(dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j])

注意c[k]==r[k+1]

即，i到j这一部分矩阵链的最优计算一定是在某处k（i<=k<j）将矩阵链分成两部分，通过先计算i到k和k+1到j这两条矩阵链再将这两个矩阵相乘得到的。

1.什么是动态规划

dynamic programming这里的programming指的是查表，表里存放的是之前求解过的子问题的解。动态规划就是动态查表，即在求解的过程中的每一步 都需要查表来得到对当前子问题求解所需的信息。如在装配线问题上dp[i][1]就分别查表找到了dp[i-1][1]和dp[i-1][2]；矩阵乘法 链问题上dp[i][j]的求解查表找到了对应于不同k值的dp[i][k]和dp[k+1][j]。

正因为存放在了表里，所以不用再次求解，才达到了较高的效率，将传统回溯解法指数的复杂度降低为多项式程度，关于复杂度后面还会说到。

2.最优子结构

一个问题要想用动态规划的方法来解决，必须具有最优子结构，至于为什么具有最优子结构的问题就可以用动态规划来解决，后面说。现在说说什么叫最优子结构。

最优子结构是指一个问题的解是一个选择过程，可能是二选一（装配线问题选择从前一道工序的哪条线上过来）、可能是多选一（矩阵链决定从哪里断开，即 先做哪一处乘法）。假设作出了正确的选择后（这其实是需要子问题信息来做选择依据的），原问题就退化成一个或多个子问题（在装配线问题中，退化成所选择的 那条装配线上完成第i-1道工序需要的最少时间，这是一个子问题；在矩阵乘法链问题中，退化成两条矩阵链i到k和k+1到j的最优求解问题，这是两个子问 题），所谓子问题指的是与原问题同构但规模较小的问题。

光有这个性质还不叫具有最优子结构，最优子结构的另一个要求是原问题的最优解必须包含子问题的最优解。在验证这一点时，可以通过剪贴+反证法的思 路，即如果该解法用到的子问题的解不是最优的，那么以最优的解代替之一定可以得到该问题的一个更好的解。还是通过例子说，装配线问题中，不管加工工序i的 最优选择是从哪条线过来，所用到的在该线上加工工序i-1的时间一定需要是最优的，否则用最优的替换之可得到对于工序i的一个更优的解。

有了这两条性质——1.做选择后问题退化为一个或几个子问题、2.问题的最优解包含子问题的最优解，一个问题就具备了最优子结构。

3.为什么高效、如何求解

如果一个问题具有最优子结构的第一条性质，就可以使用分而治之的思想求解，比如递归。通常做法是将问题分解，然后对于分解出现的各个子问题分别递归求解，如果这种分解是多分枝的，那么复杂度应该是指数级的。

同递归思想一样，动态规划也需要对所有子问题都全部求解才能得到最终的答案，但是动态规划不愿意单纯地像递归那样做，而希望能够通过一些手段只做必要的工作，多余的一点都不想做。

动态规划是基于如下两点观察：

1）某个子问题的求解只和规模更小的子问题求解有关，而与与其同规模或者更大规模的子问题求解无关。

2）某个子问题的求解只用到其子问题的最优解，也就是说对于一个子问题来说，只有其最优解是有价值的。

通过观察1）我们知道只要在求解所有子问题时控制子问题的求解顺序按照子问题规模递增来进行，就能保证求解任意子问题时，它所依赖的规模较小的子问题都已经求解完毕。

通过观察2）我们知道只有最优解是有意义的，因此我们将最优解存在表里以供后面用到时查找，就可以保证某个子问题只被求解一遍，而且有了上一个观察，在求解某个子问题时，可以保证它所需要的表格内容都已经准备好了。

所以动态规划的解法已经呼之欲出了。

首先证明一个问题具有最优子结构，然后发现描述该问题的子问题应该是什么形式的（装配线问题中的dp[i][1]、dp[i][2]和矩阵链乘法问题中的dp[i][j]），按照子问题规模递增的顺序求解所有子问题，最后得到整个问题的解。

而，这里的关键就是找出子问题的形式，和子问题在经过选择后如何向更小规模的子问题退化。

下面给出两个例子的伪代码

装配线问题

dp[1][1] = a[1][1];
dp[1][2] = a[1][2];
for (int i = 2;i <= n;i++)
{
	dp[i][1] = min(dp[i-1][1]+a[i][1],dp[i-1][2]+t[i-1][2]+a[i][1]);
	dp[i][2] = min(dp[i-1][1]+t[i-1][1]+a[i][2],dp[i-1][2]+a[i][2]);
}

矩阵链乘法

for (int i = 1;i <= n;i++)
{
	dp[i][i] = 0;
}
for (int l = 2;l <= n;l++)
{
	for (int i = 1;i <= n-l;i++)
	{
		int j = i+l-1;
		for (int k = i;k < j;k++)
		{
			dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j]);
		}
	}
}

4.动态规划的时间复杂度由什么决定

动态规划的过程就是求解所有子问题的过程，因此首先复杂度由子问题的个数决定，而子问题的个数又有子问题的形式所决定。在装配线问题中子问题形式是 dp[i][1 or 2]，其中只有i是变化的，因此子问题个数为O(n)；在矩阵链乘法问题中，子问题形式是dp[i][j]，i和j都在变化，因此子问题个数是 O(n^2)。另外由于前面所提到的每一个子问题都是一个选择，可能是二选一，可能是多选一，而要解答此子问题就要考察所有的选项，因此每一个子问题的求 解时间还和面临的选择个数有关，因此复杂度应该是子问题个数*每个子问题面临选择数。这样，装配线问题的时间复杂度O(n)，矩阵链乘法问题的时间复杂度 为O(n^3)，正如代码中所示。

由于求最小哈密顿回路的问题是NP问题，随着递归的进行，时间复杂度为阶乘级（如不加标记则为指数级），故最优解法能解决的问题范围是非常有限的。前面写过的那篇解决N=16个节点的图大概需要十几秒钟。

这里给出一种近似解法，是老杨上课时候给出的。后来上网搜文献搜到了这个想法的相关paper，发现作者就是老杨，据说是他第一个提出的。

想法倒是很朴素，采用分片，将一个大图分成若干个小图，每个小图单独求最小哈密顿回路，然后将各个回路连上，这样得到的基本上不会是最优解，但是能解决问题的规模大大提高了，算是一个比较好的近似解法思路吧。

原来那篇的数据结构是邻接矩阵，这里就不能用邻接矩阵了，而只能用坐标来描述图上的点，边之间的权重直接取两点之间的距离，直接默认为完全图。

代码有两个小问题没有解决，一是没有剪枝，二是有一处内存泄露。弄得头大，暂时不搞了。

解N=40是瞬间的事，当然了相当于解N=10嘛，不剪枝也挺快的。N=50大概需要17分钟，慢的不行。

Continue reading »

第二次上课的作业之一是实现所有会的排序算法（之二是实现查找欧拉回路的算法），用了总计大概两天的时间写好了这九个排序算法。没有一个算法是一次通过的，都经过了调试，甚至冒泡，而且后来才发现我第一次写的冒泡程序竟然是错误的，囧。
这还是第一次把这些算法全部亲手实现，收获还是很大的，真的加深了理解。期待通过这门课有效地提高自己的编程能力。
废话不说，上代码。
以下算法，没给出参数的默认排序范围为data[]的第0位到第N位。有些采用分治思想的算法需要范围参数，如快排和归并。
为了优化，在递归过程中如果待排序长度较短则使用插入排序代替递归，因此插入排序函数有一个带参数版本为此所用。桶排序需要一个算法实现桶内排序，这里选择了快排，因此快排有一个带三个参数的重载版本。
另外堆排序的实现用了一个类加一个外部函数。
genData函数用于生成随机数据；
check函数用于检查数据是否有序；
exchange函数用于交换两个数据；
show函数用于打印；
digit函数返回数据的某一位（用于基数排序）；
Continue reading »

老杨留的作业，折腾几个小时加上参考别人的终于写出来了，还是很弱啊。

效率貌似还可以，强化了分支定界的条件之后计算N=20的情况只需要十几秒。

好好体会一下~

 
#include <cstdlib>
#include <iostream>
#include <stdlib.h>
#include <time.h>
 
using namespace std;
 
#define N 15
 
int curLightestWeight = 1000000;
int curDepth = 0;
int curWeight = 0;
int depth;
int curCircle[N],bestCircle[N];
bool used[N];
int p[N][N];
 
void update();
void show();
 
void genGraphic(int maxWeight)
{
	for(int i = 0;i < N;i++)
	{
		for(int j = 0;j < N;j++)
		{
			if(i == j)
				p[i][j] = 0;
			else
				p[i][j] = rand()%maxWeight + 1;
		}
	}
	for(int i = 0;i < N;i++)
	{
		for(int j = 0;j < N;j++)
		{
			cout<<p[i][j]<<"   "; 		 
		} 		 
		cout<<endl;
	}
}
 
void MHC_recursion(int curVertex)
{
	curCircle[curDepth] = curVertex;
 
	curDepth++;
	used[curVertex] = true;
 
	if(curWeight + (depth - curDepth) >= curLightestWeight)
	{
		curDepth--;
		used[curVertex] = false;
		return;
	}		
	else if(curDepth == depth)
	{
		int thisWeight = p[curVertex][0];
		curWeight += thisWeight;
		if(curWeight < curLightestWeight)
		{
			curLightestWeight = curWeight;
			update();
		}
		curDepth--;
		used[curVertex] = false;
		curWeight -= thisWeight;
		return;
	} 
	else
	{
		for(int i = 0;i < N;i++)
		{
			if(i == curVertex || used[i] == true)
				continue;
			int thisWeight = p[curVertex][i];
			curWeight += thisWeight;
			MHC_recursion(i);
			curWeight -= thisWeight; 		
		}  
	}
	used[curVertex] = false;
	curDepth--;
	return;
}
 
void update()
{
	for(int i = 0;i < N;i++)
		bestCircle[i] = curCircle[i];
}
 
void show()
{
	for(int i = 0;i < N;i++)
		cout<<bestCircle[i]<<"-->";
	cout<<bestCircle[0]<<endl;
	cout<<"The weight of the circle is "<<curLightestWeight<<"."<<endl; 
}
 
void init()
{
	curDepth = 0;
	curWeight = 0;
	curLightestWeight = 1000000;
	depth = N;
}
 
int main(int argc, char *argv[])
{
	genGraphic(9);
	init();
	MHC_recursion(0);
	show();
	system("PAUSE");
	return EXIT_SUCCESS;
}