求解等圆packing问题的拟物拟人算法

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:myh8888
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
等圆Packing问题是一类典型的NP-Hard问题。拟物拟人算法源自客观世界和人类社会所蕴含的高度智慧,是求解等圆Packing问题的高效率启发式算法。拟物算法的思路与传统的数学模型恰恰相反:首先将待解决的纯粹数学问题转换成等价的物理模型,然后在客观规律的启发下求解该物理模型,最后将所得解转换成原数学问题的解。对于等圆Packing问题,拟物算法在体系中引入弹性力的概念,让体系在其作用下天然地向着更优的方向演化,最终找到问题的解。为提高效率,可在执行拟物算法的过程中引入“安乐死”策略。该策略不断估算当前搜索路径的希望大小,如果希望渺茫,则提前结束对当前路径的搜索,从而节省计算时间。当求解的问题较困难时,仅采用拟物算法往往会陷入“局部陷阱”。为此,可借鉴人类社会的经验,设计出一系列跳离“局部陷阱”的拟人算法,包括“调走最痛苦者”、“解救最痛苦者”、“全局调整法”等。其中,“解救最痛苦者”方法是对“调走最痛苦者”方法的有效改进。将拟物算法与拟人算法结合起来便得到拟物拟人算法。对于等圆Packing问题,拟物拟人算法在N=1—100这100个算例中的79个上找到了与国际纪录精度持平的解。
其他文献
频繁模式挖掘是数据挖掘领域的一个基本问题,其研究范围包括事务、序列、树和图。其方法被广泛应用于许多其它数据挖掘任务中,如相关性分析,周期分析,最大模式,闭合模式,查询,分类,索
20世纪末以数字化为核心的高速发展的信息技术,促使了教育信息化的迅速发展。在国内外高校教育中产生了前所未有的教学模式和教学方法的创新。上世纪90年代问世的大学物理仿真
电子邮件和网络上的文件传输已成为生活一部分,但是随网络技术突飞猛进,黑客技术也蓬勃发展,使得邮件的安全问题日益突出。总所周知,Internet传输的数据是不加密,如不保护自
隐马尔可夫模型(Hiddell Markov Model)是一种双随机过程,被广泛地应用于模式识别和聚类中并取得了不小的成功。HMM有坚实的统计学基础和有效的学习算法,从而在应用科学中成为
本文介绍了遥感图像分割算法及区域生长算法的优缺点,针对遥感图像分割计算量大和区域生长遥感图像分割算法中合并策略、尺度选取的问题展开了讨论。针对遥感图像数据量大和噪
无论是在研究领域还是在商业化的系统中,R-Tree都是应用最为广泛的空间索引之一,它是地理信息系统中相当核心的一个研究方向。自1984年Guttman提出R-Tree以来,有大量针对其不足
随着电子商务、电子政务的飞速发展,网上办公愈来愈普遍,各个公司组织内部及之间需要频繁传递电子文件,特别是一些重要敏感度高的文件和签章,更需要严格的保护。对安全、高效的电
随着Internet的迅速发展,电子邮件逐渐成为信息交流的主要媒介之一,而近年来,垃圾邮件的泛滥愈演愈烈,如何有效地治理它已成为棘手的问题。本文提出一种可信的反垃圾邮件网格
双语语料库在基于实例的机器翻译,翻译知识的获取,双语词典的建立,词义消歧等领域有着重要的应用价值。大规模双语语料库的建设是进行基于语料库研究的基础。如何通过现有的
我国地大物博,海洋资源极其丰富。我国目前的海洋开发活动,主要集中在狭窄的海岸带和沿岸海域。随着海洋开发的深入,各行业开发活动与海洋资源以及生态环境之间存在很多矛盾。各