Chris

通常我们把一个有向无环图边上的权值看做两个节点之间的距离，在这个模型下的问题有各种最短路问题。如果将边上的权值不看做距离而看做两点间的容量（比如两个城市之间一天的运输能力），这样的有向无环图就叫做流网络，对应的问题就是求最大流——单位时间内通过网络的最大容量（比如工厂所在城市一天最多可以生产多少才能全部经过一个流网络运到仓库所在城市而不造成中途的淤积）。

流网络只有一个源点和一个汇点。关于定义就不说了，算法导论上很清楚。有一点要说的是，如果一个流网络有多个源点和多个汇点，可以通过增加一个到所有现有源点的容量都无穷的超级源点和一个所有汇点到其容量都无穷的超级汇点转化成只有一个源点和一个汇点的流网络。

求流网络的最大流算法是Ford-Fulkerson算法。首先定义一条边的残留容量是容量减去现有流，由残留容量标示的网络称为残留网络。再定义增广路径是残留网络中从源点s到汇点t的一条路径。Ford-Fulkerson算法是一个迭代过程。每次在残留网络中查找一条增广路径，然后把这条增广路径中最小的一段残留容量加到增广路径各条边的流上，更新残留网络继续迭代，直到找不到增广路径为止。此时退出迭代，现有流就是最大流。

二分图有两部分节点L和R，各部分内部节点之间没有边，即每条边的两个节点都一定分属这两部分，二分图的一个匹配是找到这样一组边，使得每个节点都只有至多一条边与其相连。

二分图的最大匹配问题可以转化为网络最大流问题。增加一个到所有L中顶点容量均为1的源点s和一个所有R中顶点到其容量均为1的汇点t，所有L到R中的边容量也设置为1，现在查找此网络流的最大流就等同于求此二分图的最大匹配。证明过程见算法导论。

POJ2536就是一道二分图最大匹配的应用。题目给出n个老鼠的坐标和m个鼠洞的坐标，如果一只老鼠能在一定时间内到达一个鼠洞，就能躲过老鹰。所以如果某个老鼠与某个鼠洞之间距离小于某值，它俩之间就存在一条边，否则不存在，这是一个明显的二分图。而要求有多少老鼠能躲过老鹰，自然是求此二分图的最大匹配。

代码如下： Continue reading »

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

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

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

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

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

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

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))