检索结果-南通市图书馆

计算机学报 1989年第8期12卷 610-616页

作者：黄文奇华中理工大学

本文提出的算法模拟了由万有引力和屏蔽现象所引起的力学过程.这种拟物的方案可为许多np难度的问题得出有价值的近似算法.该算法对拟物类型的选择与现代递归论中的有穷损害优先方法的精神是一致的.

关键词： Covering问题 np难度拟物方法

基于贪心回溯的求解完全0-1背包问题局部动态规划算法

在线全文

学校读者我要写书评

暂无评论

华中科技大学学报（自然科学版） 2024年第2期52卷 16-21页

作者：何琨任硕郭子杰裘天宝华中科技大学计算机科学与技术学院湖北武汉430074

对于具有np难度的完全0-1背包问题,提出了一种基于贪心与回溯思想的局部动态规划算法.该算法借鉴贪心与回溯技术快速找到近似最优解,再通过局部动态规划的结果回溯逼近最优解,兼顾了算法的正确性与时间复杂度.相比于传统动态规划算法,... 详细信息

对于具有np难度的完全0-1背包问题,提出了一种基于贪心与回溯思想的局部动态规划算法.该算法借鉴贪心与回溯技术快速找到近似最优解,再通过局部动态规划的结果回溯逼近最优解,兼顾了算法的正确性与时间复杂度.相比于传统动态规划算法,该算法在大多数情况下能够显著缩短求解时间;相较于智能算法,该算法能够保证所求解是最优解.实验结果表明:所提出的算法在绝大多数情形下均能够在更短时间内准确找到问题的最优解,并且该算法贪心地进行最大单位平均价值成分的选取,背包容量不再直接影响求解时间,因此对于背包容量极大的情况,该算法能够极大地缩短求解时间.

关键词：完全0-1背包问题 np难度动态规划贪心回溯

基于动作空间求解二维矩形Packing问题的高效算法

在线全文

学校读者我要写书评

暂无评论

软件学报 2012年第5期23卷 1037-1044页

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

对于二维矩形Packing这一典型的np难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和T... 详细信息

对于二维矩形Packing这一典型的np难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的.

关键词： np难度矩形Packing 拟人动作空间穴度

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

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

求解二维矩形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难度布局优化布图规划面积最小化启发式

在线全文

学校读者我要写书评

暂无评论

Bi-swapped网络的支配集问题研究

计算机学报 2016年第12期39卷 2512-2526页

作者：陈卫东华南师范大学计算机学院广州510631

图论中支配集和连通支配集概念可用于并行分布式系统中资源布局和路由策略.作为著名Swapped网络的改良形式,Bi-swapped网络是一类组合网络体系结构,它采用任意因子网络的多个拷贝作为模块并将这些模块通过一种简单的交换互连规则连通起... 详细信息

图论中支配集和连通支配集概念可用于并行分布式系统中资源布局和路由策略.作为著名Swapped网络的改良形式,Bi-swapped网络是一类组合网络体系结构,它采用任意因子网络的多个拷贝作为模块并将这些模块通过一种简单的交换互连规则连通起来.Bi-swapped网络的优良特性使得它可为构建并行计算机提供潜在有竞争力的体系结构方案.文中基于Bi-swapped网络的互连规则研究Bi-swapped网络中最小支配集问题和最小连通支配集问题.首先证明这两个问题都是np难度的,然后基于Bi-swapped网络的模块化结构特性,给出求解这两个问题的几个简单有效的近似算法.在一个N节点的Bi-swapped网络中,文中的算法以因子网络的一个(连通)支配集为输入,在O(N)时间内能构造出Bi-swapped网络的一个(连通)支配集,并且以一定性能保证了所构造的(连通)支配集的质量.相比之下,如果将Bi-swapped网络视作一般图而不利用其模块化特性,直接构造一个同样质量的(连通)支配集则需要O(N^2)时间.该文也建立了因子网络和Bi-swapped网络的(连通)支配数之间的联系,由此获得Bi-swapped网络的(连通)支配数的非平凡的上下界.我们的方法为诸如Bi-swapped网络等组合网络中的大数据处理和分析提供了一条可行途径.

关键词：互连网络 Bi-swapped网络支配集连通支配集 np难度近似算法

在线全文

学校读者我要写书评

暂无评论

大规模稀疏图的极大团枚举算法

华中科技大学学报（自然科学版） 2017年第12期45卷 1-6页

作者：何琨邹晟昊周建荣华中科技大学计算机科学与技术学院湖北武汉430074 深圳华中科技大学研究院广东深圳518057

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量Ma... 详细信息

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.

关键词： np难度大规模图极大团枚举贪心染色算法增量MaxSAT推理算法

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

最大可满足性问题的算法研究综述

华中科技大学学报（自然科学版） 2022年第2期50卷 82-95页

作者：何琨郑迥之华中科技大学计算机科学与技术学院湖北武汉430074

最大可满足性问题(maximum satisfiability,MaxSAT)是一个著名的、具有np难度的组合优化问题.本研究总结了近年来求解最大可满足性问题的各类算法.首先,给出了最大可满足性问题的定义;然后,基于完备算法和非完备算法两个类型,对求解Max... 详细信息

最大可满足性问题(maximum satisfiability,MaxSAT)是一个著名的、具有np难度的组合优化问题.本研究总结了近年来求解最大可满足性问题的各类算法.首先,给出了最大可满足性问题的定义;然后,基于完备算法和非完备算法两个类型,对求解MaxSAT的各类算法进行了综述.其中完备算法包括分支定界算法和迭代调用可满足性问题求解器的算法,非完备算法包括近似算法、基于最小校正子集的算法和局部搜索算法;最后,分析和对比了各类求解算法的优劣,并对最大可满足性问题求解所面临的挑战及可能的研究方向进行了讨论和展望.

关键词：最大可满足性问题 np难度组合优化完备算法非完备算法