检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

启发式算法设计中的骨架分析与应用

自动化学报 2011年第3期37卷 257-269页

作者：江贺邱铁胡燕李明楚罗钟铉大连理工大学软件学院大连116621 大连理工大学数学学院大连116621

骨架是指一个np-难解问题实例的所有全局最优解的相同部分,因其在启发式算法设计中的重要作用而成为该领域的研究热点.本文对目前骨架及相关概念的研究成果进行了全面综述,将骨架本身的研究工作归纳为三个层面:理论基础层面主要考虑骨... 详细信息

骨架是指一个np-难解问题实例的所有全局最优解的相同部分,因其在启发式算法设计中的重要作用而成为该领域的研究热点.本文对目前骨架及相关概念的研究成果进行了全面综述,将骨架本身的研究工作归纳为三个层面:理论基础层面主要考虑骨架与计算复杂性的关系问题;应用基础层面主要考虑如何高效地获取骨架;应用层面主要考虑如何利用骨架进行高效启发式算法设计.在此基础上,本文详细讨论了骨架研究亟待解决的难题,并指出了解决这些问题的努力方向.

关键词： np-难解骨架启发式算法计算复杂性

TSP问题的脂肪计算复杂性与启发式算法设计

在线全文

学校读者我要写书评

暂无评论

软件学报 2009年第9期20卷 2344-2351页

作者：江贺胡燕李强于红大连理工大学软件学院辽宁大连116621 中国科学院软件研究所计算机科学国家重点实验室北京100190

旅行商问题(traveling salesman problem,简称TSP)是经典的np-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于... 详细信息

旅行商问题(traveling salesman problem,简称TSP)是经典的np-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是np-难解的,即在P≠np的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法——动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的***典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他np-难解问题具有一定的参考价值.

关键词：旅行商问题 np-难解脂肪启发式

在线全文

学校读者我要写书评

暂无评论

近似骨架导向的归约聚类算法

电子与信息学报 2009年第12期31卷 2953-2957页

作者：宗瑜李明楚江贺大连理工大学软件学院大连116621 中国科学院软件研究所计算机科学国家重点实验室北京100190

该文针对聚类问题上缺乏骨架研究成果的现状,分析了聚类问题的近似骨架特征,设计并实现了近似骨架导向的归约聚类算法。该算法的基本思想是:首先利用现有的启发式聚类算法得到同一聚类实例的多个局部最优解,通过对局部最优解求交得到近... 详细信息

该文针对聚类问题上缺乏骨架研究成果的现状,分析了聚类问题的近似骨架特征,设计并实现了近似骨架导向的归约聚类算法。该算法的基本思想是:首先利用现有的启发式聚类算法得到同一聚类实例的多个局部最优解,通过对局部最优解求交得到近似骨架,将近似骨架固定得到规模更小的搜索空间,最后在新空间上求解。在26个仿真数据集和3个实际数据集上的实验结果表明,骨架理论对提高聚类质量、降低初始解影响及加快算法收敛速度等方面均十分有效。

关键词：聚类问题 np-难解启发式算法近似骨架

带多项式量级约束条件的多商品流BWTSP线性规划

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 2007年第10期44卷 1796-1800页

作者：江贺张宪超车皓阳陈国良大连理工大学软件学院大连116621 中国科学院软件研究所北京100080 中国科学技术大学计算机科学与技术系合肥230027

黑白旅行商问题(BWTSP)是近年来出现的新np-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约... 详细信息

黑白旅行商问题(BWTSP)是近年来出现的新np-难解问题,根据图中边是否对称可以分为无向BWTSP和有向BWTSP两种.现有无向BWTSP的Ghiani线性规划中约束条件数目为指数多个.权值阈值等于+∞的有向BWTSP通过转换为RATSP问题而存在多项式个约束条件的线性规划.针对一般的有向BWTSP,提出了一种仅包含多项式个约束条件的新线性规划.其基本思想是首先将有向BWTSP问题归约为ATSP问题,然后利用ATSP包含n(n+4)个约束条件的Finke-Claus-Gunn线性规划,通过定义剩余和消耗基数商品流,分析了环路上的弧应满足的约束条件,并证明这些n2+2|W|的约束条件即是基数约束条件;类似地通过定义剩余和消耗权值商品流,得到n2+n+2|B|个权值约束条件.最终得到原始问题仅包含3n2+7n个约束条件的线性规划.由于无向BWTSP问题和权值阈值等于+∞的有向BWTSP均是一般有向BWTSP的特例,故此结果对于它们同样有效.

关键词：黑白旅行商问题 np-难解线性规划完全算法商品流

在线全文

学校读者我要写书评

暂无评论

GPP问题的骨架分析与启发式算法设计

计算机学报 2009年第8期32卷 1662-1667页

作者：江贺邱铁大连理工大学软件学院大连辽宁116621 中国科学院软件研究所计算机科学国家重点实验室北京100190

图的划分问题(GPP)是具有广泛应用背景的典型np-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论上... 详细信息

图的划分问题(GPP)是具有广泛应用背景的典型np-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论上证明了获取GPP的骨架是np-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它np-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.

