求解等圆packing问题的高性能近似算法

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:ZXFAMD
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
等圆packing问题是一类非常典型的NP难度问题,它不仅在工程上有广泛的应用,更具有特殊的理论意义。20世纪70年代至今的计算复杂性理论表明,对于NP难度问题可能根本就不存在多项式时间复杂度的求解算法,于是人们使用各种启发式算法求此类问题的近似解。拟物算法最早由黄文奇教授提出,其基本的思路是设计算法模拟自然界弹性物体的挤压运动。实践证明拟物算法在求解一些NP难度问题是非常有效的,这里使用拟物算法求解等圆packing问题就是一个很好的例子。在建立物理模型,并给出严格的数学定义后,设计出了模拟弹性实体相互挤压运动过程的算法,即求解问题的原始拟物算法。.在势能函数的基础上,结合众所周知的最速下降法,得到了求解问题的拟物最速下降算法。在使用拟物算法求解问题时,计算经常会落入局部最小值点。针对这个问题,提出了三种拟人策略:压力解除策略,资源让与策略,最痛苦者自救策略。在拟物算法的基础上,分别结合这三种拟人策略,得到了几个不同的拟物拟人算法。最后,通过典型的算例验证了几种算法的性能。
其他文献
图形用户界面(GUI)被广泛地应用于应用软件中,但其大量使用也为软件的开发和测试带来了极大的挑战。在今天的软件开发中,GUI可占到全部代码60%以上。因此,GUI测试在软件开发
随着网络技术的快速发展,作为Internet基石的TCP/IP协议族正进行着一场前所未有的变革。这场变革的起因是IPv4协议在面对Internet发展时出现越来越多的不足,人们为解决这些不
随着Agent技术的不断发展,Agent的应用已逐渐深入到了各个领域。Agent所执行任务的难度以及应用环境的复杂度也在不断增加,单个Agent已经不能满足应用的要求,多Agent系统研究
网络教育的教学效果很大程度上取决于采用的教育技术。利用网络教学平台提供同步或者异步的教学辅导、答疑是网络教育提供给学生的学习支持服务的主要形式之一。而目前我国的
泛函网络是对人工神经网络的一种有效推广,但有些理论还不太健全,需要人们不断地提出新的模型和新的算法,完善基础理论,以便进一步拓展泛函网络的应用范畴。本文从计算方法的角度
随着Java软件平台技术的不断发展,Java软件的应用已经从桌面的应用延伸到企业平台,大型信息系统,控制系统,嵌入式系统等各个方面。但由于Java软件体系结构的特点决定了Java软
RIA(Rich Internet Application,丰富互联网应用程序)模式是一种新的软件设计方式,它为电子商城平台的发展注入了新的力量。电子商务平台共同存在以下缺点:1、购物流程复杂,顾客
本文介绍了当前网络安全的现状,对传统的防火墙进行了研究,介绍了传统防火墙的发展史,基本特性以及传统防火墙的主要缺陷,分析了国内外智能防火墙技术的发展状况,智能防火墙
网格的目标是整合地理上分布的资源为用户提供各种服务,因此,如何有效地发现资源、利用资源成为网格研究领域中的关键技术。本文将协商模型引入到基于经济的网格资源管理方法
智能化的多运动目标检测与跟踪系统可以大量减少工作人员,提高工作效率,极大的提高监控系统的性能,是计算机视觉领域非常活跃的一个研究方向。目前在安防、军事、医疗领域具