矩形Packing基本问题的高性能求解算法-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

矩形Packing基本问题的高性能求解算法

项目名称：矩形Packing基本问题的高性能求解算法
项目类别：面上项目
批准号：10471051
申请代码：A011202
项目来源：国家自然科学基金
研究期限：2005-01-01-2007-12-31

项目负责人：许如初
负责人职称：副教授
依托单位：华中科技大学
批准年度：2004

中文摘要：

研究如下问题的求解算法已知一个矩形容器及有穷个矩形块各自的长和宽（正整数）。要求尽可能多地将这些矩形块互不重叠地放进容器中去。多的含义是指放进去的诸块的总面积尽可能地大。各矩形块的放置方向应是其边平行于容器的边。这是一个纯粹的矩形Packing（装填）问题。他具有NP难度，当今世上不存在既高质量又高速度的精确求解算法。但他是关于切材下料的一类核心问题，而切材下料又是许多工业部门施工设计的一个瓶颈。将此Packing问题的高性能求解算法加以应用将显著地加快这些施工设计的周期，降低产品的成本，增加部门的经济效益。对NP难问题求解的有关哲学和技术，项目主要成员已潜心研究28年，提出了独创的拟物拟人途径，并已对若干Packing问题取得了显著成绩，现在来求解此具体问题条件已经成熟，预计能研制出当今国际领先水平的高性能求解算法。

中文主题词： Packing问题；切材下料；NP难度；算法；拟人

英文摘要：

packing problem; cutting and b

英文主题词： packing problem; cutting and b

结论摘要：

研究如下问题的求解算法已知一个矩形容器及有穷个矩形块各自的长和宽（正整数）。要求尽可能多地将这些矩形块互不重叠地放进容器中去。多的含义是指放进去的诸块的总面积尽可能地大。各矩形块的放置方向应是其边平行于容器的边。这是一个纯粹的矩形Packing(装填)问题。他具有NP难度，当今世上不存在既高质量又高速度的精确求解算法。但他是关于切材下料的一类核心问题，而切材下料又是许多工业部门施工设计的一个瓶颈。将此Packing问题的高性能求解算法加以应用将显著地加快这些施工设计的周期，降低产品的成本，增加部门的经济效益。对NP难问题求解的有关哲学和技术，项目主要成员已潜心研究30年之久，提出了独创的拟物拟人途径，并已对若干Packing问题取得了显著成绩，2005年正式求解此具体问题条件已经成熟。对此问题现在已经研制出其性能指标为当今国际领先纪录的求解算法。本项研究另外还有重大理论科学的意义，她说明了对于公理化纯粹数学不可解的重大问题，经过人的经验和智慧仍然可能得出现实生活中令人非常满意的解答。

成果综合统计