Chris

由于求最小哈密顿回路的问题是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;
}

这三个算法每本算法书都要讲到，这次看《算法之道》又复习了一遍，觉得有些新的领悟，写个模板记录一下。

Kruskal和Prim算法解决的问题都是最小生成树问题，即对于一个图G<V,E>，找到它的最小生成树T<V,E’>，其中E’包含于E，使得所有V都连通。Dijkstra算法解决的是单源多点最短路径问题，即对于一个图G<V,E>和一个起点S，为图中的其它所有节点找到距离S最近的路径。

所说的图都是加权图，如果是均权图或者权重为一的图，则不存在最小生成树这一概念，因为任意一棵生成树的大小都是一致的。所谓的单源多点最短路径也可以用BFS进行解答。

这三个算法的本质都是贪心，三个问题都具有贪婪选择性质使得使用贪心算法可以得到最优解。

先来看Kruskal算法。先描述算法再证明最优性。

建立两个边集，初始时Q为所有边的集合，A为空集，算法终结时A为所求的最小生成树。每次删掉Q中权重最小的边并对其进行考察，如果它加入A中不会形成环路，则将其加入A，当A中边数打到|V|-1时，求解完毕。

Q=E
A=NULL
while(n<|V|-1)
      e=min(Q)
      Q=Q-e
      if(e加入A中不会构成回路)
            A=A AND e

容易知道一棵最小生成树所包含边的条数为|V|-1。所以求解一棵最小生成树的过程就是选择|V|-1条边的过程。问题的开始相当于所有的节点都是分离的，而问题的结尾要求所有的节点连通。每一条边的加入必须要使图的连通度加一（否则构成环路，则产生冗余的可删除的边）。将问题抽象为：对于一个森林和一些潜在的边，要求加入一条权重最小边使得森林的连通度加一，即森林中树的个数减少一。这样问题就具备了贪婪选择性质：每次应该选择不构成回路的权重最小的边，并且次贪婪选择只引出一个子问题。另外该问题又具备最优子结构，最优解一定包含子问题的最优解，否则可以用子问题的最优解替换当前子问题的解从而得到整个问题的更优解而导出矛盾。因此用贪心策略的Kruskal算法解决最小生成树问题是正确的。

再看Prim算法。Kruskal算法以边的权值作为贪心考虑，每次加入一条能起到作用的权重最小的边，从而得到最优解，是一种很直观的思路。另一种思路，将问题初始阶段看做所有节点都独立，然后构建一个连通的集合，每次按照贪婪的策略向该集合内加入一个点，最终使得所有点都在集合内，便完成了最小生成树的构建。那么应该给每个点赋一个什么样的值来进行贪婪选择呢？应该赋予每个点距离现有集合的距离（与集合里距离最短的点之间的距离）。

伪代码如下：

Q=V
A=NULL
while(|A|<|V|-1)
      v=Q中到A中距离最小的点
      A=A AND v
      由于v的加入，更新Q中剩余点到A的距离

Prim算法在求解的过程中一直维持中途解是一棵树，而Kruskal的中途解则是一个森林。将问题抽象为给定一棵树和一组散节点，通过将散节点中的一个加入树中从而使得树的节点数增一，要求增加的权重最小。这样问题就具有了最优子结构和贪婪选择性质。每步求解后的子问题的最优解一定包含在整个问题的最优解当中，同样也是反证法可以证明；每次的贪婪选择都只会留下一个子问题。这样就证明了Prim算法的正确性。

Dijkstra算法和Prim算法如出一辙。也是每次向一棵树（或者说子图）按照贪心的策略加入一个节点，加入后对会被新加入节点所影响的未加入节点信息进行更新，再重复上述过程直到所有节点都加入为止。区别在于贪心所考虑的指标不同。最小生成树要求的是连通，因此应该将与已构建的部分生成树中的任意节点的距离中最小的一条距离作为贪心考虑，而单源多点最短路径考虑的是所有节点与一个特定原点的距离，因此在进行贪婪选择的时候也应该选择所有未加入的点中与该原点之间距离最短的节点，加入后要更新的信息也是这个，更新方法是考察原有距离和经由刚加入的节点到达原点的距离哪个更小。

伪代码如下：

Q=V
A=NULL
while(|A|<|V|-1)
      v=Q中到s距离最小的点
      A=A AND v
      由于v的加入，更新Q中剩余点到A的距离
      for each x in Q
            dist[x]=min(dist[x],dist[v]+e(u,v))

