检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

无线网络中寻找非干扰不相交路径的拟人算法

计算机科学 2014年第8期41卷 70-74页

作者：董高秀凌珊陈卫东华南师范大学计算机学院广州510631

针对无线网络中寻找从源点s到汇点t的两条非干扰不相交路径这一np难问题,提出了一种拟人算法。该算法首先基于网络流方法得到两条点不相交的s-t路径,然后通过一种拟人化的策略逐步调整这两条路径,力图使得它们变为两条非干扰不相交的s-... 详细信息

针对无线网络中寻找从源点s到汇点t的两条非干扰不相交路径这一np难问题,提出了一种拟人算法。该算法首先基于网络流方法得到两条点不相交的s-t路径,然后通过一种拟人化的策略逐步调整这两条路径,力图使得它们变为两条非干扰不相交的s-t路径。模拟实验表明,与现有的算法相比,拟人算法可以快速地以更高的概率找到两条长度较短的非干扰不相交路径。

关键词：无线网络不相交路径非干扰不相交路径 np难度拟人算法

求解长方体Packing问题的纯粹拟人算法

在线全文

学校读者我要写书评

暂无评论

中国科学（F辑:信息科学） 2009年第6期39卷 617-622页

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

对于具有np难度的长方体Packing问题,挖掘出了中国古代谚语"金角银边草肚皮"中隐藏的智慧,并进一步发展出新子句"价值最高钻石穴".在利用现代西方的先进数学工具经过确切化、完整化与形式化后,得出了一种纯粹拟人型的求解算法.试算了国... 详细信息

对于具有np难度的长方体Packing问题,挖掘出了中国古代谚语"金角银边草肚皮"中隐藏的智慧,并进一步发展出新子句"价值最高钻石穴".在利用现代西方的先进数学工具经过确切化、完整化与形式化后,得出了一种纯粹拟人型的求解算法.试算了国际上公开通行的两组有代表性的算例(benchmark).对于100个强异构型的困难算例,所得布局图案达到了87.31%的平均空间利用率,刷新了当今国际上的最好纪录,将它提高了1.83个百分点.对于47个无方向约束的困难算例,得到了92.05%的平均空间利用率,将当今国际上的最好纪录提高了1.05个百分点.

关键词： Packing问题 np难度启发式算法拟人方法穴度

在线全文

学校读者我要写书评

暂无评论

社交网络中求最小正影响支配集的改进算法

华南师范大学学报（自然科学版） 2016年第3期48卷 59-63页

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

网络中求解最小正影响支配集的问题已经被证明是np难问题,且已有性能较好的贪心求解算法.通过分析现有的贪心近似算法(Wang-Greedy)和贪心启发式算法(Raei-Greedy),融合其贪心策略,提出了1个改进的贪心近似算法(Hybrid-Greedy).理论分... 详细信息

网络中求解最小正影响支配集的问题已经被证明是np难问题,且已有性能较好的贪心求解算法.通过分析现有的贪心近似算法(Wang-Greedy)和贪心启发式算法(Raei-Greedy),融合其贪心策略,提出了1个改进的贪心近似算法(Hybrid-Greedy).理论分析表明,Hybrid-Greedy仍保持Wang-Greedy的近似比性能和时间复杂度.在一些较大规模的真实社交网络实例中的实验研究表明,Hybrid-Greedy在这些社交网络中所得解的质量较Wang-Greedy和Raei-Greedy有明显提高.

关键词：正影响支配集 np难度近似算法贪心算法社交网络

求解2-D Strip Packing问题的u-分组优化算法

在线全文

学校读者我要写书评

暂无评论

计算机科学 2017年第5期44卷 290-293,303页

作者：黄海李松斌莆田学院信息工程学院莆田351100 中国科学院声学研究所南海研究站海口570105 中国科学院声学研究所国家网络新媒体工程技术研究中心北京100190

2-D strip packing问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大。基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的... 详细信息

2-D strip packing问题指将带有价值的矩形物品装入长宽固定的箱子中,使其装入的物品价值最大。基于装箱的期望目标ε,提出一种新的分组构造函数,结合装箱矩形特点计算出最优分组参数u并对矩形进行分类,同时对不同类别的矩形引入相应的数据结构,最后对不同类别矩形基于箱子X轴的u等分点进行填充,使其装入的物品价值最大。文中的主要贡献在于:提出了一种有效的分组构造函数;计算出了对应的最优分组参数u;简化了不同类别箱体的数据结构以及相应的装箱算法;特别地,在期望目标ε、多项式时间复杂度和至少装入(1-ε)OPT价值物品的情况下,可将所需箱体宽度从1+ε减小到1,而高度保持不变。

