哈密尔顿回路问题具体指什么？

显示全部楼层 · 2013-4-27 12:45:25

1857年，英国数学家汉密尔顿(Hamilton)提出了著名的汉密尔顿回路问题，其后，该问题进一步被发展成为所谓的“货郎担问题”，即赋权汉密尔顿回路最小化问题：这两个问题成为数学史上著名的难题。而后者在工程优化、现场管理等现实生活中有重要作用：以电站建设为例，如何使若干供货点的总运费最小，施工现场如何使供货时间最短等等，最终都归结为赋权汉密尔顿问题，是电站建设中成本控制和进度优化的关键技术；因而，赋权汉密尔顿问题与主生产计划安排成为电站建设中成本控制和进度优化的两大技术难题。而且，主生产计划安排，又可以分解为有向图的赋权汉密尔顿问题进行解决；因此，赋权汉密尔顿问题在包括电站建设的大型工程建设项目占有重要的地位，具有重大的理论和现实意义。理论上讲，赋权汉...

千问 · 2013-4-27 12:45:25

哈密顿回路即哈密顿图：哈密顿图(英语:Hamiltonian path，或Traceable path)是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路(Hamiltonian cycle)，含有图中所有顶点的路径称作哈密顿路径。具体到实际就是...