求解等球packing 问题的两个策略
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(61070235, 61173180)


Two Strategies for Solving the Equal Sphere Packing Problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    为求解等球packing 问题,在拟物模型基础上提出两个启发式策略:伪球策略和序列对称换位策略.前者旨在保证获取精确解;后者则用于从局部最优布局出发搜索到紧凑的可行布局.在处理器为Pentium E6500 2.93GHz的PC 机上进行了实算.在球形容器内对多达200 个等球、在立方体内对多达150 个等球进行了紧密装填.结果在质量和算例数量上均显著改进了国际上已知最好记录.特别地,在半径小于5 的大球中装下了68 个半径为1 的等球,证明否定了一个猜想,其认为半径为5 的大球最多只能装下67 个半径为1 的等球.

    Abstract:

    Based on the quasi physical model, two heuristic strategies are proposed for dealing with the equal sphere packing problem. The fake sphere strategy guarantees that the results are rigorous. The serial symmetrical relocation strategy is designed to search a dense feasible configuration from a local optimal configuration. Through a personal computer with Pentium E6500 2.93GHz CPU, the study has densely packed up to 200 equal spheres in spherical container and up to 150 equal spheres in cubic container. The obtained results not only have better quality than that of the international best known records, but also greatly outnumbered them. Particularly, the study packed 68 equal spheres of radius 1 into a large sphere whose radius is smaller than 5, thus proved wrong a conjecture which alleges a large sphere of radius 5 can contain at most 67 equal spheres of radius 1.

    参考文献
    相似文献
    引证文献
引用本文

余亮,黄文奇.求解等球packing 问题的两个策略.软件学报,2012,23(9):2285-2296

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2011-07-09
  • 最后修改日期:2011-11-02
  • 录用日期:
  • 在线发布日期: 2012-09-05
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号