哈密尔顿圈(货郎担问题）的解法pascal

来源：百度知道 编辑：UC知道 时间：2024/06/14 11:30:54
重点是算法！最好有短，又高效。。
甚至。。可以不写程序！

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