图论--旅行商问题

五一果然基本献给了数据压缩（除了两个晚上用于打球），看了小波的一些理论，看了EZW编码和SPIHT编码方法，看了一篇基于提升小波和改进SPIHT算法的图像编码的论文，最后就决定以这篇文章为基础进行实现了。还好理解了SPIHT算法的整个过程了，不然这篇文章估计也看不懂。现在比较愁的是，我要用matlab实现好呢？还是用c实现啊？matlab不是很熟，可是如果c的话可能要有很多跟图像相关的操作，还有矩阵。。。有关数据压缩的，就先到这里一个段落吧。

 

最后一个晚上开始做旅行商问题(tsp)。

 

首先描述一下问题：salesman从某个城市出发，要去很多城市推销商品，从a城市到b城市路上的开销已知，现在要找一条路，从salesman从该城市出发，最后又回到这个城市，路上的开销最少。

 

以前一直听说tsp是一个NP难问题，做数模的时候从来不敢轻易用精确算法来解决这个问题（其实当时图的规模也不大），对于很多启发式算法又其实不是很懂，总之就是，我从来没有觉得答案是最优解。借着这次机会，消除了一些思维误区，也告诫自己，凡事不能浅尝辄止。

 

解题思路是从《图论与代数结构》这本书上看来的，我结合例子试着复述一遍：

 

例：G=[ 0 42 33 52 29

            42  0 26 38 49

            33 26  0 34 27

            52 38 34  0 35

            29 49 27 35  0 ]

假设以顶点1、2为顶点的边表示为e12

 

首先是对边根据它的权重从小到大排序。

e23(26)  e35(27)  e15(29)  e13(33)  e34(34)  e45(35)  e24(38)  e12(42)  e25(49)  e14(52)

 

构造哈密顿回路H：

把符合条件的边一条一条地加到H中去（符合条件指的是：如果将某条边加入到H中去，不会有顶点的入度超过3）直到H有n条边。这样就构成了一个哈密顿回路。

应该说，构成哈密顿回路的过程是一个搜索过程。搜索的树的形状差不多是这样子的：

根节点是人为构造的，设它为level=-1, 下面包含了（n-1)*n/2-n+1个子节点，如上面的例子，n=5，根节点下面有6个子节点，分别是

e23 e35 e15 e13 e34 e45

它代表的含义是，可以把这条边放在第0层，并接着往下再搜索4条边形成一个H回路。这也就是为什么只有(n-1)*n/2-n+1个子结点了。

以e23为结点的树的第1层有孩子结点：e35 e15 e13 e34 e45 e24

以e35为结点的树的第1层有孩子结点：e15 e13 e34 e45 e24

看出来没有，子结点的边一定比父结点要大。

深搜的时候，有两个条件可以进行剪枝：

（1）如果边不符合条件，以这条边根结点的树不需要再往下搜索

（2）如果通过该边得到的回路的总开销大于前面找到的回路的总开销，以这条边的父结点为根结点的树不再往下搜索

第一点是很显然的，比方说从e23这条边进行深搜，路径是：e23->e35->e15，e15下面有子结点：e13, e34, e45, e24, e12， e12、e34、e45都不符合要求，因此这些树都不需要进行搜索了。

第二点需要想到的是，父结点下面的siblings是从左到边变大的，且子结点都比父结点大，所以如果左边的搜索到的H回路已经比原先的H回路权重大了，再往下或往右搜索肯定是更大的，所以整个父结点都不需要搜索了。

 

不知道我把问题解释清楚了没有？

 

其实之前看书里的解题思路的时候，我还不是这么想的，在实现的过程中递归到我自己也迷糊了，最后才提炼出来这样的结果的，呵呵。我还是不大会递归啊。

 

最后看一下实现的代码：

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

double currentMax = 0.0;
int maxRound;

//a struct to ease index
typedef struct {
	int start;
	int end;
	double cost;
	int index;
}edge;

//record the optimum route
edge* bestPath;

//the function for qsort
int edgeCompare( const edge* a, const edge* b ){
	if( a->cost - b->cost > 0.0001 )
		return 1;
	if( a->cost - b->cost < 0.0001 )
		return -1;
	return 0;
}

double tsp( edge* cost, edge* stack, int* count, int n, double current, int level ){
	int i;
	if( level == n-1 ){
		if( current < currentMax ){
			currentMax = current;
			for( i=0; i<n; i++ )
				bestPath[i] = stack[i];
			}
		return currentMax;
	}
	for( i=stack[level].index+1; i<n*(n-3)/2+level+2; i++ ){
		//if the edge is unproper, no further tsp is performed to this node
		if( count[cost[i].start]+1 < 3 && count[cost[i].end]+1 < 3 ){
			stack[level+1] = cost[i];
			count[cost[i].start] ++;
			count[cost[i].end]++;
			current += cost[i].cost;
			double r;
			//if the cost of the H route newly get is no better then the previously best one
			//no further tsp is performed to this level, that's this node's father node
			if(  (r = tsp( cost, stack, count, n, current, level+1 )) > currentMax )
				return currentMax;	
			//restore after recursive call
			count[cost[i].start]--;
			count[cost[i].end]--;
			current -= cost[i].cost;
		}
	}
	return currentMax;
}

main(){
	int num, s, e, i;
	double c;
	edge* edges;
	//the graph is construct by user input
	printf( "enter the number of nodes: " );
	scanf( "%d", &num );
	maxRound = num;
	bestPath = (edge*)malloc( sizeof(edge)*num );
	edges = (edge*)malloc( sizeof(edge)*num*(num-1)/2 );
	printf( "enter the edge and its cost in such a triple: <start end cost>\n" );
	i=0;
	while( i<num*(num-1)/2 ){
		scanf( "%d %d %lf", &s, &e, &c );
		edges[i].start = s;
		edges[i].end = e;
		edges[i].cost = c;
		currentMax += c;
		i++;
	}
	qsort( edges, num*(num-1)/2, sizeof(edge), edgeCompare );
	for( i=0; i<num*(num-1)/2; i++ )
		edges[i].index = i;
	
	int* count = (int*)malloc( sizeof(int)*(num+1) );
	memset( count, 0, sizeof(int)*(num+1) );
	edge* stack = (edge*)malloc(sizeof(edge)*num );
	double r;
	//level -1
	for( i=0; i<num*(num-1)/2-num+1; i++ ){
		stack[0] = edges[i];
		count[stack[0].start]++;
		count[stack[0].end]++;
		if( (r=tsp( edges, stack, count, num, edges[i].cost, 0 ))>currentMax )
			break;
		}
	printf( "haha, let's make a test... total: %.1lf\n", currentMax );
	for( i=0; i<num; i++ )
		printf( "%d %d %lf\n", bestPath[i].start, bestPath[i].end, bestPath[i].cost );
}