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

<正> 1.问题的提出“货郎担问题”是世界难于解决的著名难题之一,至今仍有不少学者在研究它。最早由K.Menger提出该问题的基本描述是:某售货员要到若干个村庄售货,各村庄之间的路程是已知的,售货员从他所在的商店出发,到各村庄售货一次然后返回商店。为了提高效率,求出他应选择一条总路程最短的线路。根据此描述,用图论方法给出了如下的形式描述:设G（V,E）是一个具有边成本为Cij的有向图,V是G的结点集,E是G的边集,i和j为图中结点标号,Cij的定义如下:对于所有的i和j,Cij>0。若（i,j）∈E,则Cij为该边的成本,若（i,j）E,则Cij=∞。令|V|=n,并假定n>1。G的一条周游路线是包含V中每个结点的一个有向环。周游路线的成本是此路线上所有边的成本和,货郎担问题是求具有最小成本的周游路线,即最优货郎担问题。