导读:本文包含了动态约束满足问题论文开题报告文献综述及选题提纲参考文献，主要关键词:约束满足问题,分级启发式,动态回溯
动态约束满足问题论文文献综述
李博宇[1]（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）
陈恺,冯登国,苏璞睿[2]（2012）在《基于有限约束满足问题的溢出漏洞动态检测方法》一文中研究指出溢出型漏洞是最为普遍且最具危害的漏洞类型之一,溢出漏洞检测也是目前国内外研究的热点问题.目前漏洞检测方法主要分为白盒测试和黑盒测试两类.前者主要针对程序指令进行漏洞分析,但存在效率较低、检测结果不准确等缺点;后者难以保证程序覆盖的全面性与测试数据的针对性.文中提出了一种基于有限约束满足性问题(Constraint Satisfaction Problem,CSP)的溢出漏洞动态检测方法.在程序执行过程中,结合动态污点传播和动态循环分析,选取可能产生溢出漏洞的语句并生成CSP表达式,表达式包括语句的执行条件和漏洞产生条件两部分;通过对此CSP表达式化简求解,验证漏洞的存在性与漏洞的触发条件.该方法可直接分析可执行程序,解决了间接跳转、多态代码等静态分析中难以解决的问题.为了验证该方法的有效性,作者开发了一套原型系统并进行相关实验,结果表明该方法缩小了漏洞分析范围,提高了分析效率.(本文来源于《计算机学报》期刊2012年05期）
李占山,王孜文,艾阳,李宏博[3]（2011）在《基于AC-4的动态值启发式约束满足问题求解算法》一文中研究指出通过对弧相容算法AC-4的研究,提出了基于AC-4的动态值启发式约束满足问题求解算法MAC-DMSV。算法充分利用AC-4在初始化阶段建立的计数器信息,选择计数最大者为优先实例化的值。将此值启发式加入MAC算法之中,在MAC的相容性检查时,更新计数器的值,实现了动态值启发式。实验结果表明,MAC-DMSV算法比MAC和BT+MPAC算法具有更高的求解效率。(本文来源于《吉林大学学报(工学版)》期刊2011年05期）
于淼,赵政,李满天,黄天泽[4]（2011）在《动态约束满足问题及其在辅助决策系统中的应用》一文中研究指出在处理突发事件时,应急人员需要迅速地做出决策,提出处置措施,形成行动方案。突发事件极易随时间的发展和已采取的处置措施而发生改变,具有很强的实时性,需要应急人员及时做出新的决策。本文建立了突发事件模型和处置措施决策模型,由以上模型提出了一种基于动态约束满足问题(Dynamic constraint satisfaction problem,简称DCSP)的辅助决策方法,并分析了基于DCSP系统的辅助决策过程。根据真实的辅助决策系统的运行结果,本文的方法能够很好地解决突发事件辅助决策问题,能够实现快速、准确、有效的实时辅助决策。(本文来源于《Proceedings of 2011 International Conference on Software Engineering and Multimedia Communication （SEMC2011 V2）》期刊2011-07-09）
阴艳超,刘泓滨[5]（2011）在《广义动态约束满足问题的一种双层组合启发式求解算法》一文中研究指出为了求解并行协同设计过程中诸多制约关系形成的约束网络,研究动态约束满足问题,提出一种基于模糊物元分析和改进微粒群算法的双层组合启发式求解算法。将模糊物元分析理论作为算法的第一层,建立广义动态约束满足问题的可拓关系元形式化模型,并应用模糊关系元优化方法完成从求解空间到寻优空间的转换;将改进微粒群算法作为第二层,在基本微粒群算法基础上,引入柔性变异概率及动态更新响应方式提高算法对复杂动态系统环境变化的适应性,追踪协同设计进程中动态约束带来的系统极值的最新变化。通过设计实例验证所提算法的有效性。面向广义动态约束网络的双层组合优化算法为协同设计过程中的约束建模和求解提供了一种形式化和动态的研究方法。(本文来源于《机械工程学报》期刊2011年03期）
于淼,赵政,李满天,黄天泽[6]（2010）在《动态约束满足问题及其在辅助决策系统中的应用》一文中研究指出在处理突发事件时,应急人员需要迅速地做出决策,提出处置措施,形成行动方案。突发事件极易随时间的发展和已采取的处置措施而发生改变,具有很强的实时性,需要应急人员及时做出新的决策。本文建立了突发事件模型和处置措施决策模型,由以上模型提出了一种基于动态约束满足问题(Dynamic constraint satisfaction problem,简称DCSP)的辅助决策方法,并分析了基于DCSP系统的辅助决策过程。根据真实的辅助决策系统的运行结果,本文的方法能够很好地解决突发事件辅助决策问题,能够实现快速、准确、有效的实时辅助决策。(本文来源于《Proceedings of 2010 International Conference on Broadcast Technology and Multimedia Communication(Volume 2)》期刊2010-12-13）
冯欣,唐立新,王梦光[7]（2006）在《动态加强CPT解job-shop调度约束满足优化问题》一文中研究指出带有相同到达期与交货期的job-shop调度问题(JSSP)作为多种实际生产调度问题简化模型,是一类典型强NP-hard问题.对优化目标是最小化最大完工时间的JSSP问题,建立了约束满足优化问题模型(JSSC-SOP).利用弧一致约束传播算法和深度优先启发式构造活动调度,逐步加入新约束,实现活动调度集的部分列举与寻优.提出3种动态加强约束传播技术(CPT),嵌入搜索过程,提高求解效率.最后通过随机生成的实例,验证了各方法可行性与有效性.(本文来源于《系统工程学报》期刊2006年06期）
李伟,刘光复[8]（2005）在《一类基于动态约束满足问题的产品配置方法》一文中研究指出分析了传统约束满足问题在表示产品配置中动态配置知识上的缺陷,对传统约束满足问题的概念进行了扩展,提出了一类动态约束满足问题,能够表示配置中的动态配置知识,比传统约束满足问题具有更强的知识表示能力,更小的搜索空间和更好的计算复杂度,最后给出了基于动态约束满足问题的产品配置仿真。(本文来源于《机械科学与技术》期刊2005年04期）
刘洋,陈英武[9]（2004）在《动态约束满足及其在资源调度问题中的应用》一文中研究指出论文系统地论述了动态约束满足技术的基本理论与方法,建立了动态约束满足技术的基本分析框架,给出了动态约束满足在Job-Shop问题中的应用实例。(本文来源于《计算机工程与应用》期刊2004年27期）
动态约束满足问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
溢出型漏洞是最为普遍且最具危害的漏洞类型之一,溢出漏洞检测也是目前国内外研究的热点问题.目前漏洞检测方法主要分为白盒测试和黑盒测试两类.前者主要针对程序指令进行漏洞分析,但存在效率较低、检测结果不准确等缺点;后者难以保证程序覆盖的全面性与测试数据的针对性.文中提出了一种基于有限约束满足性问题(Constraint Satisfaction Problem,CSP)的溢出漏洞动态检测方法.在程序执行过程中,结合动态污点传播和动态循环分析,选取可能产生溢出漏洞的语句并生成CSP表达式,表达式包括语句的执行条件和漏洞产生条件两部分;通过对此CSP表达式化简求解,验证漏洞的存在性与漏洞的触发条件.该方法可直接分析可执行程序,解决了间接跳转、多态代码等静态分析中难以解决的问题.为了验证该方法的有效性,作者开发了一套原型系统并进行相关实验,结果表明该方法缩小了漏洞分析范围,提高了分析效率.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
动态约束满足问题论文参考文献
[1].李博宇.求解约束满足问题的dom/wdeg启发式及动态回溯算法的研究[D].吉林大学.2014
[2].陈恺,冯登国,苏璞睿.基于有限约束满足问题的溢出漏洞动态检测方法[J].计算机学报.2012
[3].李占山,王孜文,艾阳,李宏博.基于AC-4的动态值启发式约束满足问题求解算法[J].吉林大学学报(工学版).2011
[4].于淼,赵政,李满天,黄天泽.动态约束满足问题及其在辅助决策系统中的应用[C].Proceedingsof2011InternationalConferenceonSoftwareEngineeringandMultimediaCommunication（SEMC2011V2）.2011
[5].阴艳超,刘泓滨.广义动态约束满足问题的一种双层组合启发式求解算法[J].机械工程学报.2011
[6].于淼,赵政,李满天,黄天泽.动态约束满足问题及其在辅助决策系统中的应用[C].Proceedingsof2010InternationalConferenceonBroadcastTechnologyandMultimediaCommunication(Volume2).2010
[7].冯欣,唐立新,王梦光.动态加强CPT解job-shop调度约束满足优化问题[J].系统工程学报.2006
[8].李伟,刘光复.一类基于动态约束满足问题的产品配置方法[J].机械科学与技术.2005
[9].刘洋,陈英武.动态约束满足及其在资源调度问题中的应用[J].计算机工程与应用.2004