检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

求解等球packing问题的两个策略

软件学报 2012年第9期23卷 2285-2296页

作者：余亮黄文奇华中科技大学计算机科学与技术学院湖北武汉430074

为求解等球packing问题,在拟物模型基础上提出两个启发式策略:伪球策略和序列对称换位策略.前者旨在保证获取精确解;后者则用于从局部最优布局出发搜索到紧凑的可行布局.在处理器为Pentium E6500 2.93GHz的PC机上进行了实算.在球形容器... 详细信息

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

关键词：等球packing问题拟物模型启发式伪球策略序列对称换位策略

求解二维矩形Packing面积最小化问题的动态归约算法

在线全文

学校读者我要写书评

暂无评论

软件学报 2013年第9期24卷 2078-2088页

作者：何琨姬朋立李初民华中科技大学计算机科学与技术学院湖北武汉430074 School of Computer Science and Technology University of Picardie Jules Verne

二维矩形Packing面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RP... 详细信息

二维矩形Packing面积最小化问题(rectangle packing area minimization problem,简称RPAMP)是具有NP难度的高复杂度的布局优化问题,也是大规模集成电路设计中floorplanning问题的一个核心问题.通过动态构造矩形框的宽和高,将求解一个RPAMP转化为求解一组二维矩形Packing判定问题(rectangle packing decision problem,简称RPDP).在求解RPDP的最大适配度算法的基础上,进一步考虑了当前动作对全局紧凑性的影响,评估了当前动作对局部空间的损害程度,设计了求解RPDP的最小损害度算法.然后,结合矩形框宽、高的动态构造方法,设计得到求解RPAMP的最终算法.对15个相关的RPAMP算例(包括著名的MCNC算例和GSRC算例)进行了测试.更新了其中9个算例的最好记录,另有2个与当前的最好记录持平.得到了98.50%的平均填充率,将国内外文献中已见报道的最高平均填充率提高了0.85%.

关键词： NP难度布局优化布图规划面积最小化启发式

动作空间带平衡约束圆形Packing问题的拟物求解算法

在线全文

学校读者我要写书评

暂无评论

软件学报 2016年第9期27卷 2218-2229页

作者：何琨杨辰凯黄梦龙黄文奇华中科技大学计算机科学与技术学院湖北武汉430074

对于一个以卫星舱内设备布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形Packing问题,提出了基于动作空间的拟物求解算法.在拟物下降遇到局部极小点的陷阱时,如何找到当前格局下的最空闲空间以使搜索过程跳到更有前景的区域... 详细信息

对于一个以卫星舱内设备布局为背景的具有NP难度的全局优化问题——带平衡约束的圆形Packing问题,提出了基于动作空间的拟物求解算法.在拟物下降遇到局部极小点的陷阱时,如何找到当前格局下的最空闲空间以使搜索过程跳到更有前景的区域去是设计跳坑策略的一个关键难点.借鉴求解矩形Packing问题中动作空间的概念,通过化"圆"为"方",将不规则的空闲空间近似为一系列规则的矩形空间,从而有效地解决了此难点.另外,将拟物法与提前中止、粗精调和自适应步长这3个拟人辅助策略相结合,以提高势能下降的效率.对3组共13个代表性算例的计算结果及与国内外代表性算法的比较表明,所提格局的外包络圆半径多为最小或次小,且在部分算例上找到了有更小外包络圆半径的格局,总体计算结果较好,且静不平衡量的精度较高.

关键词： NP难度圆形Packing 拟物动作空间平衡约束

基于优化冲突集提高下界的MAXSAT完备算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2013年第10期36卷 2087-2095页

作者：刘燕丽李初民何琨华中科技大学计算机科学与技术学院武汉430074 武汉科技大学理学院武汉430081 亚眠大学计算机科学系法国80033

最大可满足性问题(MAXSAT)是经典的NP完全问题SAT的一个扩展问题.基于分支限界设计MAXSAT完备算法时,如何有效地提高下界是设计高效算法的关键和难点.基于优先找到规模小、结构简单的冲突集的思想,在Maxsatz算法的基础上,提出了改进的算... 详细信息

最大可满足性问题(MAXSAT)是经典的NP完全问题SAT的一个扩展问题.基于分支限界设计MAXSAT完备算法时,如何有效地提高下界是设计高效算法的关键和难点.基于优先找到规模小、结构简单的冲突集的思想,在Maxsatz算法的基础上,提出了改进的算法Maxsatz2013.通过使用推理规则优先、改变单子句的传播顺序、进一步失败文字检测这3个优化策略,增加了检测到的冲突集数,从而有效地提高了下界.测试了MAXSAT 4个类别共800多个算例.实验结果表明,这3个优化冲突集的策略是可行且有效的,所提出的算法在每一类算例上均明显地提高了计算效率.

关键词： NP完全最大可满足性问题单子句传播推理规则失败文字

四维时空高效利用的装箱调度问题及其可计算性证明

在线全文

学校读者我要写书评

暂无评论

计算机学报 2013年第9期36卷 1880-1888页

作者：黄文奇何琨华中科技大学计算机科学与技术学院武汉430074

提出了四维时空中考虑时间因素的一个长方体装箱工作的优化调度问题.已知一个形状大小任意给定的长方体形的箱子和有限个形状大小分别任意给定的长方体形的刚性物体,又知每个物体须在箱中连续烘烤的时间长度,问应如何安排每个物体的入... 详细信息