关键词：图的划分问题 np-难解骨架分析启发式算法设计

在线全文

学校读者我要写书评

暂无评论

黑白二次分配问题

计算机学报 2007年第3期30卷 440-447页

作者：江贺张宪超陈国良李明楚大连理工大学软件学院大连116621 中国科技大学计算机科学与技术系合肥230027

二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑... 详细信息

二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是np-难解问题,不存在ε-近似度的多项式时间近似算法(ε>0).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于np-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.

关键词：黑白二次分配问题 np-难解启发式算法黑白图支配集

在线全文

学校读者我要写书评

暂无评论

面向不确定数据的近似骨架启发式聚类算法

南京大学学报（自然科学版） 2015年第1期51卷 197-205页

作者：金萍宗瑜屈世超胡燕田园皖西学院信息工程学院六安237012 中国科学与技术大学计算机科学与技术学院合肥230027 大连理工大学软件学院大连116621

不确定数据聚类是传统数据挖掘的扩展,面对不确定数据聚类,研究者们经常把聚类问题描述成组合优化问题,并设计启发式聚类算法进行求解.现有的启发式聚类算法,如UK-means和UK-Medoids具有容易理解和实现简单等优点,但初始解敏感问题严重... 详细信息

不确定数据聚类是传统数据挖掘的扩展,面对不确定数据聚类,研究者们经常把聚类问题描述成组合优化问题,并设计启发式聚类算法进行求解.现有的启发式聚类算法,如UK-means和UK-Medoids具有容易理解和实现简单等优点,但初始解敏感问题严重影响了聚类质量.本文在近似骨架理论的基础上,提出了一种近似骨架启发式聚类算法APPGCU(Approximate backbone guided heuristic clustering algorithm for uncertain data).该算法首先对原数据集完成P次采样,在采样后的规模较小的P个数据集上分别执行UK-Medoids算法得到P个局部最优解;然后通过对P个局部最优解求交得到近似骨架,并从中提取初始簇心;最后从初始簇心开始,启发式搜索出聚类结果.在仿真和实际数据集中的实验结果表明,算法APPGCU的聚类结果明显高于实验对比的启发式聚类算法,提高了聚类质量.

关键词： np-难解启发式算法近似骨架不确定数据聚类

在线全文

学校读者我要写书评

暂无评论

二次分配问题的骨架分析与算法设计

中国科学（E辑） 2008年第2期38卷 209-222页

作者：江贺张宪超陈国良李明楚大连理工大学软件学院大连116621 中国科技大学计算机科学与技术系合肥230027

骨架分析是近年来np-难解问题研究的热点,对于衡量问题的相变、难度及算法设计具有重要意义.骨架的理论分析及在算法设计方面的应用还处于起步阶段.从QAP问题入手,对QAP骨架进行了理论分析,证明寻找QAP问题的骨架属于np-难解问题,不存... 详细信息

骨架分析是近年来np-难解问题研究的热点,对于衡量问题的相变、难度及算法设计具有重要意义.骨架的理论分析及在算法设计方面的应用还处于起步阶段.从QAP问题入手,对QAP骨架进行了理论分析,证明寻找QAP问题的骨架属于np-难解问题,不存在多项式时间的算法可以保证得到QAP问题的骨架,为局部最优解交叉来获得近似骨架提供了合理性解释.在此基础上,利用偏移实例构造方法,提出了基于偏移实例的近似骨架算法.其基本思想是:首先为QAP实例构造偏移实例,其最优解恰是原QAP实例的一个全局最优解;然后利用现有算法求得新实例的多个局部最优解,通过对局部最优解求交得到近似骨架;将近似骨架固定以得到规模更小的搜索空间,最后在新空间上求解.拓广了骨架理论研究的范围,所提出的算法为np-难解问题的通用算法设计提供了一种新思路.

关键词：二次匹配问题 np-难解骨架分析偏移实例元启发算法

在线全文

学校读者我要写书评

暂无评论

求解GCP问题的ILSBR算法

计算机工程与应用 2007年第33期43卷 43-45页

作者：田瑞兴江贺大连理工大学软件学院辽宁大连116621

图着色问题(GCP,Graph Coloring Problem)是经典的np-Hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的启发式算法,以便在合理的计算时间内解决大规模问题。由于对规模较大的问题,目前的启发式算法尚不能在较短的时间内给出... 详细信息

图着色问题(GCP,Graph Coloring Problem)是经典的np-Hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的启发式算法,以便在合理的计算时间内解决大规模问题。由于对规模较大的问题,目前的启发式算法尚不能在较短的时间内给出高质量的解,因此提出了一种基于全局最优解和局部最优解关系的ILS算法(ILSBR)。该算法的基本原理是通过对GCP问题的局部最优解和全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解。利用这些部分解构造一种新的扰动策略(RLG重着色),并将其应用到传统的ILS算法中。在DIMACS标准集中,典型实例上的实验结果表明,采用RBILS算法在求解质量不变的情况下,求解速度上与目前的已知算法相比有较大的改进。

关键词：图着色问题 np-难解部分解扰动