《算法之道》提到，问题的基本求解理念有三种——分治与递归、动态规划、贪心。

分治与递归所能处理的问题最多，对问题的性质没有要求（不过可能会出现很复杂的分治情况），所需要求解的子问题数最多，而且如果子问题有重复，则每一次都要重复求解；

动态规划叫做Dynamic Programming，这里的Programming的意思不是编程而是查表，动态规划不如翻译成动态查表更容易理解些，规划这个词太空了。动态规划的思想就是发现在分治递归求解中有很多子问题都被求解了多次从而造成了复杂度的上升，如果只求解一次然后存储起来再备后来查表，就可以解决这个问题。所以将递归的自顶向下改为自底向上就得到了动态规划的思路，如果仍然使用自顶向下的思路但是每次求解一个子问题的时候查看是否已经求解过（自然也需要将子问题的解存储起来）则得到了“存储化递归”的解法，复杂度与动态规划只有常数差别。

动态规划要处理的问题要求问题具有最优子结构（即最优解包含子问题的最优解），是一种自底向上的求解思路，与递归正好相反，每次求解到一个阶段时，该阶段求解所依赖的子问题已经完全求解完毕，因此每一步的求解都是在直到全部所需信息的情况下进行的，因此可以得到全局最优解。

贪心算法如果想要得到最优解，需要对问题性质有更严格的要求，除了要有最优子结构外，还要求问题具有贪婪选择性质。具体来说就是：贪心是一种策略，即每一步都要选择当前看来最好的，做完此选择后便将问题化为一个（仅仅一个）子问题，这是一个顺序的求解过程，每一步都是单独考虑，只考虑局部最优，因为并没有完成对之后子问题的求解，所以贪心算法不能完成对整个解空间的搜索，因此通常不能得到最优解。除非问题具有贪婪选择性质。所谓贪婪选择性质就是问题经过一次贪婪选择后只能形成一个子问题，这样求解空间实际上就是一个线性的空间，贪心算法可以得到最优解。

也许有些问题初看起来并不具备该性质而需要一定的转化，这方面一个经典的例子是教室排课问题：给出N门课的开始时间和结束时间，如何排课才能让尽可能多的课在一个教室里面上？贪心策略是每次选择可以选择的课（即开始时间晚于当前已排课程中结束最晚的课的结束时间）里结束时间最早的课。

Description

Input

Output

Sample Input

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

Sample Output

15

Source

#include <iostream>
 
using namespace std;
 
int numbers[105][105],dp[105],n,temp[105];
 
int main()
{
	cin>>n;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++)
			cin>>numbers[i][j];
	int Max = 0;
	for (int i = 1;i <= n;i++)	//start from line i
	{
		memset(temp,0,sizeof(temp));
		for (int j = i;j <= n;j++)	//end at line j
		{
			for (int k = 1;k <= n;k++)
			{
				temp[k] += numbers[j][k];
 
				if (temp[k] + dp[k-1] > 0)
					dp[k] = temp[k] + dp[k-1];
				else
					dp[k] = 0;
 
				if (Max < dp[k])
					Max = dp[k];
			}
		}
	}
	cout<<Max<<endl;
}

Description

‘Oh no, they’ve done it again’, cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without crossing each other, is imminent. Bearing in mind that there may be thousands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do.

Input

Output

Continue reading »

今天一个高中同学的校内更新了一个状态“屋内有多张桌子，若每3人一桌，多2人；每5人一桌，多4人；每7人一桌，多6人；每9人一桌，多8人；11人一桌刚刚好；Q:共有多少人？”。第一反应自然是“中国剩余定理”，但是细细想来，第一次看到中国剩余定理的时候我并没有仔细看透，而只是以为它是一种预处理手段，今天上网查了一下，原来是一个O(N)的解法（N为条件个数），非常高效，自己也算了算，原理很直观，很漂亮。当初低估你了。

就用上面的例子来说明吧。

我们要求一个数，这个数除3余2，除5余4，除7余6，除9余8，除11余0。首先我们应该保证这些数互素，否则条件是冗余的，容易发现“除9余8”包含“除3余2”，因此去掉第一个条件。下一步求出剩下这些互素的数5，7，9，11的最小公倍数3465，然后分别考察这四个互素的数：

1.用3465除以5，得到693，693是除了5以外三个数的最小公倍数，因此在我们要求的结果里加上任意倍的693不会影响对另外三个数余数的情况，而只会影响5的余数。我们的目标是令对5余4，容易发现693*3是符合该条件的最小数，记下它。接下来考察其它数的时候都按照这个方法，因为都是5的倍数，所以不会影响除5余4这个结果。