提出了四维时空中考虑时间因素的一个长方体装箱工作的优化调度问题.已知一个形状大小任意给定的长方体形的箱子和有限个形状大小分别任意给定的长方体形的刚性物体,又知每个物体须在箱中连续烘烤的时间长度,问应如何安排每个物体的入箱时刻,以及至出箱前这段时间内它在每个时刻上的位置和方向,才能使整个箱子的被使用时间最少.问题中涉及的箱子及诸长方形刚体的长、宽、高以及各刚体须连续烘烤的时间长度均为分别任意给定的正实数.与经典装箱问题的不同之处在于,各物体在箱子内可以随时间而改变其位置和方向,从而使四维时空得到更真实、更充分的利用.进一步地,通过枚举长方体的各种排列,并证明对每一种排列,按照某种贪心策略可得到该排列下问题的最优解,从而给出了原问题具有可计算性的严格证明.在此基础上,今后有望对此问题发展出各种有效的实用求解算法.

关键词：可计算性装箱调度优化 NP难度

在线全文

学校读者我要写书评

暂无评论

球形容器内等球装填问题的启发式算法

华中科技大学学报（自然科学版） 2012年第12期40卷 23-27页

作者：黄文奇余亮华中科技大学计算机科学与技术学院湖北武汉430074

为了在球形容器内紧密装填n个等球,设计了序列对称换位策略,将其与拟物算法结合得到一个有效的启发式算法.序列对称换位策略每次从一个局部最优布局出发,通过对称换位此局部最优布局的不同真子集得到n(n-1)/2个不同的新布局,并用拟物算... 详细信息

为了在球形容器内紧密装填n个等球,设计了序列对称换位策略,将其与拟物算法结合得到一个有效的启发式算法.序列对称换位策略每次从一个局部最优布局出发,通过对称换位此局部最优布局的不同真子集得到n(n-1)/2个不同的新布局,并用拟物算法检查这些新布局.此启发式算法只须检查O(n2)个布局,即可找到一个紧凑的可行布局.所找到的最好结果显著改进了目前best known记录,并证否了半径为5的球形容器至多只能装填67个半径为1的等球的猜想.

关键词： NP难度等球装填问题启发式拟物算法序列对称换位策略

基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2013年第6期36卷 1224-1234页

作者：何琨莫旦增许如初黄文奇华中科技大学计算机科学与技术学院武汉430074

带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中"粗精加工"现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既... 详细信息

带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中"粗精加工"现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.

关键词： Packing问题布局优化拟物平衡约束粗精调技术

在线全文

学校读者我要写书评

暂无评论

求解二维矩形Packing问题的完备算法

计算机科学 2014年第8期41卷 55-59,89页

作者：何琨姚鹏程李立文华中科技大学计算机科学与技术学院武汉430074

对于典型的NP难度问题——二维矩形Packing问题,经典完备算法的计算复杂度不仅与待放块的数目相关,也与矩形框的宽和高相关。通过观察二维矩形Packing问题的合法布局的特点,将其与一对有向无环图相对应,并基于Prüfer码进行编码,提出了... 详细信息

对于典型的NP难度问题——二维矩形Packing问题,经典完备算法的计算复杂度不仅与待放块的数目相关,也与矩形框的宽和高相关。通过观察二维矩形Packing问题的合法布局的特点,将其与一对有向无环图相对应,并基于Prüfer码进行编码,提出了一种计算复杂度仅与待放块数相关的复杂度较低的完备算法。

关键词： Packing问题完备算法计算复杂度 Prüfer编码有向无环图

在线全文

学校读者我要写书评

暂无评论

基于穴度的三维时空优化问题的贪心调度算法

计算机科学与探索 2016年第8期10卷 1051-1062页

作者：朱鹏何琨曹伟刚杨欢华中科技大学计算机科学与技术学院武汉430074

研究了基于二维矩形Packing的三维时空优化问题,即对给定的一个任意宽、高的大矩形框和有限个有连续加工时间要求的任意宽、高的小矩形块,如何安排每个小矩形块的入框时刻及其出框前每一时刻的位置和方向,使得所有小矩形块的总加工时间... 详细信息

研究了基于二维矩形Packing的三维时空优化问题,即对给定的一个任意宽、高的大矩形框和有限个有连续加工时间要求的任意宽、高的小矩形块,如何安排每个小矩形块的入框时刻及其出框前每一时刻的位置和方向,使得所有小矩形块的总加工时间即总调度长度makespan最短。与经典布局问题的不同之处在于,各矩形块在框内可随时间的绵延而改变其位置和方向,从而能更充分地利用矩形框的空间。基于实角与实占角动作的定义,设计了求解其子问题二维矩形Packing问题的增强穴度算法。然后,每步迭代优先考虑剩余加工时间长的矩形块,提出了求解此问题的贪心穴度调度算法(caving-degree based greedy scheduling algorithm,CGSA)。作为比较,同时设计了矩形块在框内不可随时间移动的将时间简单类比为空间的对应Packing问题的调度算法CGSA′。对于实验中提出的满足非闸断模式的4个小型算例,它们在原问题上的最优调度长度为2,但若将时间简单地类比为空间,即矩形块放入框内后不可随时间移动其方位,则其最优调度长度为3。实验表明,算法CGSA在这4个非闸断算例上均得到了最优调度。进一步地研究出满足闸断模式的21组共210个自动生成算例,通过实验验证了算法CGSA的最优解的数目明显多于CGSA′,且CGSA的平均调度长度明显短于CGSA′。

关键词：时空优化贪心调度装箱算例布局