对“货郎担问题”的深入解析

1.问题的提出'货郎担问题'是世界难于解决的著名难题之一,至今仍有不少学者在研究它.最早由K.Menger提出该问题的基本描述是:某售货员要到若干个村庄售货,各村庄之间的路程是已知的,售货员从他所在的商店出发,到各村庄售货一次然后返回商店.

货郎担问题的近似算法

利用集合运算求解货郎担问题的近似解。该方法所构造的算法对有ｎ个结点，ｅ条边的无向连通网络，寻找出精度较高的一条货郎担近似回路。它的平均复杂性为Ｏ（ｅＧ（ｎ））（当ｎ＜２１６时，Ｇ（ｎ）≤３）。