2.再举一步，考察7，用3465除以7，得到495，因此我们在所要求的结果上加上任意倍的495，都不会影响除了7以外的三个数的余数的情况，自然也不会影响刚刚考察过的5。而偶们的目标是除7余6，容易得出495*4符合条件。

3.考察9得到385*5。考察11得315*11。

4.将上述结果相加693*3+495*4+385*5+315*11=9449，则9449一定满足题目的条件，但是却不是最小的答案，因为从9449中加上和减去任意倍的3465都不影响对各个数的余数，因此对3465取模得到2519为最终答案。

Description

Input

Output

Sample Input

2 1
8 4
4 7

Sample Output

0
1
0

Source

这个游戏就是所谓的威佐夫博弈（Wythoff Game），很有意思。

昨天就在做这道题目，思考成果是：用一个二维数组来表示玩家将面临的局面，即a[i][j]表示两堆石头分别有i个和j个，如果a[i][j]是必败局面的话，那么——这个点的右侧所有点a[i][k](k>j)都是必胜点，因为可以通过拿走第二堆的k-j个石子令对方面临必败局面a[i][j]；这个点的下侧所有点a[k][j](k>i)都是必胜点，因为可以通过拿走第二堆的k-i个石子令对方面临必败局面a[i][j]；这个点的右下方45度所有点a[i+k][j+k](k>0)都是必胜点，因为可以通过同时拿走两堆的k个石子令对方面临必败局面a[i][j]。这样如果在二维数组a[i][j]处标记”X”表示必败的话，在上面提到的三类点的位置都可以标记”O”表示必胜了，做完这项工作后，再挑选如今距离原点最近的未被标记的点，它一定是下一个必败点——因为它无法通过游戏规则移动到一个必败点，并且规则规定的动作都是朝向原点移动的，而它是距离原点最近的未被标记的点，因此它只能移动到一个必胜点从而让对方获胜，所以该点一定是下一个必败点。有了新必败点后就可以重复上述工作，直到找出问题范围内的所有必败点。

然而这样的模拟工作是不被允许的，因为数据量太大了，因此这道题要求的是给定两个数i,j，有办法立刻判断a[i][j]是不是必败点，在O(1)时间给出解答。

我试图找到必败点的规律，但是没成功，以上就是昨天的思考结果。因为这个问题够简洁，所以我坚信一定有简单规律的，因此在考察了很大数据量仍然没有发现规律后，我无比好奇这道题的解法。今天上网一搜才知道规律果然够简单够经典，竟然是“黄金分割”，以下内容来自对网上内容的总结：

前几个必败点如下：(0，0)，(1，2)，(3，5)，(4，7)，(6，10)，(8，13)……可以发现，对于第k个必败点(m(k),n(k))来说，m(k)是前面没有出现过的最小自然数，n(k)=m(k)+k。一个必败点有如下性质：

1.所有自然数都会且仅会出现在一个必败点中；

证明：m(k)是前面没有出现过的最小自然数，自然与前k-1个必败点中的数字都不同；m(k)>m(k-1)，否则违背m(k-1)的选择原则；n(k)=m(k)+k>m(k-1)+(k-1)=n(k-1)>m(k-1)，因此n(k)比以往出现的任何数都大，即也没有出现过。又由于m(k)的选择原则，所有自然数都会出现在某个必败点中。性质1证毕。

2.规则允许的任意操作可将必败点移动到必胜点；

证明：以必败点(m(k),n(k))为例。若只改变两个数中的一个，由于性质1，则得到的点一定是必胜点；若同时增加两个数，由于不能改变两数之差，又有n(k)-m(k)=k，故得到的点也一定是必胜点。性质2证毕。

3.一定存在规则允许的某种操作可将必胜点移动到必败点；

证明：以某个必胜点(i,j)为例。因为所有自然数都会出现在某个必败点中，故要么i等于m(k)，要么j等于n(k)。若i=m(k)，j>n(k)，可从j中取走j-n(k)个石子到达必败点；若i=m(k)，j<n(k)，可从两堆同时拿走m(k)-m(j-m(k))，从而到达必败点(m(j-m(k))，m(j-m(k))+j-m(k))；若i>m(k)，j=n(k)，可从i中取走i-m(k)个石子到达必败点；若i<m(k)，j=n(k)，需要再分两种情况，因为i一定也出现在某个必败点中，若i=m(l)，则从j中拿走j-n(l)，若i=n(l)，则从j中拿走j-m(l)，从而到达必败点(m(l),n(l))。性质3证毕。

