论文部分内容阅读
哈密尔顿路问题是一类经典的组合优化问题。我们考虑哈密尔顿路问题的一个推广形式，即k-人哈密尔顿路问题:给定一个无向边赋权度量完全图G=（V, E;w），其中w:E→R+，及一个正整数k，要寻找一个由k条子路构成的集合(P)={P1，P2,…，Pk}，这k条子路满足条件:(1)对每个i=1，2,…，k，Pi均以v为起点，并且Pi是至少包含一条边的简单路;(2)对于每一个顶点u∈V-{v}，存在唯一一条子路经过顶点u。目标是使得这k条子路的长度之和达到最小，即w（(P)）=∑ki=1w（Pi）达到最小。我们得到的下面结果:k-人哈密尔顿路问题是一个NP-完备性问题，设计了一个2-近似算法解决它，此算法的时间复杂性为O(|V|3)，并且对这个算法进行了程序实现。