关键词： u-分组二维装箱近似算法 np难度启发式

在线全文

学校读者我要写书评

暂无评论

三维矩形Packing问题的拟人求解算法

中国科学：信息科学 2010年第12期40卷 1586-1595页

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

基于当前格局下可能填充的最大矩形空间的概念以及围城战术,将求解三维矩形Packing这一典型np难度问题的拟人型穴度算法做了关键性的改进,得到了新的更强有力的算法ICDA.在时间开销与当今代表性算法大致相当的前提下,ICDA对于国际上公... 详细信息

基于当前格局下可能填充的最大矩形空间的概念以及围城战术,将求解三维矩形Packing这一典型np难度问题的拟人型穴度算法做了关键性的改进,得到了新的更强有力的算法ICDA.在时间开销与当今代表性算法大致相当的前提下,ICDA对于国际上公开的由100个实例组成的天然的最困难的问题类,即待放长方体的形状大小随机给定、几乎两两皆不相同的情形,得到了90.92%的平均空间利用率.所得精度比国际学术界最新公开发表的同时也是迄今为止最好的结果要高出0.54个百分点.

关键词： np难度三维Packing 拟人策略动作空间穴度

求解二维矩形packing问题的高效算法设计

在线全文

学校读者我要写书评

暂无评论

求解二维矩形packing问题的高效算法设计

作者：金燕华中科技大学

学位级别：硕士

研究了二维矩形packing这一类np难度问题。在黄文奇等人提出的拟人型穴度算法的基础之上，提出了基于动作空间的拟人型穴度算法，通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法既继承了原有穴度算... 详细信息

研究了二维矩形packing这一类np难度问题。在黄文奇等人提出的拟人型穴度算法的基础之上，提出了基于动作空间的拟人型穴度算法，通过定义动作空间来简化对不同放入动作的评价,使穴度的计算时间明显缩短,从而使算法既继承了原有穴度算法的优势，又能够快速地得到面积利用率较高的布局图案。重点研究了二维矩形装填问题，给出了格局、动作空间、占角动作、平整度、评价标准和比较策略的定义。基于动作空间，简化了对不同放入动作的评价，明显缩短了计算时间。在算法的设计中，着重考虑了如何分割矩形框内的剩余空间使放入块与周围的已放入块更紧密、采用哪种数据结构使得剩余空间的更新更快捷、如何选取一个唯一的占角动作使之遵循“可持续发展的路线”、选取哪种搜索策略可以使结果不断趋近全局最优解而不至于陷入局部最小值的陷阱。进一步地，将此算法适当调整以求解二维strip packing问题和二维矩形packing价值优化问题。针对二维strip packing问题的特点，结合了加1法和二分法以求解已知矩形敞口框的最优高度和未知矩形敞口框的最优高度的两类子问题。针对二维矩形packing价值优化问题的特点，修改了占角动作的比较策略，加入了放入块的单位价值作为比较因子，并将目标函数调整为所有放入块的总价值。对二维矩形装填问题、二维strip packing问题和二维矩形packing价值优化问题，试算了国际上著名的相关算例。所提出的算法均能在较短的时间内得到较优的结果。对二维矩形装填问题，在Hopper和Turton提出的21个著名算例的每个实例上，所提出的算法均在较短的时间内得到了面积利用率为100%的最优布局;对Burke等人提出的13个算例，得到了7个最优解且平均面积利用率为99.84%，刷新了目前国际上已见发表的最好结果。对二维strip packing问题和二维矩形packing价值优化问题，所提出的求解算法的计算结果也接近国际上已见发表的最好结果。

关键词： np难度矩形packing问题拟人动作空间

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

组合拍卖赢者决定问题及其应用研究

组合拍卖赢者决定问题及其应用研究

作者：秦琴湖南师范大学

学位级别：硕士