判断一个点是不是必败点的公式与黄金分割有关，为：

m(k) = k * (1 + sqrt(5))/2

n(k) = m(k) + k

至于为什么如此，我就不知道了，也没有查到，很好奇。

POJ1067就是这道题，代码如下：

#include 
#include 
 
using namespace std;
 
int main()
{
	int m,n;
	while(cin>>m>>n)
	{
		if (m > n)
		{
			int temp;
			temp = m;
			m = n;
			n =temp;
		}
		int k = n - m;
		int data = floor(k*(1.0+sqrt(5.0))/2.0);
		if (data == m)
			cout<<0<<endl;
        }
}

Description

“Help Jimmy” 是在下图所示的场景上完成的游戏。

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。

Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。

设计一个程序，计算Jimmy到底地面时可能的最早时间。

Input

1
3 8 17 20
0 10 8
0 10 13
4 14 3

23

if (板子i的左侧下方Max以内的距离有其它板子j)
	f[i].fromLeft=i高度-j高度+max(i的X走到j左侧的时间+f[j].fromLeft,i的X走到j右侧的时间+f[j].fromRight);
else
	f[i].fromLeft=正无穷;

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
#define INF 9999999
 
struct _platform 
{
	int x1;
	int x2;
	int height;
};
 
bool UDgreater(_platform p1,_platform p2)
{
	return p1.height < p2.height;
}
 
struct _time
{
	int fromLeft;
	int fromRight;
};
 
int N,X,Y,MAX;
vector<_platform> pvec;
_time fastest[1005];
 
void prepare()
{
	memset(fastest,INF,sizeof(fastest));
	pvec.clear();
	cin>>N>>X>>Y>>MAX;
 
	_platform platform;
	platform.x1 = -INF;
	platform.x2 = INF;
	platform.height = 0;
	pvec.push_back(platform);
 
	for (int i = 1;i <= N;i++)
	{
		cin>>platform.x1>>platform.x2>>platform.height;
		if (platform.height <= Y)
		{
			pvec.push_back(platform);
		}
	}
	platform.x1 = X;
	platform.x2 = X;
	platform.height = Y;
	pvec.push_back(platform);
	sort(pvec.begin(),pvec.end(),UDgreater);
}
 
bool CanLoad(int i,int j,int dir)
{	//whether Jimmy can load on j from i safely;0 for left,1 for right
	if (dir == 0)
	{
		if (pvec[i].height-pvec[j].height <= MAX&&\
			pvec[i].x1>=pvec[j].x1&&pvec[i].x1<=pvec[j].x2)
			return true;
	}
	else
	{
		if (pvec[i].height-pvec[j].height <= MAX&&\
			pvec[i].x2>=pvec[j].x1&&pvec[i].x2<=pvec[j].x2)
			return true;		
	}
	return false;
}
 
int main()
{
	int n;
	cin>>n;
	while (n--)
	{
		prepare();
		fastest[0].fromLeft = 0;
		fastest[0].fromRight = 0;
		int size = pvec.size();
		for (int i = 1;i < size;i++)
		{
			int leftMin = INF,rightMin = INF;
			int j = i-1;
			while(j>=0&&!CanLoad(i,j,0))
				j--;
			if (j > 0)
				fastest[i].fromLeft = min(fastest[j].fromLeft+\
				abs(pvec[i].x1-pvec[j].x1),fastest[j].fromRight+\
				abs(pvec[i].x1-pvec[j].x2))+abs(pvec[i].height-pvec[j].height);
			else if(j == 0)
				fastest[i].fromLeft = abs(pvec[i].height-pvec[j].height);
			j = i-1;
			while (j>=0&&!CanLoad(i,j,1))
				j--;
			if (j > 0)
				fastest[i].fromRight = min(fastest[j].fromLeft+\
				abs(pvec[i].x2-pvec[j].x1),fastest[j].fromRight+\
				abs(pvec[i].x2-pvec[j].x2))+abs(pvec[i].height-pvec[j].height);				
			else if(j == 0)
				fastest[i].fromRight = abs(pvec[i].height-pvec[j].height);
		}
		cout<<min(fastest[size-1].fromLeft,fastest[size-1].fromRight)<<endl;
	}
}