导读:本文包含了问题归约论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:可达,人工免疫,性问题,可达性,复杂度,冗余,最小化。
问题归约论文文献综述
黄青华[1]（2018）在《面向大图的传递归约问题研究》一文中研究指出图在互联网技术中有及其广泛的应用,但随着互联网的迅猛发展,图的规模也变得非常庞大,如何对图进行简化从而提升系统的扩展性是研究界关注的热点问题之一。传递归约是图操作中的核心操作,通过去除有向无环图G中的冗余边来实现简化的目的。简化后的有向无环图与G有相同的传递闭包。但是现有的传递归约算法的时间和空间复杂度较大,无法处理大规模有向无环图。针对现有的问题,本文提出了适用于大图的传递归约算法,具体的研究内容如下。首先,根据冗余边的性质,提出利用已有的可达性查询算法来加速冗余边判断的思路。考虑到计算每个兄弟的可达性的复杂度较高,提出将兄弟顶点按照拓扑排序的结果依次处理的算法来得到传递归约的结果。其次,针对出度大且冗余边很少的顶点可能存在处理代价高的问题,提出了对顶点按照(出度+入度)进行升序排序,依次处理每个顶点的方法来避免随机处理存在的冗余计算问题。该方法对每个被处理顶点都检查双向冗余边,并将确认的冗余边在图的邻接表中进行标记。其好处是先将度小的顶点处理完,后处理度较大的顶点时,和度大顶点关联的好多边都已被标记完成,从而有效减少了度大顶点关联的边的处理数量,降低度大顶点的处理代价。最后,本文基于28个不同大小的真实数据集进行实验,从多个角度通过实验结果对所提出算法的高效性进行对比与分析,验证了该算法的高效性和可扩展性。(本文来源于《燕山大学》期刊2018-05-01）
周世杰[2]（2016）在《面向大图的传递归约问题研究》一文中研究指出给定有向无环图G,G的传递归约是和G有相同传递闭包的最小唯一子图。传递归约是图论中的经典问题之一,并广泛应用于实际中简化问题的求解,包括传递闭包、背包问题、可达性问题等。然而,现有传递归约方法的计算代价高昂。随着网络技术的飞速发展和新型应用的不断涌现,实际应用中的图规模越来越大,在机器内存容量受限的情况下,已有的传递归约算法因其较高的空间复杂度面临无法使用的尴尬境地。本文从以下几个方面对有向无环图的传递归约方法进行研究,具体内容如下。首先,提出自底向上的BUTR算法。该算法首先将G分解为k条路径,以自底向上的方式处理每条路径p。其特点体现在处理每条路径p时,可以利用p中顶点间的父子关系来避免对部分顶点和边的重复访问,并保证在处理完p的所有顶点后,所有涉及到的边仅被访问一次。当处理完所有的k条路径之后,即可得到传递归约。BUTR时间与空间复杂度分别为O(km)和O(n),其中n、m分别为图G中结点和边的个数。其次,针对BUTR算法在实际应用中路径分解规模过大的问题,提出无需路径分解的算法TDTR来避免BUTR算法存在的冗余计算问题。TDTR通过栈来缓存已处理结点并标记其逆向传递闭包,从而尽可能早的利用结点间的父子关系来避免BUTR算法存在的冗余计算问题。算法TDTR时间与空间复杂度分别为O(wavgm)和O(n),wavg为为处理单个结点时平均访问结点数目。最后,在26个不同规模的真实数据集上,通过实验从不同角度对算法的性能进行深入比较和分析。实验结果验证了本文算法的高效性和扩展性。(本文来源于《燕山大学》期刊2016-05-01）
何琨,姬朋立,李初民[3]（2013）在《求解二维矩形Packing面积最小化问题的动态归约算法》一文中研究指出二维矩形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%.(本文来源于《软件学报》期刊2013年09期）
许道云,王晓峰[4]（2012）在《可满足性问题的归约技术(英文)》一文中研究指出通过一个恰当的归约变换,可以将一个CNF公式变换为另一个具有某种特殊结构或性质的公式,使其两者具有相同的可满足性。一个典型的归约是将一般的CNF公式变换为3-CNF公式。通过构造一些恰当的工具,可以将公式类变换为所要求的正则类。极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足。我们提供了一种归约技术,通过构造恰当的极小不可满足公式作为工具,将公式类变换为具有正则结构的公式类。研究正则结构的公式的复杂性及性质很有意义。如,将一个从3-CNF公式变换为(34)-CNF公式,这里(34)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4。因此,(34)-SAT是一个NP-完全问题,并且正则二部图的诸多良好性质对于研究正则结构的SAT问题具有许多潜在的作用。(本文来源于《逻辑学研究》期刊2012年01期）
岳昊[5]（2008）在《叁划分问题可多项式归约为唯一可达向量Petri网可达性问题》一文中研究指出为了对基于唯一可达向量Petri网(URV-PN)的密码体制进行密码分析工作,有必要对唯一可达向量网系统的数学本质和各种性质进行深入的研究.定义了扩展的叁划分问题,叁划分问题是扩展的叁划分问题的一种特殊情况;给出了一个一般的多项式时间复杂度算法构造扩展的叁划分问题的Petri网模型;证明扩展的叁划分问题有解当且仅当所构造的Petri网模型中某个标识可达;从而说明叁划分问题可多项式归约为唯一可达向量Petri网系统的可达性问题,从而给出了求解唯一可达向量网系统可达性问题的一个复杂度下界.(本文来源于《2008年全国开放式分布与并行计算机学术会议论文集(下册)》期刊2008-10-25）
岳昊[6]（2008）在《叁划分问题可多项式归约为唯一可达向量Petri网可达性问题》一文中研究指出为了对基于唯一可达向量Petri网(URV-PN)的密码体制进行密码分析工作,有必要对唯一可达向量网系统的数学本质和各种性质进行深入的研究.定义了扩展的叁划分问题,叁划分问题是扩展的叁划分问题的一种特殊情况;给出了一个一般的多项式时间复杂度算法构造扩展的叁划分问题的Petri网模型;证明扩展的叁划分问题有解当且仅当所构造的Petri网模型中某个标识可达;从而说明叁划分问题可多项式归约为唯一可达向量Petri网系统的可达性问题,从而给出了求解唯一可达向量网系统可达性问题的一个复杂度下界.(本文来源于《微电子学与计算机》期刊2008年10期）
戚玉涛,刘芳,焦李成[7]（2008）在《求解大规模TSP问题的自适应归约免疫算法》一文中研究指出从理论上分析了影响多级算法性能的因素,并以此为依据构造了求解TSP问题的自适应归约免疫算法.该算法借助归约集的进化使归约集规模自适应增长,归约边的预测精度不断提高,从而提高了算法在归约后找到全局最优解的概率.实验结果表明,该算法比其他算法获得了质量更高的解.(本文来源于《软件学报》期刊2008年06期）
曾纯强[8]（2006）在《用归约原理求解凸壳问题的计算复杂性的研究》一文中研究指出分析了利用归约原理求解凸壳问题的时间复杂度。(本文来源于《软件导刊》期刊2006年11期）
雷玉霞,刘阳,曹宝香[9]（2006）在《梵塔问题的问题归约描述和JAVA实现》一文中研究指出N阶梵塔问题是人工智能中一个很典型的智力问题.本文以问题归约的观点研究了梵塔问题,给出了N阶梵塔问题的Java算法与实现的思想,分析了算法的时间和空间复杂性以及系统的特点.(本文来源于《计算机与信息技术》期刊2006年04期）
邹鹏,周智,陈国良,顾钧[10]（2003）在《求解TSP问题的多级归约算法》一文中研究指出TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.(本文来源于《软件学报》期刊2003年01期）
问题归约论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
给定有向无环图G,G的传递归约是和G有相同传递闭包的最小唯一子图。传递归约是图论中的经典问题之一,并广泛应用于实际中简化问题的求解,包括传递闭包、背包问题、可达性问题等。然而,现有传递归约方法的计算代价高昂。随着网络技术的飞速发展和新型应用的不断涌现,实际应用中的图规模越来越大,在机器内存容量受限的情况下,已有的传递归约算法因其较高的空间复杂度面临无法使用的尴尬境地。本文从以下几个方面对有向无环图的传递归约方法进行研究,具体内容如下。首先,提出自底向上的BUTR算法。该算法首先将G分解为k条路径,以自底向上的方式处理每条路径p。其特点体现在处理每条路径p时,可以利用p中顶点间的父子关系来避免对部分顶点和边的重复访问,并保证在处理完p的所有顶点后,所有涉及到的边仅被访问一次。当处理完所有的k条路径之后,即可得到传递归约。BUTR时间与空间复杂度分别为O(km)和O(n),其中n、m分别为图G中结点和边的个数。其次,针对BUTR算法在实际应用中路径分解规模过大的问题,提出无需路径分解的算法TDTR来避免BUTR算法存在的冗余计算问题。TDTR通过栈来缓存已处理结点并标记其逆向传递闭包,从而尽可能早的利用结点间的父子关系来避免BUTR算法存在的冗余计算问题。算法TDTR时间与空间复杂度分别为O(wavgm)和O(n),wavg为为处理单个结点时平均访问结点数目。最后,在26个不同规模的真实数据集上,通过实验从不同角度对算法的性能进行深入比较和分析。实验结果验证了本文算法的高效性和扩展性。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
问题归约论文参考文献
[1].黄青华.面向大图的传递归约问题研究[D].燕山大学.2018
[2].周世杰.面向大图的传递归约问题研究[D].燕山大学.2016
[3].何琨,姬朋立,李初民.求解二维矩形Packing面积最小化问题的动态归约算法[J].软件学报.2013
[4].许道云,王晓峰.可满足性问题的归约技术(英文)[J].逻辑学研究.2012
[5].岳昊.叁划分问题可多项式归约为唯一可达向量Petri网可达性问题[C].2008年全国开放式分布与并行计算机学术会议论文集(下册).2008
[6].岳昊.叁划分问题可多项式归约为唯一可达向量Petri网可达性问题[J].微电子学与计算机.2008
[7].戚玉涛,刘芳,焦李成.求解大规模TSP问题的自适应归约免疫算法[J].软件学报.2008
[8].曾纯强.用归约原理求解凸壳问题的计算复杂性的研究[J].软件导刊.2006
[9].雷玉霞,刘阳,曹宝香.梵塔问题的问题归约描述和JAVA实现[J].计算机与信息技术.2006
[10].邹鹏,周智,陈国良,顾钧.求解TSP问题的多级归约算法[J].软件学报.2003
论文知识图