随着电子商务的发展和拍卖多单元物品的实际需要,许多传统的拍卖理论和假设已经不再适合新的拍卖经济环境。人们开始设计并使用一些适合复杂性质物品的拍卖方式。实验表明在多物品拍卖中,当物品具有很强的协同作用(互补性或替代性)时,... 详细信息

随着电子商务的发展和拍卖多单元物品的实际需要,许多传统的拍卖理论和假设已经不再适合新的拍卖经济环境。人们开始设计并使用一些适合复杂性质物品的拍卖方式。实验表明在多物品拍卖中,当物品具有很强的协同作用(互补性或替代性)时,同时叫价拍卖优于序贯拍卖,而组合拍卖优于前两者。因此多物品拍卖中的组合拍卖在二十世纪九十年代后成为拍卖领域的研究热点。但是组合拍卖设计在应用中受到了很大的限制,原因是当销售商品数量和种类增加时,拍卖很快就变得非常复杂,确定赢者成为了一个难于计算的问题。赢者决定问题的复杂性不仅令拍卖方陷入决定的困境,还使得竞价人很难预计自己的投标结果,同时也很难判断拍卖方是否诚实地进行拍卖。因此,赢者决定问题严重地阻碍了组合拍卖理论的应用和发展。目前,关于赢者决定问题的研究大都是计算机领域的学者对该问题进行算法的改进,而从经济和应用领域研究如何解决赢者决定问题是不多见的。本文通过系统地阐述解决赢者决定问题的理论方法,重点研究这些处理方法在相关领域的应用中的异同。在研究过程中采用理论证明、实验证明、比较分析等研究方法。首先阐述了序贯拍卖和平行拍卖在实践应用中的缺陷,如分配结果的无效率、赢者诅咒等等,而组合拍卖可以很好地解决这些问题。其次系统地论证正向组合拍卖、逆向组合拍卖和双向组合拍卖赢者决定问题的复杂性,。接下来,文章讨论了组合拍卖赢者决定问题处理方法,并将处理方法分为三大类：赢者决定问题的简化处理(得到易处理的WDP)、赢者决定问题的算法改进和拍卖机制改进。最后,本文着重研究组合拍卖的主要应用领域——频谱拍卖、电力能源拍卖、飞机停机位拍卖、巴士线路拍卖、货车运输拍卖和采购拍卖,并将这六大应用领域分成三类,分别是：可分物品正向拍卖、不可分物品正向拍卖和不可分物品逆向拍卖。通过拍卖理论分析,设计并实施了系列计算机模拟实验,对实验结果,运用描述性统计及推断统计分析方法比较分析了在三类组合拍卖中不同的赢者决定问题处理方法的差异。对于可分物品正向拍卖赢者决定问题的处理,拍卖方定义优化组合和竞价人提交优化组合两种方法同时使用与选择其中一种方法比较,计算时间并不会显著减少。对于不可分物品的正向拍卖和逆向拍卖赢者决定问题的处理,拍卖方定义优化组合和竞价人提交优化组合两种方法应同时使用较单独使用一种方法,均能显著地减少计算时间,并且逆向拍卖中限制搜索这一方法也会显著减少计算时间。

关键词：组合拍卖赢者决定问题 np难度拍卖实验

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于二维矩形Packing的优化调度问题

基于二维矩形Packing的优化调度问题

作者：曹伟刚华中科技大学

学位级别：硕士

基于二维矩形Packing的优化调度问题是指对于给定的一个大矩形框和有连续加工时间要求的有限个小矩形块，如何调度各个小矩形块的入框时间和在框内的空间布局，使得大矩形框的总利用时间即makespan最小，要求任意时刻框内的各小矩形块... 详细信息

