期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到211篇文章
< 1 2 … 11 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
求解SAT问题的拟物拟人算法—Solar 被引量：23
1
作者 黄文奇 金人超 《中国科学（E辑）》 CSCD 1997年第2期179-186,共8页
利用拟物与拟人的方法,为合取范式可满足性问题的高效率近似求解得出了继承策略、新路策略和赦免策略,然后对著名的Bart Selman跳坑策略给出了一个直观解释.综合这些策略得出了一个新的求解算法——Solar.
关键词 合取范式 拟物法 拟人法 计算机算法 SAT
原文传递
一种求解合取范式可满足性问题的数学物理方法 被引量：21
2
作者 李未 黄文奇 《中国科学（A辑）》 CSCD 1994年第11期1208-1217,共10页
给出合取范式与带电质点在某类静电场中势函数的一一对应关系,证明判断一个合取范式是否可满足等价于判断一个带电质点在相应的静电场中是否有使其势函数为零的位置,由于带电质点在静电场中总是沿使其势能下降最快的方向,也就是沿其势... 给出合取范式与带电质点在某类静电场中势函数的一一对应关系,证明判断一个合取范式是否可满足等价于判断一个带电质点在相应的静电场中是否有使其势函数为零的位置,由于带电质点在静电场中总是沿使其势能下降最快的方向,也就是沿其势函数梯度指引的方向运动,并最终达到势能最低的位置。因此,对一个客观上可满足的合取范式所对应的势函数,使用梯度算法是求使该合取范式成真的赋值的高效算法。 展开更多
关键词 合取范式 可满足性问题 数学物理算法 NP问题
原文传递
求解SAT问题的拟人退火算法 被引量：27
3
作者 张德富 黄文奇 汪厚祥 《计算机学报》 EI CSCD 北大核心 2002年第2期148-152,共5页
该文利用一个简单的变换 ,将可满足性 (SAT)问题转换为一个求相应目标函数最小值的优化问题 ,提出了一种用于跳出局部陷阱的拟人策略 .基于模拟退火算法和拟人策略 ,为 SAT问题的高效近似求解得出了拟人退火算法 (PA) ,该方法不仅具有... 该文利用一个简单的变换 ,将可满足性 (SAT)问题转换为一个求相应目标函数最小值的优化问题 ,提出了一种用于跳出局部陷阱的拟人策略 .基于模拟退火算法和拟人策略 ,为 SAT问题的高效近似求解得出了拟人退火算法 (PA) ,该方法不仅具有模拟退火算法的全局收敛性质 ,而且具有一定的并行性、继承性 .数值实验表明 ,对于本文随机产生的测试问题例 ,采用拟人策略的模拟退火算法的结果优于局部搜索算法、模拟退火算法以及近来国际上流行的 WAL KSAT算法 。 展开更多
关键词 SAT问题 模拟退火算法 拟人退火算法 目标函数 计算机 可满足性
下载PDF
求解工件车间调度问题的一种新的邻域搜索算法 被引量：20
4
作者 王磊 黄文奇 《计算机学报》 EI CSCD 北大核心 2005年第5期809-816,共8页
该文提出了一种新的求解工件车间调度(jobshopscheduling)问题的邻域搜索算法.问题的目标是在满足约束条件的前提下使得调度的makespan尽可能地小.定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调... 该文提出了一种新的求解工件车间调度(jobshopscheduling)问题的邻域搜索算法.问题的目标是在满足约束条件的前提下使得调度的makespan尽可能地小.定义了一种新的优先分配规则以生成初始解;定义了一种新的邻域结构;将邻域搜索跟单机调度结合在一起;提出了跳坑策略以跳出局部最优解并且将搜索引向有希望的方向.计算了当前国际文献中的一组共58个benchmark问题实例,算法的优度高于当前国外学者提出的两种著名的先进算法.其中对18个10工件10机器的实例,包括最著名的难解实例ft10,在可接受的时间内都找到了最优解.这些实例是当前文献中报导的所有规模为10工件10机器的实例. 展开更多
关键词 组合优化 NP难问题 工件车间调度 邻域搜索
下载PDF
基于欧氏距离的矩形Packing问题的确定性启发式求解算法 被引量：26
5
作者 黄文奇 刘景发 《计算机学报》 EI CSCD 北大核心 2006年第5期734-739,共6页
使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.
关键词 PACKING问题 拟人法 占角动作 穴度 价值度 欧氏距离
下载PDF
求解Covering问题的拟物方法——NP难度问题的一个处理途径 被引量：16
6
作者 黄文奇 《计算机学报》 EI CSCD 北大核心 1989年第8期610-616,共7页
本文提出的算法模拟了由万有引力和屏蔽现象所引起的力学过程.这种拟物的方案可为许多NP难度的问题得出有价值的近似算法.该算法对拟物类型的选择与现代递归论中的有穷损害优先方法的精神是一致的.
关键词 Covering问题 NP难度 拟物方法
下载PDF
求解有关空间利用的调度问题的拟物方法 被引量：9
7
作者 黄文奇 陈亮 《中国科学（A辑）》 CSCD 1991年第3期325-331,共7页
可将有关空间利用的调度问题看作四维时空中的Packing问题。对于三维空间中的Packing问题已有拟物型的求解方法,将此种方法加以适当引伸后得出了求解有关调度问题的拟物方法。它能被具体化为关于空间利用调度问题的专家系统或计算机辅... 可将有关空间利用的调度问题看作四维时空中的Packing问题。对于三维空间中的Packing问题已有拟物型的求解方法,将此种方法加以适当引伸后得出了求解有关调度问题的拟物方法。它能被具体化为关于空间利用调度问题的专家系统或计算机辅助设计软件系统。 展开更多
关键词 调度问题 NP难度 PACKING问题
原文传递
求解方格packing问题的启发式算法 被引量：14
8
作者 黄文奇 朱虹 +1 位作者 许向阳 宋益民 《计算机学报》 EI CSCD 北大核心 1993年第11期829-836,共8页
沿着拟物与拟人的途径,本文为一类具有NP难度的方格packing问题得到了实用的近似求解算法,以此算法为基础可以发展出一种为大规模集成电路芯片裁切工作做计算机辅助设计的高效的软件系统。
关键词 方格 PACKING问题 CAD 启发式算法
下载PDF
基于动作空间求解二维矩形Packing问题的高效算法 被引量：22
9
作者 何琨 黄文奇 金燕 《软件学报》 EI CSCD 北大核心 2012年第5期1037-1044,共8页
对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和T... 对于二维矩形Packing这一典型的NP难度问题,在黄文奇等人提出的拟人型穴度算法的基础上,通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法能够快速地得到空间利用率较高的布局图案.实验测试了Hopper和Turton提出的21个著名的二维矩形Packing问题的实例.改进的算法对其中的每一个实例都得到了空间利用率为100%的最优布局,且在普通PC机上的平均计算时间未超过7分钟.实验结果表明,基于动作空间对拟人型穴度算法所进行的改进是明显而有效的. 展开更多
关键词 NP难度 矩形Packing 拟人 动作空间 穴度
下载PDF
求解圆形Packing问题的一个启发式算法 被引量：10
10
作者 康雁 黄文奇 《计算机研究与发展》 EI CSCD 北大核心 2002年第4期410-414,共5页
求解ＮＰ难度问题一直是计算机科学技术中的一个瓶颈任务．自２０世纪７０年代以来的研究表明，求解ＮＰ难度问题不存在既完整严格又不太慢的求解算法．因此，近年来，启发式方法成为研究热点．圆形Ｐａｃｋｉｎｇ问题是ＮＰ难的，具有... 求解ＮＰ难度问题一直是计算机科学技术中的一个瓶颈任务．自２０世纪７０年代以来的研究表明，求解ＮＰ难度问题不存在既完整严格又不太慢的求解算法．因此，近年来，启发式方法成为研究热点．圆形Ｐａｃｋｉｎｇ问题是ＮＰ难的，具有很高的理论和实践价值．它的求解目标是寻求多个圆在一个大圆内的一个优良布局，使得这些圆互不重叠地放置．基于拟物法以及适者生存的启发式思想，为圆形Ｐａｃｋｉｎｇ问题的快速求解提出了一个高效的启发式算法．算法的高效性通过计算实例得到了验证． 展开更多
关键词 圆形PACKING问题 启发式算法 NP难度问题 计算机
下载PDF
一种基于禁忌搜索的作业车间调度算法 被引量：13
11
作者 黄志 黄文奇 《计算机工程与应用》 CSCD 北大核心 2006年第3期12-14,共3页
文章描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法。该算法基于禁忌搜索技术和前瞻思想,为了得到更好的结果,还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例... 文章描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法。该算法基于禁忌搜索技术和前瞻思想,为了得到更好的结果,还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比2004年提出的ISSB算法和另一种基于禁忌搜索的TSAB算法更好的结果。 展开更多
关键词 作业车间调度 启发式算法 禁忌搜索 倒转技术
下载PDF
基于动作空间的三维装箱问题的确定性高效率求解算法 被引量：20
12
作者 何琨 黄文奇 《计算机学报》 EI CSCD 北大核心 2014年第8期1786-1793,共8页
三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚... 三维装箱问题要求将有限个三维矩形物体尽可能多地装入到一个三维矩形箱子中,使得箱子的填充率即体积利用率最大.在求解三维装箱问题的穴度算法的基础之上,进一步做了以下改进:(1)将当前剩余空间中可能放入的每个体积最大的三维矩形虚拟物体所对应的空间定义为动作空间,在动作空间内放入物体并使穴度的定义体现放入物体与动作空间的吻合程度;(2)在物体放入位置的选择上直接体现"金角银边草肚皮"的思想,每一步只选择最靠近箱子边缘的一个动作空间来装载物体;(3)结合捆绑策略,将形状大小相同的物体捆绑为一个较大的矩形块进行放入,对捆绑块形状大小的选择为在不超出动作空间的前提下尽量用物体填满该空间的两至三个维度.实验结果表明,改进后的穴度算法在付出很少的开销代价的情况下显著地提高了箱子的填充率. 展开更多
关键词 三维布局 装箱 启发式 动作空间 穴度
下载PDF
求解矩形packing问题的贪心算法 被引量：15
13
作者 陈端兵 黄文奇 《计算机工程》 CAS CSCD 北大核心 2007年第4期160-162,共3页
在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形pack... 在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解。测试结果表明,该算法对求解矩形packing问题相当有效。 展开更多
关键词 矩形packing 贪心算法 占角动作
下载PDF
基于禁忌搜索的启发式算法求解圆形packing问题 被引量：12
14
作者 康雁 黄文奇 《计算机研究与发展》 EI CSCD 北大核心 2004年第9期1554-1558,共5页
求解具有NP难度的圆形 packing问题具有很高的理论与实用价值 现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题 此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程... 求解具有NP难度的圆形 packing问题具有很高的理论与实用价值 现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题 此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程中利用了禁忌搜索法的思想 ,通过禁止重复前面已做的工作 ,使搜索能有效地逃离局部极小值的陷阱 ,提高了搜索效率 实验结果表明 。 展开更多
关键词 圆形PACKING问题 禁忌搜索法 启发式算法 NP难问题
下载PDF
基于任务复制的分簇与调度算法 被引量：14
15
作者 何琨 赵勇 黄文奇 《计算机学报》 EI CSCD 北大核心 2008年第5期733-740,共8页
针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意DAG,算法有优... 针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意DAG,算法有优于前人的性能下界.实验结果优于典型任务复制算法,特别是对经典EZ算例的解(调度长度为8)好于前人认为的理论最优解(调度长度为8.5),并证明了新的解为最优解.定义了DAG的补图,讨论了不允许任务复制时树型DAG的2-优度算法. 展开更多
关键词 任务复制 任务分簇 调度算法 DAG任务粒度
下载PDF
一种求解集合覆盖问题的启发式算法 被引量：13
16
作者 陈端兵 黄文奇 《计算机科学》 CSCD 北大核心 2007年第4期133-136,共4页
集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小。集合覆盖问题被广泛应用到航空人员行程安排、电路设计、... 集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小。集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域。对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法。本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法。算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列。用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的。 展开更多
关键词 集合覆盖 启发式算法 贪心策略 随机跳坑
下载PDF
利用改进的微分进化算法求解带平衡约束的圆形packing问题 被引量：13
17
作者 刘建 黄文奇 《信息与控制》 CSCD 北大核心 2006年第1期103-107,113,共6页
提出了一种改进的微分进化算法(DE)求解二维带平衡约束的圆形pack ing问题.首先,构造出等价的物理模型,定义系统的能量函数,再对能量函数进行全局优化,从而间接得到问题的近似解.其中引入的参数动态调整策略在计算初期维持个体的多样性... 提出了一种改进的微分进化算法(DE)求解二维带平衡约束的圆形pack ing问题.首先,构造出等价的物理模型,定义系统的能量函数,再对能量函数进行全局优化,从而间接得到问题的近似解.其中引入的参数动态调整策略在计算初期维持个体的多样性,后期加快算法的收敛速度,提高了DE算法的性能.最后,对两个算例进行了数值计算,实验结果证明了算法的有效性.此算法思路可推广应用于求解其它类型布局问题. 展开更多
关键词 微分进化算法 NP难问题 约束布局问题 能量模型
下载PDF
解 packing 及 CNF-SAT 问题的拟物拟人方法 被引量：6
18
作者 黄文奇 许如初 +1 位作者 陈卫东 张京芬 《华中理工大学学报》 CSCD 北大核心 1998年第9期5-7,54,共4页
提出拟物拟人方法．论述了如何按此种方法为ＮＰ难问题设计出高效实用的快速求解算法．作为例证，所得出的关于ＣＮＦ－ＳＡＴ问题及ｐａｃｋｉｎｇ问题的算法，其先进性在国际竞赛及工业生产中得到了显示．
关键词 PACKING问题 拟物 拟人 算法 CNF-SAT问题
下载PDF
求解蛋白质折叠问题的拟人算法:对PERM的改进 被引量：7
19
作者 黄文奇 吕志鹏 《科学通报》 EI CAS CSCD 北大核心 2004年第17期1801-1804,共4页
PERM(Pruned-Enriched-Rosenbluth Method)是目前文献中依格点模型求解蛋白质折叠问题的最高效算法. 给出了PERM算法的一种拟人解释, 对算法中的权重及预测值进行了拟人化的改进, 并对选择动作时不同情况下的权重计算公式进行了统一. ... PERM(Pruned-Enriched-Rosenbluth Method)是目前文献中依格点模型求解蛋白质折叠问题的最高效算法. 给出了PERM算法的一种拟人解释, 对算法中的权重及预测值进行了拟人化的改进, 并对选择动作时不同情况下的权重计算公式进行了统一. 综合这些策略得到了改进的PERM算法——人口控制算法. 该算法在计算效率上有了明显的提高: 对当前文献中公认的最难的4个算例的计算都达到了最优解, 计算速度较PERM提高了几倍至几百倍. 对于这4个难例中的3个, 还找到了迄今为止文献中所没有的全新的最低能量构形. 展开更多
关键词 文献 拟人化 Method) 动作 情况 综合 策略 求解 最优解 格点
原文传递
基于模拟退火算法的蛋白质折叠问题求解 被引量：5
20
作者 黄文奇 李宗 《计算机工程与应用》 CSCD 北大核心 2005年第7期40-41,86,共3页
论文将模拟退火思想用于蛋白质结构预测问题,并在此基础上提出改进策略,计算结果表明,对于蛋白质折叠问题模拟退火算法是有效的,改进后的模拟退火算法的计算效率优于目前常用的遗传算法和MonteCarlo方法。
关键词 蛋白质折叠 NP难问题 二维整点模型 构形 模拟退火 自重叠
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 2 … 11 下一页 到第 页
使用帮助 返回顶部