欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
位置：立项数据库 > 立项详情页
中文摘要：
NP难度问题的求解是国际公认难度大、有重大影响的基础性问题。本项目深入地研究了NP难度问题求解的新型计算理论及算法- - 拟物拟人方法。作为工作的介质与靶子，用拟物方法研究典型的NP难度问题- - 著名的等圆Packing问题，用拟人方法研究另一个典型的NP难度问题- - 著名的长方体Packing问题。不同于国际上流行的遗传退火等启发式算法，我们找出物理世界和人类社会中与原始问题等价的具体现象，观察体会这些现象的演进方式以及社会的人在其中表现出的智慧，受到启发经形式化后得出求解原始问题的确切算法。所得算法之性能指标普遍地超过了国内外学术界目前已达到的最高纪录。对于等圆Packing问题，在N<=200的算例上有72个找到了比此前国际最优记录更优的记录，且其中有64个仍保持为现在的国际最优记录。对于长方体Packing问题，在16组共1600个BR算例和1组共15个LN算例上均找到了好于前人的结果，且在LN算例和8组BR算例上仍保持为现在的国际最优纪录。本项研究说明对于公理化纯粹数学不可解的重大问题，经过大自然与人的智慧仍然可能得出现实生活中令人非常满意的解答。
结论摘要：
英文主题词NP-hard; algorithm; packing problem; quasi-physical; quasi-human
成果综合统计
期刊论文
会议论文
专利
获奖
著作
期刊论文
相关项目
黄文奇的项目
