^3^ ΔTSP 2017.5.11 张子谦.

Presentation on theme: "^3^ ΔTSP 2017.5.11 张子谦."— Presentation transcript:

1 ^3^ ΔTSP 张子谦

2 找出一个Δ-TSP问题的近似解，并证明这个解的近似度界，说明这个问题是NPO的哪一类问题？
TSP问题（Travelling Salesman Problem) 设G是具有n个城市的地图，旅行商从其中某一城市出发周游，遍历每个城市1次恰好1次后回到出发地，求其最短的周游路线。亦即，求一条最短的哈密顿回路(Hamiltonian Cycle，简称HC)。 因为边的长度可以为无限大，因此不妨设G为边加权的无向完全图。下面只 考虑TSP的特殊版本：满足三角不等式的ΔTSP（Metric TSP）问题。

3 解决ΔTSP问题两种算法： MST启发（2近似） & CH启发（1.5近似）

4 MST启发式： 基于MST启发的ΔTSP的近似算法： 求G的任一MST T； 重复T的边构造一欧拉环ET； 从ET产生一哈密尔顿圈。
Def1 设G是一个多重图，G的一条欧拉路是一条经过每个顶点至少一次、 经过每条边恰好一次的周游路线。 Th1 一个多重图G有一个欧拉环当且仅当G连通且所有顶点的度数为偶数 (易在多项式时间内构造一个欧拉环）。

5 Alg. MST： Input：G(V,E)和距离函数d Output：G里的一个哈密尔顿圈 1.在G里找一棵最小生成树T；
B C E 1.在G里找一棵最小生成树T； 2.通过将T的每条边复制一copy构造一多重图T’； 3.在T’中找一欧拉圈ET； 4.通过短路欧拉路的方法构造哈密尔顿圈HC： 从任一顶点出发，沿着欧拉圈前进，遇新顶点则访问，遇到重复顶点 则直接跳到下一未访问过的顶点，最终回到出发点即可。 ET： ABCBDBAEA； HC：ABCDEA

6 下面证明： 用MST启发解ΔTSP时，为2近似，即 Pf：
∵T’连通且每个顶点度为偶数，故可找到欧拉环；在完全图的假定下，step4产生一个哈密顿圈。 若H是G的边集，则d(H)表示H里所有边的长度之和。 ∵任何哈密尔顿圈去掉1条边后都是1棵生成树 ∴ 短路过程确保: 因为短路是用1条非欧拉边取代2或多条欧拉边， 三角不等式保证其成立。故有：

7 下面证明： CH启发(Christofides)
避免从MST T到欧拉环的双边，为T的每对奇度顶点加 一条边使之度数为偶数。∵T中所有顶点度数之和为2|E|， ∴奇度顶点总数为偶数。 V(G)的子集S的一个匹配是E(G)的一个子集（边独 立集），其中所有边的端点集恰为S，S中每个顶点 恰好依附匹配集中的一条边。∵G是完全图，故任一 S均存在一个匹配(|S|为偶数)。已证明，可在多项式 时间内找到S的一个最小权匹配。 下面证明：

8 Pf： (由Δ不等式决定) 设M是T中奇数点集O上的最小权匹配集，则有：
在1个最优解中做短路操作以排除不在O中的顶点，所得的圈X(O上的圈) 必满足： (由Δ不等式决定) ∵T中奇度顶点是偶数个, ∴|O|=m为偶数。 O上圈有m条边，但是O上的一个匹配集只有m/2条边，故 该圈是2个匹配集之并。 点集O上的圈必是O的两个匹配集的并。

9 这两个匹配集之一的权必定至多是圈X的一半，而M是O的 最小权匹配集，故有：
A T B E 例：O={B,C,D,E}.匹配M1={(B,E),(C,D)}, M2={(B,C),(D,E)}.M1∪M2是O上圈 C D ∵图T∪M中所有顶点度为偶数，∴可从其构造欧拉环ET 用短路法从ET构造HC不会使权增加，故有： ，即：

10 两种算法比较： 近似比1.5是目前最好的结果，但是要找一个最小权 值匹配需要O(n3)时间，而MST启发的运行时间几乎是线 性的(求MST除外)。

11 属于第几类NPO问题？

12 谢谢~