基于二维矩形Packing的优化调度问题是指对于给定的一个大矩形框和有连续加工时间要求的有限个小矩形块，如何调度各个小矩形块的入框时间和在框内的空间布局，使得大矩形框的总利用时间即makespan最小，要求任意时刻框内的各小矩形块完全正交放入且两两互不嵌入。此问题属于考虑时间因素的优化调度问题。其子问题二维矩形Packing问题就已经属于np难问题。随着待放入矩形块数量的增加，该子问题求解代价呈指数级增长。在基于二维矩形Packing的优化调度问题中，由于需要考虑随着连续量时间的绵延每一时刻框内的布局，使得问题的求解更加困难。首先，设计了子问题二维矩形Packing问题的求解算法，区分了实角和虚角，提出了寻找和判断实角的算法，改进了动作空间的定义，至少依赖一个实角，占角动作只占实角，动作空间的寻找在实角的基础上进行，采用了基线到基线的方式，减少了动作空间更新的工作量。然后，通过对基于二维矩形Packing的优化调度问题的分析，提出了基于时间和空间的贪心策略调度算法。优先考虑加工时间长的矩形块进行调度，尽量将加工时间长的矩形块分配到每次调度中。在时间相等的条件下，再考虑空间因素，使空间的利用率达到最高。由于问题具有时间和空间的相关性，空间的最优化利用可以带来时间的最小化开销。基于二维矩形Packing的优化调度问题是近年来学术界提出的一个新问题。目前国际上尚没有相关的算例。改造和设计了若干小型算例，提出和实现了一个算例生成算法，并进行了算法的正确性和可行性验证。

关键词：优化调度 np难度 Packing问题动作空间

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于适合度的二维矩形排样问题算法求解

基于适合度的二维矩形排样问题算法求解

作者：酆宇文江西财经大学

学位级别：硕士

我国的工业与制造业当前正处在变革转型的关键阶段,得益于我国的全产业链优势以及我国科技近年来的井喷式进步,智能制造等新兴技术变得炙手可热。在世界范围内新冠疫情的反复肆虐,将在未来几年对世界经济产生持续性的影响,这在之前是不... 详细信息

我国的工业与制造业当前正处在变革转型的关键阶段,得益于我国的全产业链优势以及我国科技近年来的井喷式进步,智能制造等新兴技术变得炙手可热。在世界范围内新冠疫情的反复肆虐,将在未来几年对世界经济产生持续性的影响,这在之前是不可想象的,工厂为了在经济寒流中提升自身竞争力在降低成本提升自身的资源利用率方面的需求将变得愈发迫切。所以对二维平面矩形的排样问题在生活中的应用展开研究依然有着相当的实用价值。二维矩形排样问题是经典的np难问题,如今城市的高楼大厦日益增多,受到夜幕下的摩天大楼启发联想到了天际线(Skyline)概念。该概念主要是利用矩形块顶部直线代表动作空间的宽度,同时记录天际线左端点的X、Y坐标,前驱及后继的X、Y坐标,可以在被使用时计算出当前动作空间的左右高度以及宽度。同时加入适合度(Fitness)概念以便于选择和优先放置更加契合格局的矩形块以生成更加“平整”的动作空间,适合度策略在考虑放置当前格局下最合适的矩形的同时,还考虑了矩形块放置完成后剩余动作空间空间的使用状态,为后续操作奠定了较好的基础。本文以适合度为核心,利用适合度打分策略挑选当前情况下最大适合度的矩形块进行放置,同时利用堆、线段树Segment Tree快速找到动作空间和目标矩形块。以此策略为基础得出了基础算法。本算法的主要思想是在当前格局下,通过适合度策略以及高效的搜索方式挑选出契合动作空间条件的最佳矩形块,并完成放置动作,对剩余数据进行规范化管理,直到所有矩形块均被放置进入大矩形容器以后得到终止格局,终止格局的最高点即为本次计算所需要的最低高度。所以,一个好的适合度打分策略在相同的计算时间内可以提高基础算法的精确度和效率。为了提高算法的随机性,获得更优解,我们使用随机交换矩形策略结合基础算法,设计得到了增强算法,在增强算法中,算法将进行N次迭代,N为矩形块的个数,每次迭代时将已经完成排序的矩形块序列R中,任意两对矩形块ID互换,再按照基础算法的选择,放置策略进行操作,并且完成计算,得到解H,保存计算过程中出现的最小H,直至计算时间限制或计算结束,H即为该算法的最优解。增强算法引入的交换策略,增强了算法的随机性,使得计算过程中矩形块的选取顺序发生改变,从而改变矩形的放置顺序和最终格局,获得放置顺讯不同得到的答案H,相比于基础算法,在规定时间段内,使用该算法进行放置的矩形顺序及答案更多样,更容易得到最优解,所以如何随机交换矩形是该算法的重要组成部分,通过对算例集C、N、NT、CX、2SP进行计算。得到的实验结果与其他优秀的同类算法的实验结果进行比较,验证了本算法是精确且高效的。

关键词： np难度矩形排样问题动作空间局部随机搜索