导读:本文包含了动态回溯算法论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:算法,动态,背包,状态,启发式,空间,人工智能。
动态回溯算法论文文献综述
唐静[1]（2015）在《基于动态状态树的回溯算法分析》一文中研究指出首先阐述作为算法设计基本策略之一的回溯算法以及状态空间树的概念,然后提出将两者相结合的求解问题的思路,说明结合了回溯算法的动态状态树在求解既没有最优子结构也没有贪心选择性质一类问题上的突出优点。而且,该结合算法的时间复杂度远小于静态状态树,一系列的特性都突出表现了动态状态树在回溯算法应用上的诸多优点。(本文来源于《信息与电脑(理论版)》期刊2015年13期）
许苍竹,郝爽,李博宇,刘明慧[2]（2015）在《基于MAC的动态回溯算法优化》一文中研究指出针对基于MAC的动态回溯算法在求解约束满足问题时,不仅需要大量空间存储删除解释,而且回溯机制过于复杂,对经典的删除解释及动态回溯算法的回溯机制进行优化,优化后的动态回溯算法减少了存储删除解释的空间,并可仅使用一次回溯操作返回到可能导致冲突的关键变量.在最差情况下,存储删除解释的空间复杂度由O(n2 d)改进为O(nd+n2).通过结合restart技术使优化后的动态回溯算法成为完备算法.实验结果表明,优化后的完备动态回溯算法在大部分问题求解中,整体效率明显优于标准回溯算法.(本文来源于《吉林大学学报(理学版)》期刊2015年02期）
李博宇[3]（2014）在《求解约束满足问题的dom/wdeg启发式及动态回溯算法的研究》一文中研究指出约束满足问题（Constraint Satisfaction Problem）是人工智能领域的重要组成部分。它将一类现实中问题如计划调度、资源分配、生物信息等抽象为由变量、值域和约束关系叁部分组成的模型，并通过计算最终得到一个满足所有约束条件的解,继而实现了一种由现实问题转化为抽象符号问题并将其加以解决的求解方式。解决约束满足问题一般都是通过回溯算法完成的，其中包括了相容性技术、启发式及回溯机制叁个方面。其中相容性技术是目前解决约束满足问题的核心技术，它可以通过对问题相容性的检查减小问题的规模，启发式是加快求解效率的有效途径，它主要是通过决定实例化变量的先后顺序及实例化变量的赋值来实现，回溯机制则是保证了问题求解的完备性，它提供了当问题在求解遇到冲突时的解决方法。本文的内容主要有：首先对约束满足问题的相关背景知识如相容性技术、求解算法以及启发式进行研究，然后在研究的基础上对经典动态变量启发式dom/wdeg在MAC算法中的部分进行完善，以及对动态回溯算法DBT进行改进。具体工作如下：(1)通过对dom/wdeg启发式在MAC算法中求解过程的研究，比较在使用dom/wdeg启发式时，由于当不同变量的dom/wdeg比值相等时选取不同的变量所导致的求解效率的差异，并且考虑到越靠前实例化变量的选择越需要更加严谨。因此，在开始进行求解且未遇到冲突情况之前，根据问题的结构选择使用合适的静态启发式选取实例化的变量（本文给出了一个较通用的静态启发式，是通过变量值域中值的支持率来选择），并在遇到冲突情况之后，转换为使用dom/wdeg启发式选取实例化变量，改进之后的启发式称之为分级启发式。这样也就避免了在问题初始化时使用dom/wdeg启发式会存在许多dom/wdeg比值相等变量以至于无法选择的情况，并且同时尽最大可能保证了前面几个实例化变量的坚固性。(2)通过对经典的动态回溯算法进行研究，对经典的删值解释以及动态回溯算法的回溯机制进行了改进，使得改进之后的动态回溯算法可以仅使用一次回溯操作返回到可能导致冲突的关键变量。在最坏情况下，恢复变量值域的时间复杂度由原来的O(nd)改进为O(1)，且存储删值解释的空间复杂度由原来的O(n2d)改进为O(nd)，其中n表示问题中变量的数量，d表示问题中最大论域包含的值的数量。但由于改进之后的动态回溯算法属于不完备算法，因此将其结合了restart技术进行改进，使其最终成为完备算法。(本文来源于《吉林大学》期刊2014-05-01）
王萌[4]（2012）在《一种基于图分割的动态回溯算法》一文中研究指出动态回溯算法在进行回溯时保留所有已赋值变量的值,从而可能与后面赋值的变量产生冲突,其在解决不具有明显子问题结构的约束满足问题时效率较低。为此,将图分割技术应用于动态回溯,通过图分割将变量分为若干集合,当发生回溯时,不保留全部变量的值,舍弃那些与引起冲突的变量在同一集合变量中的值。实验结果表明,该算法在求解没有明显子问题结构的约束满足问题时具有较高的效率。(本文来源于《计算机工程》期刊2012年21期）
任小康,吴尚智,苟平章[5]（2007）在《基于动态状态树的回溯算法》一文中研究指出介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法。以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用。(本文来源于《计算机工程与设计》期刊2007年04期）
张治洪,刘玉贵[6]（1996）在《0／1背包问题的动态状态树的回溯算法》一文中研究指出本文给出了一个以动态状态空间树为基础的０／１背包问题的回溯算法．动态树方法对求解线性规划问题等是非常有用的，该算法所用时间比静态状态空间树方法要少．文中给出的Ｓｐａｒｋｓ算法经用Ｃ语言写成程序上机验证，思路正确(本文来源于《天津理工学院学报》期刊1996年04期）
动态回溯算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对基于MAC的动态回溯算法在求解约束满足问题时,不仅需要大量空间存储删除解释,而且回溯机制过于复杂,对经典的删除解释及动态回溯算法的回溯机制进行优化,优化后的动态回溯算法减少了存储删除解释的空间,并可仅使用一次回溯操作返回到可能导致冲突的关键变量.在最差情况下,存储删除解释的空间复杂度由O(n2 d)改进为O(nd+n2).通过结合restart技术使优化后的动态回溯算法成为完备算法.实验结果表明,优化后的完备动态回溯算法在大部分问题求解中,整体效率明显优于标准回溯算法.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
动态回溯算法论文参考文献
[1].唐静.基于动态状态树的回溯算法分析[J].信息与电脑(理论版).2015
[2].许苍竹,郝爽,李博宇,刘明慧.基于MAC的动态回溯算法优化[J].吉林大学学报(理学版).2015
[3].李博宇.求解约束满足问题的dom/wdeg启发式及动态回溯算法的研究[D].吉林大学.2014
[4].王萌.一种基于图分割的动态回溯算法[J].计算机工程.2012
[5].任小康,吴尚智,苟平章.基于动态状态树的回溯算法[J].计算机工程与设计.2007
[6].张治洪,刘玉贵.0／1背包问题的动态状态树的回溯算法[J].天津理工学院学报.1996
论文知识图
