图论--旅行商问题
五一果然基本献给了数据压缩（除了两个晚上用于打球），看了小波的一些理论，看了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回路权重大了，再往下或往右搜索肯定是更大的，所以整个父结点都不需要搜索了。
?
不知道我把问题解释清楚了没有？
?
其实之前看书里的解题思路的时候，我还不是这么想的，在实现的过程中递归到我自己也迷糊了，最后才提炼出来这样的结果的，呵呵。我还是不大会递归啊。
?
最后看一下实现的代码：
?
?
