论文部分内容阅读
货郎担问题也称最小哈密顿回路问题。假设G（V，E，W）表示带权连通图G，其中V为图G的结点集，E为图G的边集，W表示图G的边上权的集合。货郎担问题就是求图G中使总权最小的、且通过每个结点一次而且仅一次的回路，也叫最小哈密顿回路。显然，若图G的n个结点表示n个村庄，边表示这n个村庄之间的道路，每条边上的权表示相应道路的长度，