所谓货郎担问题是指,给定一个无向图,并已知各边的权,在这样的图中,要找一个闭合回路,使回路经过图中的每一个点,而且回路各边的权之和为最小,如右图所示.如a,b,c,d,e,f这6个点,坐标分别为(0,0),(4,3),(1,7),(15,7),(15,4),(18,0),这是最优解.(算法程序略)求解步骤一般如下:计算各点间距离(邻接矩阵);距离关系表排序;贪婪法选择边,入选的边应符合如下两条件:每个端点不能联系两条以上的边;不会使入选的边形成回路,除非入选正好是边数等于端点数.为此引入端点关系表如果由(3)得不到解,应调整距离关系表中距离相同的边的次序,再试;若有解,则按端点关系表给出回路的轨迹.
|
