计算机算法分析与设计

我们在求解一个问题的时候，不应当只是逐个尝试各个算法技术或者纯粹依赖于灵感，而是应该依赖于我们对问题结构的认识，思考问题应该沿着“实际问题-----抽象出的数学问题------算法设计”这一脉络。怎么感觉有点像运筹学呢？？

问题结构与基本算法思想

方法：

分析：

TSP旅行商问题

1925年，一个公司的销售员需要走过350个城市，每一次只能走一次，将商品销售给不同城市的人，那么他就要知道怎么走才能使路程最短并且所有的城市都走一遍。
INPUT：n cities V={1,2,…n},and a distance matrix D.where d denotes the distance between city i and j;
OUTPUT:the shortest tour that visits each city exactly once and returns to the origin city.

分治策略

Decompose the original problem into subproblem

方法一 : 我们用M(S,e)表示从1这个点开始，经过S，到达e。例如M（{2}，3）意思是从1出发经过2点到3.
那么整个问题域就分成了：

上面公式的意思是走过所有的路可能有三种方法，可能是D21（从2走到1），然后从1出发，经过3，4点到达2。剩下的两条路照推。
在这其中最小的问题是M（{2}，3）=D12+D23=6
那么：M（{2，3}，4）可以分解为
min{D34+M({2}，3)，D24+M({3}，2)}


伪代码：

方法二：Improvment Strategy
Strat from a rough complete solution，and try to improve it step by step。
但是这样很麻烦就不说了。
方法三，Intelligent enumeration strategy智能枚举
令x1=1表示边为1的路线已经走过，=0的边为不走
Examp：a–>b–>c–>d–>e–>a ，可以表示为：X={1，0，0，1，1，0，0，1，0，1}

现在画一下部分决策树

但是这种方法是 NOT　EFFICIANT！！！没有效率啊
所以我们相处一个办法，先求下界，也就是我走这些旅程最少最少要多少。
　对与每一城市沃恩选择两条最短的距离，将这些２ｎ个距离加起来除以２就是我们最少的距离。
　（５＋６＋８＋７＋９）／２＝１７．５
　即１７.５为下界，最少不低于１７.５的路程。
　if　ｘ＝１，０，？，？，？，，，，，？，计算的结果为（５＋６＋９＋７＋９）／２＝１８
　因此：
　
　
　
　按照左边的做法，将右边的决策树补齐就是：