求解单位等边三角形Packing问题的占角算法 被引量：2

1

作者 黄文奇 王瑞民 《鄂州大学学报》 2000年第2期1-3,共3页

本文沿着拟人的途径，得出了关于 ＮＰ难度的单位等边三角形 Ｐａｃｋｉｎｇ 问题的实用求解算法，此算法的思想，经过发展和具体化后，可以用来求解许多ＮＰ难度问题。

关键词 NP难度 拟物法 拟人法 角区 占角动作

下载PDF 职称材料

解决二维下料问题的顺序启发式算法 被引量：20

2

作者 黄少丽 杨剑 +1 位作者 侯桂玉 崔耀东 《计算机工程与应用》 CSCD 北大核心 2011年第13期234-237,共4页

求解二维下料问题即求解如何用最少的板材排入所需的全部毛坯的问题。一种基于价值修正策略的顺序启发式算法被用来生成排样方案,方案中的排样方式按单位面积价值最大生成,在各排样方式顺序生成的过程中不断修正方式中使用到的毛坯的价... 求解二维下料问题即求解如何用最少的板材排入所需的全部毛坯的问题。一种基于价值修正策略的顺序启发式算法被用来生成排样方案,方案中的排样方式按单位面积价值最大生成,在各排样方式顺序生成的过程中不断修正方式中使用到的毛坯的价值。迭代调用该过程多次生成多个排样方案,从中选择最优的排样方案。通过实验证明算法的有效性。 展开更多

关键词 二维下料 占角动作 穴度 顺序价值修正 顺序启发式算法

下载PDF 职称材料

基于欧氏距离的矩形Packing问题的确定性启发式求解算法 被引量：26

3

作者 黄文奇 刘景发 《计算机学报》 EI CSCD 北大核心 2006年第5期734-739,共6页

使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.

关键词 PACKING问题 拟人法 占角动作 穴度 价值度 欧氏距离

下载PDF 职称材料

求解矩形packing问题的贪心算法 被引量：15

4

作者 陈端兵 黄文奇 《计算机工程》 CAS CSCD 北大核心 2007年第4期160-162,共3页

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形pack... 在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解。测试结果表明,该算法对求解矩形packing问题相当有效。 展开更多

关键词 矩形packing 贪心算法 占角动作

下载PDF 职称材料

一种求解矩形块布局问题的拟物拟人算法 被引量：7

5

作者 黄文奇 陈端兵 《计算机科学》 CSCD 北大核心 2005年第11期182-186,共5页

在VLSI工作中提出了矩形块布局问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法等求解算法。本文以人类上万年以来形成的经验为基础,利用“占角”和“聚类”两个拟物拟人的思想策略,提出了基于最大穴度优先的拟物拟人布局... 在VLSI工作中提出了矩形块布局问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法等求解算法。本文以人类上万年以来形成的经验为基础,利用“占角”和“聚类”两个拟物拟人的思想策略,提出了基于最大穴度优先的拟物拟人布局算法。用本文提出的算法,对MCNC、GSRC两个典型测试算例的所有实例进行了实算测试,测试结果表明:计算所得布局结果的优度高,计算时间短。对MCNC和GSRC测试算例,除apte实例外,其它所有实例均得到了最优解,而计算时间都在10秒以内。与CBL算法、遗传算法和号称当今最好的CompaSS算法相比,本文算法所得结果的优度更高,计算时间更短。进一步的测试表明,本文提出的拟物拟人布局算法为当今的一种高效算法。 展开更多

关键词 PACKING VLSI布图规划 拟物拟人算法 占角动作 聚类 布局问题 求解算法 矩形 COMPASS 计算时间

下载PDF 职称材料

求解不等圆Packing问题的一个启发式算法 被引量：5

6

作者 陈矛 黄文奇 《计算机研究与发展》 EI CSCD 北大核心 2007年第12期2092-2097,共6页

求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多... 求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将待布局圆按半径大小降序排列,然后用占角动作来逐个放置.通过试探性地放入一个或多个待布局圆,给出了占角动作的度以及更全局的有限枚举策略来评价占角动作的优度.在放置每一个圆时,以贪心的方式选取当前具有最大优度的占角动作来放置.最后用测试算例验证了算法的高效性. 展开更多

关键词 NP难问题 圆形PACKING问题 启发式算法 占角动作 有限枚举策略

下载PDF 职称材料

一种求解矩形packing问题的智能枚举算法 被引量：1

7

作者 陈端兵 刘景发 +1 位作者 尚明生 傅彦 《重庆邮电大学学报（自然科学版）》 2008年第4期447-452,共6页

矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算... 矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明:该算法对求解矩形packing问题是行之有效的。 展开更多

关键词 矩形packing NP完全 智能枚举算法 占角动作 穴度

下载PDF 职称材料

求解矩形和圆形装填问题的最大穴度算法 被引量：2

8

作者 陈端兵 黄文奇 《计算机工程与应用》 CSCD 北大核心 2007年第4期1-3,共3页

