大数据

当前位置:首页 > 大数据

《算法导论》第三十四章(续8)

34.5.4 旅行商问题

旅行商问题与哈密顿回路问题有着密切的联系。在该问题中,一个售货员必须访问n个城市。如果把该问题模型化为一个具有n个顶点的完全图,就可以说这个售货员希望进行一次巡回旅行,或经过哈密顿回路,恰好访问每个城市一次,并最终回到出发城市。这个售货员从城市i到城市j的旅行费用为一个整数c(i,j),旅行所需的全部费用是他旅行经过的各边费用之和,而售货员希望使整个旅行费用最低。例如,在图34-18中,费用最低的旅行路线是(u,w,v,x,u),其费用为7,与旅行商问题对应的判定问题的形式语言是:

TSP-{<G,c,k>:G=(V,E)是一个完全图,c是v xV→Z上的一个函数,k ∈ z,G中包含一个最大花费为k的旅行回路}

《算法导论》第三十四章(续8)

下面的定理说明不太可能存在一种关于旅行商问题的快速算法。

定理34.14  旅行商问题是NP完全的。

证明︰  首先来说明TSP属于NP。给定该问题的一个实例,用回路中n个顶点所组成的序列作为证书。验证算法检查该序列是否恰好包含每个顶点一次,并且对这些边的花费进行求和后,检查和是否至多为k。这一过程是可以在多项式时间内完成的。

为了证明TSP是NP难度的,我们先来证明HAM-CYCLE≤pTSP。设G=(V,E)是HAM-CYCLE的一个实例。构造TSP的实例如下。首先建立一个完全图G'=(V,E'),其中E'={(i,j): i,j∈V,i≠j},定义费用函数c为:

c(i,j)=0若(i,j)∈E

(注意,由于G是无向图,所以它没有自环路,因而对所有顶点v∈V,都有c(v,v)=1。)于是(G',c,O>就是TSP的一个实例,它可以轻易地在多项式时间内产生。

现在,我们来说明图G中具有一个哈密顿回路,当且仅当图G中有一个费用至多为0的回路。假定图G中有一个哈密顿回路h,h中的每条边都属于E,因此在G中的费用为0。因此,h是G中费用为0的回路。反之,假定图G中有一个费用至多为0的回路h'。由于E中边的费用只能是0或1,故回路h'的费用就是0,且回路上每条边的费用必为0。因此,h'仅包含E中的边。综上,我们可以得出结论,h'是图G中的一个哈密顿回路。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~