图论--旅行商问题
五一果然基本献给了数据压缩（除了两个晚上用于打球），看了小波的一些理论，看了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 indextypedef struct {int start;int end;double cost;int index;}edge;//record the optimum routeedge* bestPath;//the function for qsortint 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 = stack;}return currentMax;}for( i=stack.index+1; i<n*(n-3)/2+level+2; i++ ){//if the edge is unproper, no further tsp is performed to this nodeif( count.start]+1 < 3 && count.end]+1 < 3 ){stack = cost;count.start] ++;count.end]++;current += cost.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 nodeif((r = tsp( cost, stack, count, n, current, level+1 )) > currentMax )return currentMax;//restore after recursive callcount.start]--;count.end]--;current -= cost.cost;}}return currentMax;}main(){int num, s, e, i;double c;edge* edges;//the graph is construct by user inputprintf( "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.start = s;edges.end = e;edges.cost = c;currentMax += c;i++;}qsort( edges, num*(num-1)/2, sizeof(edge), edgeCompare );for( i=0; i<num*(num-1)/2; i++ )edges.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 -1for( i=0; i<num*(num-1)/2-num+1; i++ ){stack = edges;count.start]++;count.end]++;if( (r=tsp( edges, stack, count, num, edges.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.start, bestPath.end, bestPath.cost );}
页:
[1]