在超大规模集成电路设计,裁缝裁剪布料,玻璃切割等工作中提出了矩形和圆形装填问题,即把不同大小的矩形块和圆饼装入一个矩形容器中,以最大化容器的面积利用率为优化目标。对这一问题,可采用模拟退火,遗传算法等国际流行算法进行求解,... 在超大规模集成电路设计,裁缝裁剪布料,玻璃切割等工作中提出了矩形和圆形装填问题,即把不同大小的矩形块和圆饼装入一个矩形容器中,以最大化容器的面积利用率为优化目标。对这一问题,可采用模拟退火,遗传算法等国际流行算法进行求解,但这些方法计算时间较长,计算结果的优度也不甚理想。利用人类的智慧和经验,提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试,所得结果的平均面积利用率为90.80%,平均计算时间为8.38s。测试结果表明,算法对求解矩形和圆形装填问题是行之有效的。 展开更多

关键词 装填 矩形和圆 占角动作 穴度

下载PDF 职称材料

基于拟人策略的带有预放置模块的布局算法 被引量：1

9

作者 刘景发 黄文奇 《计算机工程》 EI CAS CSCD 北大核心 2006年第19期26-28,共3页

在超大规模集成电路设计中,一些特别重要的模块,像RAM、ROM和CPU等经常被优先放置,而其它模块则被两两互不重叠地放置在芯片的剩余区域。此类问题能被形式化为带有预放置模块的布局问题,关于此问题的求解方法多为随机优化方法。该文基... 在超大规模集成电路设计中,一些特别重要的模块,像RAM、ROM和CPU等经常被优先放置,而其它模块则被两两互不重叠地放置在芯片的剩余区域。此类问题能被形式化为带有预放置模块的布局问题,关于此问题的求解方法多为随机优化方法。该文基于拟人的思想,提出了占角和最大穴度优先的放置策略,为该问题的快速求解提供了一种高效的启发式确定性算法。算法的高效性通过应用于标准电路MCNC得到了验证。 展开更多

关键词 预放置 拟人策略 占角动作 穴度 布局算法

下载PDF 职称材料

一种求解矩形块装填问题的拟人算法 被引量：1

10

作者 陈端兵 黄文奇 《计算机科学》 CSCD 北大核心 2006年第5期234-237,共4页

在货物装载、木材下料、超大规模集成电路(VLSI)设计等工作中提出了矩形块装填与切割问题,对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验,提... 在货物装载、木材下料、超大规模集成电路(VLSI)设计等工作中提出了矩形块装填与切割问题,对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。本文利用人类的智慧和他们上万年以来形成的经验,提出了一种求解矩形块装填问题的拟人算法。该算法使用了两个主要的思想策略,即矩形块选择策略和矩形块放置策略。用本文提出的算法,对21个测试算例进行了实算测试,测试结果表明:算法所得装填结果的优度高,计算时间短。对这21个测试算例,用本文算法计算,得到了其中16个算例的最优解,而计算时间都在2秒以内。进一步的测试表明,本文提出的算法对求解矩形决装填问题十分有效。 展开更多

关键词 矩形块装填 切割 拟人算法 占角动作

下载PDF 职称材料

求解集装箱装载问题的拟人算法

11

作者 黄文奇 何琨 +1 位作者 赵亮 张辉 《通讯和计算机（中英文版）》 2007年第2期19-21,共3页

本文对长方体Pacing问题（即集装箱装载问题），提出了一种拟人型的启发式算法。不同于求解该问题的传统方法，本文利用最大穴度优先原则，使长方体的排列尽可能紧凑，从而使容器中装入画可能多的长方体。实验表明即使用于强异构型的困... 本文对长方体Pacing问题（即集装箱装载问题），提出了一种拟人型的启发式算法。不同于求解该问题的传统方法，本文利用最大穴度优先原则，使长方体的排列尽可能紧凑，从而使容器中装入画可能多的长方体。实验表明即使用于强异构型的困难算例，该算法也具有高效的求解结果。 展开更多

关键词 启发式 拟人法 装箱问题 占角动作 穴度

下载PDF 职称材料

一种基于最小价值度优先的集成电路布图规划和布局算法

12

作者 黄文奇 马俊涛 《武汉工程职业技术学院学报》 2002年第1期52-55,共4页

平面布局的自动化是CAD领域的研究方向之一 ,旨在为工程设计师提供智能辅助工具 ,用以求解在大规模集成电路、产品包装、集装箱运输等若干领域中出现的空间布局问题。本文针对一类特定集成电路空间布局问题提出了中心线贴边动作和占角... 平面布局的自动化是CAD领域的研究方向之一 ,旨在为工程设计师提供智能辅助工具 ,用以求解在大规模集成电路、产品包装、集装箱运输等若干领域中出现的空间布局问题。本文针对一类特定集成电路空间布局问题提出了中心线贴边动作和占角动作的思想和相应的基于最小价值度优化 (LVFP)的算法。实验表明 ,在多数情况下 ,这一算法可以快速得到比较好的计算结果。 展开更多

关键词 集成电路 中心线贴边动作 占角动作 格局 目标矩形 价值度 CAD

下载PDF 职称材料