（计算机应用技术专业论文）基于动态约束满足的软件过程调度模型.pdf

基于动态约束满足的软件过程调度模型 摘要 由于在软件产品的开发过程中，需要安排的任务和资源约束过多， 且由于外界因素的影响，软件开发项目处于一个动态环境中，因此确 定任务的时序以及资源的分配需要耗费大量的精力和体力。如何调配 资源分配任务才能满足项目需求，保证软件质量，保证资源得到最优 配置，保证在最短的时间内完成所有的任务，是大规模软件开发必须 解决的问题。 由于软件过程的动态性，本文将软件过程划分为一系列任务，提 出一种基于动态约束满足的软件过程调度模型，使得软件过程能够及 时调整、改进，以适应不断变化的外部环境，有效地帮助软件企业在 提高管理效率，降低管理成本。本文的主要工作是围绕约束满足问题 而展开的，具体研究内容如下： 文章首先介绍了约束满足问题的基本概念，讨论了约束满足问题 求解策略，预处理技术，搜索次序对搜索效率的影响以及最优化约束 满足问题等。然后本文系统地介绍了动态约束满足问题的概念，不同 的问题类型与求解不同类型问题的方法，最后介绍了调度的概念，分 析了软件过程调度中的难点。 在此基础上，建立了基于动态约束满足问题的软件过程基本分析 框架，并给出了其在软件过程问题中的应用实例，并通过实验证明该 北京化工大学硕士学位论文 模型在实际应用中可行。 关键词：软件过程；动态任务调度；约束满足 i i a b s t ra c t d y n a m i cc o n s t r a i n ts a t i s f a c t i o n b a s e d s o f t 厂a r ep r o c e s ss c h e d u l i n gm o d e l a b s t r a ct i nt h ep r o c e s so fs o f t w a r ep r o d u c td e v e l o p m e n t ，b e c a u s et h e r ea r es o m a n yt a s k sn e e d e dt oa r r a n g ea n dc o n s t r a i n e dr e s o u r c e s ，a n db e c a u s et h e i m p a c to fe x t e r n a lf a c t o r s ，s o f t w a r ed e v e l o p m e n tp r o j e c t sa r eu s u a l l yi na d y n a m i ce n v i r o n m e n t t h e r e f o r e ，i no r d e rt od e t e r m i n et h et i m i n go ft a s k s a n da l l o c a t et h el i m i t e dr e s o u r c e sr e q u i r e sal o to fe n e r g ya n ds t r e n g t h s o ， h o wt oa l l o c a t er e s o u r c e sa n da s s i g nt a s k st om e e tp r o j e c tr e q u i r e m e n t s ， t oe n s u r e o p t i m a l a l l o c a t i o no fr e s o u r c e s ，t oe n s u r et h es o f t w a r e q u a l i t y ，a n dt oe n s u r et h ec o m p l e t i o no fa l lt a s k sw i t h i nt h es h o r e s tt i m e i st h e p r o b l e mw h i c hl a r g e s c a l e s o f t w a r e d e v e l o p m e n tm u s tb e a d d r e s s e d b e c a u s eo ft h ed y n a m i cn a t u r eo fs o f t w a r ep r o c e s s ，t h i sa r t i c l ed i v i d e s t h es o f t w a r ep r o c e s s e si n t oas e r i e so ft a s k s ，a n dp r o p o s e sas o f t w a r e p r o c e s ss c h e d u l i n gm o d e lb a s e do nd y n a m i cc o n s t r a i n ts a t i s f a c t i o n ， w h i c hm a k et h es o f t w a r ep r o c e s sa d j u s ta n di m p r o v ei no r d e rt oa d a p tt o t h ec h a n g i n ge x t e r n a le n v i r o n m e n t ，a n dc a na l s oe f f e c t i v e l yh e l ps o f t w a r e c o m p a n i e si m p r o v em a n a g e m e n te f f i c i e n c ya n dr e d u c em a n a g e m e n tc o s t s i i i 北京化t 大学硕士学位论文 t h em a i nt a s ko ft h i sa r t i c l ei st os t a r ta r o u n dt h ec o n s t r a i n ts a t i s f a c t i o n p r o b l e m a n dt h es p e c i f i cr e s e a r c hc o n t e n t sa r ea sf o l l o w s ： f i r s tt h i sa r t i c l ei n t r o d u c e st h eb a s i c c o n c e p t s o fc o n s t r a i n t s a t i s f a c t i o np r o b l e m sa n dd i s c u s s e st h es t r a t e g i e so fs o l v i n gc o n s t r a i n t s a t i s f a c t i o np r o b l e m ，p r e t r e a t m e n tt e c h n o l o g ya n ds e a r c ho r d e r so nt h e s e a r c he f f i c i e n c y t h e nt h i sa r t i c l ei n t r o d u c e ss y s t e m l yt h ec o n c e p to f d y n a m i cc o n s t r a i n ts a t i s f a c t i o np r o b l e m ，d i f f e r e n tt y p e so fd y n a m i c c o n s t r a i n ts a t i s f a c t i o np r o b l e m sa n dm e t h o d so f s o l v i n gd i f f e r e n tt y p e so f d y n a m i cc o n s t r a i n ts a t i s f a c t i o np r o b l e m s a tl a s t ，t h i sa r t i c l ei n t r o d u c e s t h ec o n c e p to fs c h e d u l i n ga n da n a l y s i so ft h es o f t w a r ep r o c e s ss c h e d u l i n g d i f f i c u l t i e s o nt h i sb a s i s ，e s t a b l i s ha na n a l y t i c a lf r a m e w o r ko fs o f t w a r ep r o c e s s w h i c hb a s e do nd y n a m i cc o n s t r a i n ts a t i s f a c t i o na n dg i v e sa na p p l i c a t i o n e x a m p l ea p p l i e di nt h es o f t - w a r ep r o c e s s f i n a l l y , t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h em o d e lf e a s i b l ei np r a c t i c a la p p l i c a t i o n s k e yw o r d s ：s o f t w a r ep r o c e s s ，d y n a m i ct a s ko r i e n t e ds c h e d u l i n g ， c o n s t r a i n ts a t i s f a c t i o n i v 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：虚丝：日期：兰三 盗生笪2 垒： 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名： 导师签名： 壅竺日期：掣堂! _ 皇 日期：z , , t o y - 相o b 第一章绪论 1 1 研究背景 第一章绪论 在世界范围内，软件的需求正以非常快的速度增长，这种高速的增长使得软 件开发活动急剧地增长，人们逐渐意识到软件产品的质量在很大程度上取决于产 品开发时所使用的软件过程【i 】，软件开发过程是一个为建造高质量软件所需完成 的任务的框架，即形成软件产品的一系列步骤，包括中间产品、资源、角色及过 程中采取的方法、工具等范畴。生产高质量的软件产品需要有高质量的软件过程。 以往的情况都是软件开发人员对任务集合根据已有资源进行手动安排，确定 任务的时序以及资源的分配，然而，一旦需要安排的任务和资源约束过多，那么 这将十分繁琐，耗费大量的精力和体力。而且，由于影响软件开发的各种因素， 如技术的不断发展、市场的不断变化、资源( 如仪器) 的损坏、软件周期的变更、 人员的经常流动以及商业环境的持续变化，软件过程始终处于一个动态的环境 中，在软件生命周期内会出现很多新需求，经历许多新变更，若采用人工的方式 在有限的时间和精力下，根本无法及时有效地完成软件调度任务。因此，一个高 质量的软件过程也必须是一个持续不断改进的过程，开发高效且实用的软件调度 模型已成为众多软件企业的迫切需求。 调度是为了实现某一目的而对共同使用的资源实行时间分配【2 】。调度理论广 泛应用在能源、制造、教育等众多领域。软件过程的调度是一个n p 完全问题， 如何在不断变化的外界环境中，合理的调度软件生命周期的各个任务，如何才能 使资源得到最优的配置，在最短的时间内完成所有的任务，保证软件项目能够如 期完成是大规模软件开发必须解决的问题，也一直是困扰业界的难点。目前求解 调度问题方法有遗传算法【3 】【4 】、微粒群优化算法【弱、基于神经网络的方法【6 1 、以 及数学规划等。 经典的约束满足问题( c o n s t r a i n ts a t i s f a c t i o np r o b l e m s c s p ) ，是由一个变量集 合、各个变量的值域和一个限制变量取值的约束集合所组成，约束满足问题是人 工智能中相当活跃的研究领域，在许多实际问题中都得到了广泛的应用，它能很 好地描述智能领域的组合、调度和规划等复杂问题，尤其适用于表示和求解大规 模的组台优化问题。目前，基于c s p 的调度方法研究主要集中在如何提高算法 的搜索效率上，但采用c s p 解决调度问题时，它的处理能力遇到了巨大的挑战， 这是因为当为某个问题建立模型的时候，这个模型初始时刻就被确定了下来，并 且这个模型是静态的，不能随着环境的变化而改变，因此很难用经典的约束满足 北京化t 大学硕士学位论文 问题来建模和求解。 基于以上背景本文采用动态约束满足方法解决软件过程中任务的调度问题， 通过一致性技术，在搜索中可以有效地缩减变量论域，大幅度缩减了软件过程任 务调度的搜索空间，通过软件过程动态约束满足求解器保证在任务调度过程中的 稳定性，有效地帮助了软件企业在实施c m m c m m i 软件过程中提高管理效率， 降低管理成本。 1 2 研究现状 调度问题 在对调度问题的研究方法上，最初是集中在数学规划，仿真和简单的规则上， 但这些方法对解决复杂的调度问题并不理想，随着各种新的相关学科与优化技术 的建立与发展基于人工智能、计算智能和实时智能的调度方法逐渐成为主流。现 有的调度算法大体分为最优化方法和近似方法两大类： 最优化方法能获得问题的最优解，但在建模时往往要根据某些简化的假设， 不能充分反映生产实际的复杂性。用这些方法表达复杂的约束是很困难的，当调 度问题规模较大时，最优化方法的求解难度急剧上升，其结果与实际应用存在较 大距离。 近似方法在计算时间和调度效果两者之间进行折中，以较小的计算时间获得 问题的次优解或满意解，而调度问题的次优解或满意解也能满足实际应用的要 求，因此近似方法成为一种可行的选择。近年来，遗传算法( g e n e t i ca l g o r i t h m s g a s ) 、禁忌搜索算法等近似算法在车间调度中获得应用并取得许多研究成果。 g a s 由于可能产生大量的非法解而使其效率下降。而禁忌搜索算法是基于邻域的 搜索方法，其优化性能依赖于初始解和邻域构造方法，但通常一个高质量的初始 解的产生是很困难的。 软件过程研究现状 随着软件开发成本的不断提高，软件开发组织对软件系统的质量和项目成本 及进度越来越关心，开始对软件工程方法进行深入的研究，不断提出和改进软件 工程方面的技术、方法和工具，但软件项目的质量没有得到比较明显的提高，目 前人们将注意力转到过程规范、控制和改进领域，认为只有将过程规范化并进行 度量和不断改进，才能生产出高质量的软件产品。过程方法的提出和运用是项目 管理和组织管理理论的一大进步，这在i s o 制定的质量管理体系标准中有很好的 体现。但保证软件产品质量仅仅依靠过程的规范化是不够的，还必须对规范化的 过程进行度量，以便于软件开发组织掌握各过程的实施情况、过程的优缺点、过 程能力及特性等。 2 第一章绪论 纵观软件工程领域的研究和实践，分析目前现状和存在的问题，可以归纳为 如下几方面： 1 ) 对软件开发成本和进度的估计常常很不准确。 2 ) 软件过程模型缺乏“柔性，不适应多变的开发环境。 3 ) 管理与技术的脱节，造成实施上的困难。 4 ) 用户对已完成的软件系统不满意的现象经常发生。 5 ) 软件成本在计算机系统总成本中所占的比例逐年上升。 6 ) 标准的滥用与质量管理的脱位。 1 3 论文的组织 本论文共分七章： 第一章介绍了论文的研究背景以及研究现状。 第二章介绍了约束的概念与约束的性质，介绍了约束满足问题的定义，适用 范围，以及形式化表示方式，最后，给出一些与约束满足问题相关的定义。 第三章主要介绍了约束满足问题求解策略，对各种求解策略的效率进行了详 细地分析，给出不同算法的应用示例，分析了不同算法所存在的问题，比较了它 们的优缺点。详细地介绍了各种不同的预处理技术，说明了不同技术之间的联系， 并比较了它们的效率。然后介绍了搜索次序对求解约束满足问题的影响，给出了 多种排序算法的基本思想与求解示例，并对这些排序算法加以比较。最后介绍了 最优化约束满足问题的概念以及求解该问题所采用的方法，并给出了算法的应用 示例。 第四章介绍了动态约束满足问题的概念，不同的表示形式以及相应的求解方 法，并给出了不同求解方法的应用示例。 第五章介绍了基于约束的调度的概念，约束程序设计的概念，在此基础上提 出了软件过程调度模型及相应的形式化描述，并设计了软件过程动态约束满足求 解器。 第六章通过实验论证该求解器的有效性。 第七章总结了论文的工作，并对下一步的工作进行了展望。 3 第二章约束满足问题 2 1 约束 第二章约束满足问题 约束( c o n s r t a i n t ) 是一个包含若干变量的关系表达式，用来描述领域对象的性 质，相互之间的关系以及求解的目标。约束的例子如：两个变量的和等于5 0 ， 地图中两个相邻城市的着色不得相同，升降机所能承载的人数不得超过l o ，商 店的开放时间从早上1 0 点至下午4 点等。约束可以表示为多种形式，例如函数、 等式、不等式以及矩阵等等。 约束通常以说明性的方式表示领域中的问题，求解时只要用约束定义出问题 的目标及实体间的关系，而不必涉及问题求解的细节。此外，约束表示直观地对 应于领域问题的原始描述，简单自然，宜于理解和维护。 对于给定的约束c ，定义最简单的约束形式为基本约束( p r i m i t i v ec o n s t r a i n t ) 。 基本约束由约束论域c 中的约束关系符号和一定数量的参数构成。这些参数由c 中的常数、函数和变量构成。例如：y 。 若p 是一个约束满足问题，则可以表示为c s p ( p ) 。 定义2 3 约束满足问题的解定义为每个变量赋一个其值域中的值，使之满足 约束集合c 中的所有约束。形式化地，约束满足问题的解定义如下： v c s p ( ( z ，d ，c ) ) ：v 毛，屯，毛z ：( v m d x , ，吃吃，屹d x ： s o l u t i o n t u p l e ( ( ) ，( z ，d ，c ) ) 兰 “z = 五，艺，) ) 人( r e c ：s a t i s f i e s ( ( ，c ) ) ) 定义2 4 如果两个约束满足问题的变量有限集是相同的，而且它们所有的解 都相同，则说这两个约束满足问题是等价的。 定义2 5 一个c s p ( z 9d ，o 是k 可满足的，当且仅当z 中所有由k 个变量组 成的子集都存在一组标识使得这组标识满足所有和它们相关的约束。 定义2 6 如果两个约束满足问题的变量的值域相同，并且它们的解也相同， 则说这两个约束满足问题是等价的。 6 第三章约束满足问题的求解 3 1 引言 第三章约束满足问题的求解 经典的约束满足问题属于n p 困难问题 1 0 1 ，解决c s p 问题的方法多种多样，基 本搜索方法如图3 1 a 所示，通常是采用某些形式的搜索策略，系统化的生成和 测试每个可能的变量赋值组合，检查它是否满足所有约束。比较著名的基本搜索 方法有生成与测试法，回溯法，回跳算法等。由于c s p 属于n p 困难问题，因此 在解决c s p 的过程中，搜索方法的效率成为了关键。 图3 - 1 经典约束满足问题算法 f i g 3 - 1c l a s s i c a la l g o r i t h mf o rc o n s t r a i n ts a t i s f a c t i o np r o b l e m s 鉴于问题的复杂性，在使用基本搜索方法搜索变量的可能取值之前，可以采 用预处理( p r e - p m c e s s i n g ) 的方式如：一致性技术【l l 】对问题进行简化。即预处理与 基本搜索方法相结合的方式，如图3 1 b 所示。预处理技术可以在早期有效的删 除许多不满足约束条件的变量取值，从而大大的减小待解决问题的搜索空间，在 此基础上若优先对值域最小的变量进行赋值还可以及早发现当前赋值中的冲突。 然而，仅仅采用预处理的方式对于解决问题的效率来说是有限的。可以在问 题的搜索过程中结合一致性增强技术，随着搜索问题的进行不断减小问题的规 模，即采用混合搜索的方式，如图3 1 c 所示。该算法基于这样一个事实：随着 7 北京化工大学硕士学位论文 搜索过程的不断进行，可以根据上一次搜索状态下变量的取值结果，通过一致性 增强( c o n s i s t e n c ye n f o r c i n g ) 技术修剪剩余变量值域中的部分与已赋值变量不满足 约束集合中的相关约束的候选值，即：不相容的候选值。这样可以形成规模较小 的经过简化的子问题，接着进入下一轮的搜索，重复该过程直到找到该问题的解， 或证明该问题无解。 3 2 约束满足问题求解策略 一个约束满足问题可以用图的形式来描述，并称这个图为约束网络( c o n s t r a i n t n e t w o r k ) 1 2 】。这个约束网络可以用来指导c s p 的求解。当c s p 最多包含二元约 束( 那些只涉及两个变量的约束) 可以将其视为一个约束f 虱( c o r l s t r a i n tg r a p h ) 。每个 节点代表一个变量，约束通过有方向的弧表示。当存在弧a r c ( i ，) 时，根据约束 的性质，也同时存在弧a r c ( i ，f ) ，因为两个变量f ，的值域的笛卡尔乘积皿d ， 与d ，皿确定了相同的集合，即c ( 玉，x ，) = c ( z ，薯) 。如图1 2 所示的约束图，只 显示了单方向的弧a r c ( i ，) ，表示约束关系的。 z i ! d l = 只k ，_ b 现：d 2 = e 厶j 鼢：d ：l = k 玩 x 4 ，d 4 = k z e ，b ， 图3 - 2 算法示例 f i 9 3 - 2a l g o r i t h me x a m p l e 3 2 1 生成与测试方法 生成与测试( g e n e r a t ea n dt e s o 方法是解决c s p 最简单的方法。该方法生成 变量的所有可能的赋值组合，对其进行测试，并检查所生成的赋值组合是否满足 约束集合中的所有约束。在最坏的情况下，该方法生成与测试的赋值组合的数量 是c s p 所有变量笛卡儿积的组合数，其最坏的计算时问复杂度为o ( e k 2 刀) ，显 然随着问题规模的增大，问题的求解将变得因计算量很大而不无法在有限时问内 完成求解。 8 第三章约束满足问题的求解 图3 - 3 生成与测试算法示例 f i g 3 - 3a l g o r i t h me x a m p l eo f g e n e r a t ea n dt e s t 图3 3 显示了采用生成与测试方式对图3 2 所示示例进行求解所产生的生成 树的结构图。s o l u t i o n x l = b ，x 2 = j ，毛= v ，= k ) 为问题的解。对于五所产生的 失败节点在图中用倒三角形表示。该方法之所以效率低下，是因为在搜索过程中， 每次扩展叶节点之前并未进行一致性检测，因而盲目的生成了大量的错误取值， 直到测试阶段才发现因为不满足待求解问题的相关约束而淘汰。 3 2 2 回溯法 回溯法将搜索过程看做是反复地为变量选择一个与已求得的满足约束条件 的部分解相容的值来增量地把部分解扩展到最终解，如此反复直至求得满足约束 条件的问题的解，或者证明问题无解【1 3 1 。 在回溯算法执行过程中，顺序的实例化每一个变量，例如：五是将要被实例 化的变量，五，五一是已经被实例化的变量。当对鼍进行实例化的时候，检查玉 的值域毋的所有取值，若对五的赋值与已赋值的变量违反约束集合的任一约束， 则不再对此节点进行扩展，若口中的所有取值均违反相关约束就回溯到最近的 仍有可选值的变量，然后用其论域中的其它值来实例化这个变量。重复这个过程， 如果最终每一个变量都被实例化了，则找到问题的一个解；如果最终没有变量可 以回溯，则说明这个约束满足问题无解。 图3 4 显示了采用回溯方法对图3 2 所示示例进行求解所产生的生成树结构 图。黑色与白色分别代表在搜索过程中所生成的成功与失败的赋值节点。可以清 晰地看到回溯算法相对于生成与测试算法在效率方面的提升。当算法发现对变量 的赋值违反约束的时候，回溯法立即剪去以它为根节点的子树，从而减小了问题 的搜索空间，但是，该算法仅仅是对赋值检查和回溯，经常会存在很多的部分赋 值并不能形成一个解，但却总是被搜索，这样的搜索工作显然是多余的，通常被 称为抖动问题( h t a r h s i n g ) ，如图3 - 4 方框中的节点所示，该问题直接影响了算法 的求解效率。 9 k 寸 叠 寸 对 i v t 北京化工人学硕士学位论文 口n 翻岫g & b v 蛔 图3 - 4 回溯算法示例 f i g 3 - 4b a c k t r a c k i n ga l g o r i t h me x a m p l e 抖动问题 影响回溯搜索算法效率的最大问题是，当搜索进行到某一时刻，实例化相应 变量的时候，可能会产生相同的子树，而这些子树可能因为同样的原因而导致搜 索过程的失败即所谓的抖动问题【1 4 1 ，由于不断重复的搜索过程使得算法做了大量 的冗余工作，降低了搜索效率。例如：t 与玉是c s p 问题的两个变量，并且它 们之间存在约束关系。当被赋予某个值的时候，若t 值域皿中的值均不满足t 与薯之间的约束，搜索算法将在树结构的第i 层产生失败节点，因此原因而导致 失败的情况将会在后续搜索的第g 层与第i 层之间重复出现，因而降低了搜索的 效率。 这一点可以在图3 - 4 中清晰地看到，五与之间存在约束条件即x 。 或 n ) 时五与之间的约束关系进行过检验，所以b m 对于变量x 3 相对于五的约 束检查必然成功，因此无需进行二次检验。相似地，对于“r e g i o n 2 所标示的 区域，当b m 算法将值域的 k ) 、 j ) 、 e ) 或 b ) 取值赋给变量时，相对于五 的约束检查必然失败，同样无需进行二次检验。 1 2 第三章约束满足问题的求解 3 3 预处理技术 预处理技术使得算法在解决c s p 问题之前，根据问题的约束，通过约束传播 技术【1 1 7 】在使用搜索算法解决问题之前就把所有不满足约束条件的值从值域中去 除，从而所有变量的值域得到更新，并产生了与原有约束满足问题相等价的问题。 由于变量的值域的规模减少了，所以使搜索工作量减少，进而使问题变得更容易 求解，从而在搜索的时候降低问题的复杂度。预处理技术还可以应用在搜索过程 中，当通过约束传播技术发现不满足约束条件的节点时，可以剪掉以它为根的子 树。约束传播技术是预处理的核心技术，它在不同的文献中有不同的称谓，比如： 约束松弛( c o n s t r a i n tr e l a x a t i o n ) ，过滤算法( f i l t e r i n ga l g o r i t h m ) ，紧缩算法( n a r r o w i n g a l g o r i t h m ) 以及约束推理( c o n s t r a i n ti n f e r e n c e ) 等。 通常来说，采用预处理技术可以给问题的处理带来以下好处：( 1 ) 减小搜索 空间( 2 ) 避免了对会产生无解的子树的重复搜索( 3 ) 可以及早的发现无解状 态，即：当对变量赋值时，如采用约束传播技术发现某个未赋值的变量的值域变 为空集，则说明当前赋值不是c s p 问题的解。 基本的预处理方式包括节点一致( n o d e - c o n s i s t e n c yn o 、弧一致( a r c c o n s i s t e n c ya c ) 和路径一致( p a t h c o n s i s t e n c yp c - l 。 3 3 1 节点一致 节点一致是最简单的预处理方式，它保证对于每一个玉皿，与玉相关的一 元约束均可以得到满足，即：如果对于变量x 当前值域中的每个值，关于x 的所 有一元约束都被满足，则说明该变量时节点一致的。 如果变量x 的值域口中只包含一个值a ，如果值a 不满足x 上的某个一元约 束，则值a 赋予变量x 将导致失败。这样，从变量x 的值域域中删除所有不满 足关于x 的一元约束的值，就可以消除节点的不一致。由于一元约束仅影响单个 变量，因此对节点采用节点一致技术不会影响其它节点。 节点一致算法的伪代码实现如图3 7 所示： 图3 - 7 节点一致算法 f i g 3 - 7n o d ec o n s i s t e n c ya l g o r i t h m 1 3 北京化工人学硕十学位论文 3 3 2 弧一致( a r c c o n s i s t e n c ya c ) 弧一致在解决约束满足问题中起着重要作用。一方面，在搜索之前进行弧一 致的检查，可以缩小问题的规模；另一方面，在搜索过程中保持弧一致，相比其 它算法在付出一定的时空代价的情况下能够得到合理的问题规模的压缩，因此被 认为是处理大规模难解问题的行之有效的方法。 弧一致的定义如下： 假设c s p 中存在两个变量x i 其值域为皿与而其值域为d ，它们之间存在一 个二元约束c 幢若d 。中的任一元素a ( 口1 9 , ) ，都可以在d 2 中找到一个对应的元 素b ( 6 d 2 ) ，使得五= a 与x 2 = 6 可以满足约束c l ，则称变量五相对于变量艺弧 一致。若对于二元约束1 7 1 ，存在变量五相对于变量而弧一致，同时存在变量而相 对于变量五弧一致时，称这个约束弧一致，而当约束满足问题中所有的约束都是 弧一致时，称这个约束满足问题是弧一致的。 二n 如果对于任何的a d l ，都不存在相对应的6 口，使得五= a 与x 2 = b 满足 二元约束c i ，。则可以将a 从口中删除，因为a 无法构成任何满足约束条件的可 行解。从b 中删去不满足条件的值a ，会使得变量x l 与变量而之间具有弧一致的 性质。 x l ，d r - p , k , b x 和脚 k j ，e , b a ) _ | h x i , d i = b ) ( 4 ，d ： i o ，e , b b ) - 坩 x i ，d i = b ， 表示 当变量取值为0 即x o = 0 时，算法支持五= 2 ，而= 4 ，而= 6 与毛= 8 。当= 0 从的值域中删除的时候，这个集合帮助鉴别哪些变量的赋值需要被检查。对于 x o = 0 时，根据约束条件c r ，从变量五那里得到一个支持，即玉= 2 ，因此， c o u n t e r s ( o ，1 ) ，0 】_ l 。同理，可以得出c o u n t e r s ( o ，1 ) ，1 】= 1 ，因为玉= 3 是变量提 供给变量= l 的唯一支持。同样的，如果变量x o = 0 ，在满足约束条件的情况 下，变量艺可以取两个值分别是4 和6 ，因此，c o u n t e r s ( o ，2 ) ，0 】- 2 。根据同样 的原理，函数的其它取值如下：c o u n t e r s ( o ，2 ) ，l 】- l ，c o u n t e r s ( o ，3 ) ，0 】- 1 ， c o u n t e r s ( o ，3 ) ，1 】_ l 。 布尔矩阵m 通过如下的方式进行初始化，首先对于变量x 的每个取值a ，根 据约束条件e 。( 所有除变量x 以外的其它变量y ) 对其进行检查。如果不存在值b 使得( z = a ，y = 6 ) 满足约束条件，则将值a 从变量x 的值域皿中删除，并且将矩 阵m i x ，a 】的值置为1 ( 用来表示工= a 已经被删除) 。所有被删除的赋值存入到一个 名为l i s t 的队列中，以便此后的进一步处理。 如前面所示的例子，如果变量x o = l 的取值被拒绝，则m o ，1 】- l 且x o = l 被添 加到队列l i s t 中。当这个赋值被处理的时候，算法将会查看支持集合，由 于( 1 ，3 )