K-TSP问题的近似算法

Approximative Algorithms of K-TSP

利用△TSP问题的Christofides算法及其在K TSP问题上的扩展 ,通过权函数变换c′ij=cij-ui-vj 使c′ij>0 ,c′ik+c′kj≥c′ij,给出了求解K TSP问题的有效途径 ,得到了目标函数的更好的界值估计 ,C(Ha)≤λ(n)C(H ) -(λ(n) -1 ) {(k-1 )c11+∑ni=1 cii}.

Using christofides heuristics of △TSP and it′s extension to K TSP, We give an effective method to solve K TSP by a transformation of weighted matrix (c ′ ij =c ij -u i-v j, c ′ ij ≥0, c ′ ik +c ′ kj ≥c ′ ij , k≠i, j) and get a well estimation of bounds of objective function C(H a)≤λ(n)C(H *)-(λ(n)-1){(k-1)· c 11 + ni=1c ii }.