中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
求解圆形packing问题的启发式方法
作者: 康雁
答辩日期: 2002
专业: 计算机软件与理论
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 启发式方法 ; 拟物拟人法 ; 圆形packing问题 ; 计算复杂性
其他题名: The Heuristic Methods for the Disks Packing Problem
摘要: 我们提出了有效地近似求解具有NP难度的圆形packing问题的启发式方法.该文所做的工作主要有:第一,得出了一个高效地近似求解圆形packing问题的快速拟物拟人算法.此算法比之于前人所得的最好算法,其效能有了显著的提高.对于困难的问题实例,在保持优度相等的前提下,其速度大致提高了10~100倍.第二,受物理世界中弹性物体运动规律的启发,得到了一个预测搜索前景的策略,它通过及早地终止将会陷入局部极小值陷阱的搜索,提高了搜索的效率;受自然界中优胜劣汰规律的启发得出另一个策略,它通过很好地利用人类在社会活动中积累的智慧,使搜索逃离局部极小值的陷阱,并走向更有前途的方向.结合这两个启发式策略以及拟物拟人法得到了快速拟物拟人算法.第三,在模拟物理世界中弹性物体运动的基础上,借鉴模拟退火法的思想,得出了二个启发式方法.这两个方法通过在搜索过程中以不同的规则接受不优于当前解的新解,使搜索有可能逃离局部极小值陷阱,从而有效地求解了等圆packing问题.第四,在用各启发式方法有效地求解大量实例的基础上,研究了启发式方法的工作原理,提出了设计启发式方法的可行的方案.
英文摘要: Now there does not exist an exactly effective method that can always provide an optimal solution for NP-hard problems within a reasonable time limit. Inspired by the wisdom of the nature and the human society, we present heuristic methods to effectively provide approximate solutions to one of the NP-hard problems, the disks packing problem. Most of our work was done as follows: Firstly, a fast quasi-physical and quasi-human algorithm, which can effectively provide approximate solutions to the disks packing problem, is obtained. The performance of this algorithm is obviously better than the best algorithm obtained so far. This algorithm's computational speeds on the difficult instances are between 10 and 100 times faster than those of the best algorithm, on the condition of keeping the quality of the solutions same. Secondly, inspired by the movement rule of the elastic objects of the physical world, a strategy that predicts the prospect of the search is obtained. It improves the performance of the search by early stopping the search that will get trapped in local minima; Inspired by the survival of the fittest principle of the nature, another strategy lets the search escape from local minima to the direction of better prospect by using the wisdom that human has accumulated in social events. The fast quasi-physical and quasi-human algorithm is obtained as the integration of the above two methods and the quasi-physical and quasi-human algorithm. Thirdly, based on simulating the elastic objects movement, two heuristic algorithms are presented by using the idea of the simulated annealing algorithm. By accepting the new solution, whose quality is not better than the previous one, according to the different rules, the above two algorithms are possible to let the search escape from local minima and thus effectively solve the equal disks packing problem. Finally, by effectively using obtained heuristic methods to solve a lot of instances, we study the working principle of the heuristic methods, and present a feasible plan to design the heuristic methods.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/7472
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW011199.pdf(2354KB)----限制开放-- 联系获取全文

Recommended Citation:
康雁. 求解圆形packing问题的启发式方法[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2002-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[康雁]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[康雁]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace