算法经典题TSPNPC背包排工团等.pdfVIP

33算法经典22题(TSP、NPC、背包、排工、团等)

一、设L为n元数组，其中的数已按增序排列，另给定数值x，试采

用二分有哪些信誉好的足球投注网站技术设计算法，查找数值是否在L中。要求若x在L中，

则输出j，使L(j)=x；其x不在L中，则输出0。并证明，在最坏情

况下，对所有n元数组L(n≥1)，二分有哪些信誉好的足球投注网站算法将数值x与L中元素

比较次数为logn1。



2

解：

1、l1,rn

2、if(lr)j0转6

lr

3、j2

4、if(xl(j))转6

5、if(xl(j))则lj1，否则rj1，转2

6、输出j，结束

比较次数：由于是2分有哪些信誉好的足球投注网站，每次比较或者成功，或者将有哪些信誉好的足球投注网站范

围缩小一半。因此最多比较次数为2的对数，又当时，至少比较

n1

logn1

1次，所以比较次数不超过。

2

二、满足三角不等式的TSP问题是否是NPC？为什么？

解：证明思路，将哈密顿回路HC问题多项式变换到TSP问

题:HCTSP，且变换到TSP问题的实例是满足三角不等式的。因为

HCNPC，故满足三角不等式的TSPNPC。

多项式变换：HCTSP

设HC的实例为GV,E,V{VVV}，据此构造TS实例

1,2,m



GV,E,VV,(G必为完全图)，两个顶点之间的距离定义为

1i,jE

di,j

2i,jE，并设TSP旅游界值为Bm。

1/27

33算法经典22题(TSP、NPC、背包、排工、团等)

易知这个变换是多项式的。

若HC存在一条哈密顿回路，则这条回路在上的长度必为B，

G

而Bm是最短旅游的界值，故这条回路是满足实例的一个TSP旅游。

若存在一个满足B的TSP旅游，则该旅游必经过长度为1的边，

G

而这些边均在G上，因此这个TSP旅游在G上是一条HC回路。

这样就将HCTSP，而HCNPC。

变换到的TSP实例的边长为1或2，可知该实例满足三角不等式，

这就证明了满足三角不等式的TSP问题是NPC问题。

三、给定城市集合C{CC}，任两城市距离

1n

d(i,j),d(i,j)d(i,k)d(k,j)，求最小货郎旅游。试证明满足三角不等式

的货郎优化问题为NP-hard。求满足三角不等式的TSP的近似算法，

并设计出能解答该问题的多项式时间近似算法A，其近似性能比为

3

R。

A2

证明：即满足三角不等式的TSP问题。

证明思路，将哈密顿回路HC问题多项式变换到TSP问

题:HCTSP且变换到TSP问题的实例是满足三角不等式的（见第1

题）。因为HCNPC，故满足三角不等式的TSP问题是NPC问题。

设存在TSP优化问题求解算法，设计TSP判定问题的算法如下：

A

对于给定TSP判定问题的实例：G,d,k，调用A(G,d)，求得城市

m**

d(C,C)k