（计算机应用技术专业论文）约束满足及其分布式求解和应用研究.pdf

中国科学技术大学博十学位论文 摘莹 摘要 约束满足可以很好地描述组合求解问题，在人工智能和计算机其他领域都有 着广泛的应用，因而成为人工智能中成功的问题求解范例之一。近来，计算机网 络和分布式计算环境在各领域的快速发展，使得很多现实世界中的组合求解问题 都具有了分布式的特点。在这一趋势下，传统的约束满足求解方法已经不能适应 分布式的组合问题求解，特别是对自治a g e n t 间需要协商求解的多a g e m 系统 更是无法应用。随着多a g e n t 系统研究的深入开展，分布式约束满足问题被正式 提出后，其模型、求解方法、隐私保护和求解效率等理论问题已引起人们的广泛 关注。 本文基于约束满足求解策略，提出了一种针对网络环境下半结构化数掘模式 变化检测的快速方法；此外，在对分布式约束满足问题及其求解方法的系统研究 和分析基础上，针对应用中新出现的隐私安全需求，提出了高效的、真正分布式 的隐私安全分布式约束满足求解方法：最后，我们用该方法对基于多a g e m 虚拟 企业中的隐私安全协商的求解问题进行了有益的探讨。论文的主要贡献和创新 有： 1 提出了一种快速的基于约束满足求解的半结构化数据模式变化检测方法。 在约束满足求解基础上，以x m l 文档为研究对象。为了有效地对x m l 数 据进行模式变化检测，提出了一种快速的半结构化数据模式变化检测方法。该方 法使用了有向标记无序树来表示x m l 文档，从中抽取出频繁子树作为模式，并 用树型模式来描述它。在此基础上，把x m l 数据模式变化检测问题转化为约束 满足求解问题，不仅针对该问题提出了一种较高效的求解算法，而且克服了一般 方法要求在有序树上进行的限制。 2 提出了一种基于权值加密的隐私安全分布式约束满足问题的求解算法。 针对分布式约束满足问题中的隐私安全保护，从求解效率角度考虑，提出了 一种基于权值加密的隐私安全分布式约束满足问题的求解算法。该算法通过对 a g e n t 内和a g e n t 问不同的约束关系进行隐私安全性分析，在加密求解过程中使 用不同的处理方式来获得更高的求解效率，利用a g e n t 自身的计算和交互特点， 不再引入额外的控制器来参与求解，真萨实现分布式的安全策略，进一步减少了 可能的信息泄漏，因而可以在确保隐私安全的前提下引入更好的启发式搜索策 摘要中同科学手立术人学博卜擎倥论文 略。 3 提出一种基于隐私安全分布式约束满足求解的多a g e n t 虚拟企业合作伙 伴选择协商模型。 以基于多a g e n t 的虚拟企业中各候选企业的隐私安全为出发点，提出一种 利用隐私安全分布式约束满足求解的多a g e n t 虚拟企业合作伙伴选择协商模型。 在该模型中，将市场各部分需求或服务建模为a g e n t ，将需求或服务之间的关系 建模为各个a g e n t 内部或a g e n t 之间的约束，a g e n t 之间通过隐私安全分布式约 束满足求解方法来实现彼此问隐私安全的协商，进而完成满足需求的合作伙伴选 择任务。 分布式问题求解的应用将依赖于分布式约束满足问题中的求解效率、隐私安 全等关键问题的有效解决，因而这些问题的研究具有重要的理论意义和应用价 值。本文针对其中的一些问题展开了研究和探讨，如何进一步研究适应分布性从 而减少通信需求和开销的分布式约束满足方法；如何平衡隐私安全性和算法效 率，在两者间取得最佳折衷等，将为分布式约束满足更好地推向实际应用奠定基 础，这也是本文今后工作的期望和目标。 关键词；约束满足；分布式人工智能：多a g e n t 系统：异步搜索：隐私安全： l i 中国科学技术大学博士学位论文 a b s t r a c t a b s t r a c t c o n s l r a i n ts a t i s f a c t i o nc a l ld e s c r i b et h ec o m b i n a t o r i a ls o l v i n gp r o b l e m ss u i t a b l y a n db ew i d e l ya p p l i e di na r t i f i c i a li n t e l l i g e n c ea n do t h e ra r e a si nc o m p u t e rs c i e n c e i t i so n eo ft h em o s ts u c c e s s f u lp r o b l e ms o l v i n gp a r a d i g m si na r t i f i c i a li n t e l l i g e n c e w i t ht h er a p i dd e v e l o p m e n to ft h ec o m p u t e rn e t w o r k sa n dt h ed i s t r i b u t e dc o m p u t i n g e n v i r o n m e n ti nm a n ya r e a s ，al o to fr e a lw o r l dc o m b i n a t o r i a ls o l v i n gp r o b l e m sh a v ea n e wc h a r a c t e r i s t i c - b e i n gd i s t r i b u t e d i nt h i st r e n d , t h et r a d i t i o n a lc e n t r a l i z e d c o n s l r i i l _ l ts a t i s f a c t i o na l g o r i t h m sc a i in o tc o p ew i t ht h es o l v i n go ft h ed i s t r i b u t e d c o m b i n a t o r i a lp r o b l e m s ；e s p e c i a l l y , i tc a nn o tb ea p p l i e di nt h em u l t i - a g e n ts y s t e m s t h a tn e e dn e g o t i a t o r ys o l v i n gb e t w e e na u t o n o m o u sa g e n t s a l o n gw i t i lt h ei n - d e p t h r e s e a r c ho fm u l t i - a g e n ts y s t e m s ，d i s t r i b u t e dc 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 mh a sb e e n p r o p o s e df o r m a l l y a n dt h e nt h et h e o r yi s s u e sa b o u tm o d e l i n g , s o l v i n ga l g o r i t h m s ， p r i v a c yp r o t e c t i o na n ds o l v i n ge f f i c i e n c y o fd i s t r i b u t e dc 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 mh a v e b e e nc o n c e r n e dm o l ea n dm o r e b a s e do nt h ec o n s t r a i n ts a t i s f a c t i o ns o l v i n gp r o t o c o l s ，w ep r o p o s eaf a s tm e t h o d o fs c h e m ac h a n g ed e t e c t i o nf o rs e m i s t r u c t u r e dd a t ai nn e t w o r ke n v i r o n m e n t i n a d d i t i o n , w em a k ei n - d e p t hs t u d i e sa n da n a l y s e s0 nt h ed i s t r i b u t e dc 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 ma n di t ss o l v i n ga l g o r i t h m s f o rt h ep r i v a c ys e c u r i t yw h i c hi st h e n e wr e q u i r e m e n ti nt h ea p p l i c a t i o n s , w ep r e s e n tah i g he f f i c i e n c ya n dr e a ld i s t r i b u t e d s o l v i n ga l g o r i t h mo fs e c u r ed i s t r i b u t e dc 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 f i n a l l y ，b a s e d o nt h ea l g o r i t h m , w em a k eab e n e f i c i a ls t u d yo nt h es o l v i n go ft h es e c u r em u l t i a g e n t n e g o t i a t i o ni nv i r t u a le n t e r p r i s e t h em a i n c o n t r i b u t i o n sa r e ： 1 p r o p o s eaf a s tm e t h o do fs c h e m ac h a n g ed e t e c t i o nf o rs e m i s t r u c t u r e dd a t a b a s e do nt h es o l v i n gs t r a t e g yo f 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 o nt h eb a s i so ft h es o l v i n gs 灯a t e g yo fc o m q ( r a i n ts a t i s f a c t i o np r o b l e m , f o r e f f i c i e n t l yd e t e c t i n gt h es c h e m ac h a n g eo f x m l d o c u m e n t s , w ep r e s e n taf a s tm e t h o d o fs c h o m ac h a n g ed e t e c t i o nf o rs e m i - s m l c m r e dd a t a - f i r s t l y , x m ld o c u m e n ti s r e p r e s e n t e da sad i r e c t i o n a ll a b e l e du n o r d e r e dt r e e ，t h es c h e m ai saf r e q u e n ts u b - t r e e e x t r a c t e df r o mt h et r e ew h i c hr e p r e s e n t sx m ld o c u m e n t t h e n , w ep r e s e n ta l l e f f i c i e n tm e t h o do f t r a n s f o r m i n gt h ep r o b l e mo f t h es c h e m ac h a n g ed e t e c t i o no f x m l d a t ai n t oc 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 ma n daf a s tc s pa l g o r i t h mf o rt h es c h e m a c h a n g ed e t e c t i o no fx m l d a t a t h em e t h o do v e r c o n l b st h er e s t r i c t i o no fo t h e r m e t h o d st h a tt h ec h a n g ed e t e c t i o ns h o u l db ed o n eo nt h eb a s i so f o r d e r e dt r e e s i r a b s t r a c t 中回车 学手支术人学博j 学位论立 2 p r o p o s e a ne n c r y p t e ds o l v i n gm e t h o df o rs e c u r ed i s t r i b u t e dc 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 mb a s e do nw e i g h t s f o rt h ep r i v a c ys e c u r i t yo fd i s t r i b u t e dc 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 ，w e e m p h a s i z eo ns o l v i n ge f f i c i e n c yt op r o p o s ea ne n c r y p t e ds o l v i n gm e t h o df o rs e c u r e d i s t r i b u t e dc 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 mb a s e do nw e i g h t s t h ea l g o r i t h ma n a l y s e s t h es e c u r i t yo fd i f f e r e n tc o n s t r a i n tr e l a t i o n s h i pi na g e n to rb e t w e e na g e n t s ，a n du s e s d i f f e r e n ta p p r o a c ht og e th i g h e re f f i c i e n c yi ne n c r y p t e ds o l v i n gp r o c e s s b e c a u s eo f t h ec h a r a c t e r i s t i c sa b o u tc o m p u t i n ga n di n t e r a c t i o no fa g e n t s ，t h ea l g o r i t h md o e sn o t n e e dt oi n t r o d u c et h e a d d i t i o n a lc o n t r o l l e ri n t ot h e s o l v i n gp r o c e s s 乃e r e a l d i s t r i b u t e ds e c u r i t yp r o t o c o li sr e a l i z e da n dt h ep r o t o c o lf u r t h e rr e d u c e st h ep o s s i b i l i t y o ft h ei n f o r m a t i o nl e a k a g e w i t he n s u r i n gp r i v a c ys e c u r i t y , w ec a ni n t r o d u c et h e b e t t e rh e u r i s t i cs e a r c hs t r a t e g yf o rs o l v i n g 3 p r e s e n tan e g o t i a t o r yp a r t n e rs e l e c t i o nm o d e lo fm u l t i a g e n tv i r t u a le n t e r p r i s e b a s e do nt h es o l v i n gm e t h o do fs e c u r ed i s t r i b u t e dc 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 f o rp r i v a c ys e c u r i t yo f e n t e r p r i s ec a n d i d a t e si nm u l t i a g e n tv i r t u a le n t e r p r i s e ，w e p r e s e n tan e g o t i a t o r yp a r t n e rs e l e c t i o nm o d e lo fm u l t i a g e n tv i r t u a le n t e r p r i s e ，w h i c h u s e st h es o l v i n gm e t h o do fs e c u r ed i s t r i b u t e dc 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 i nt h i s m o d e l ，t h em a r k e td e m a n d so rs e r v i c e sa r ef o r m a l i z e da sa g e n t s ，a n dt h er e l a t i o n s h i p b e t w e e nd e m a n d so rs e r v i c e si sf o r m a l i z e da sc o n s t r a i n t si na g e n to ra m o n ga g e n t s a g e n t sa c h i e v es e c u r en e g o t i a t i o na c c o r d i n gt ot h es o l v i n gm e t h o do fs e c u r e d i s t r i b u t e dc 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 ，a n dt h e nc o m p l e t et h ep a r t n e rs e l e c t i o n w h i c hm e e t st h es e c u r ed e m a n d t h ea p p l i c a t i o n so fd i s t r i b u t e dp r o b l e ms o l v i n gd e p e n do ne f f i c i e n ts o l v i n go f t h ee f f i c i e n c y , p r i v a c ys e c u r i t ya n do t h e rk e yi s s u e so fd i s t r i b u t e dc 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 t h u s ，t h es t u d yo ft h e s ei s s u e si so fi m p o r t a n tt h e o r e t i c a l s i g n i f i c a n c ea n dg r e a ta p p l i c a t i o nv a l u e n l ee m p h a s i so f o u rf u r t h e rr e s e a r c hw i l lb e o np r o p o s i n gab e t t e ra l g o r i t h mt oa d a p tt ot h ed i s t r i b u t i o ns o a st or e d u c e c o m m u n i c a t i o nc o s t sa n dr e q u i r e m e n t s ，a n db a l a n c i n gt h et r a d e o f fb e t w e e np r i v a c y l o s sa n de f f i c i e n c y , e t c t h et h e o r e t i c a lr e s e a r c ho ft h e s ei s s u e sw i l lp r e s e n tt h es o l i d t h e o r e t i c a lf o u n d a t i o nf o rt h ep r a c t i c a la p p l i c a t i o n s k e y w o r d s ：c o n s t r a i n ts a t i s f a c t i o n ；d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ；a s y n c h r o n o u s s e a r c h ；p r i v a c ys e c u r i t y ； 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 军， 耘一徊 立月一步 名 年 签j 1 者 沙 怍 中国科学技术大学博十学位论文 第一节前占 第一章前言 人工智能从1 9 5 6 年诞生之初，就开始了搜索算法和通用问题求解的研究。 在近5 0 年的发展中，问题求解一直是人工智能的核心理论之一，现实世界中的 很多问题都可以归结为组合求解问题，例如调度问题、规划问题、设计问题、资 源分配、图形问题、诊断问题、配置问题、定性推理、实时系统、机器人、视觉 问题、用户模型、分子生物等【2 1 。这些问题的求解通常是复杂的，往往没有算法 可以遵循，或者即使有计算方法，也是n p ( n o n - p o l y n o m i a l ) 问题。因此，利用计 算机高效而廉价的运算能力，采用启发式知识进行求解，把复杂的问题大大简化， 在浩瀚的搜索空间中迅速找到解答，具有很高的实际应用价值。约束满足问题 ( c o n s t r a n i ts a t i s f a c t i o np r o b l e m ，c s p ) 可以很好地描述人工智能和计算机其他领 域中的许多关于调度和组合优化的应用问题l 卦，随着其在理论、实验、应用上研 究的深入，已经成为人工智能中成功的问题求解范例之一。 目前计算机的应用越来越广泛，随着计算机网络、计算机通信和并发程序设 计技术的发展，分布式计算环境已成为未来的发展趋势，所需处理的问题越来越 复杂，问题求解所涉及的信息、资料、数据很难集中式地处理，并且求解过程也 难以集中控制。这种数据或知识的分布以及并发处理，对人工智能发展带来巨大 潜力的同时也带来了各种有待于解决的困难问题。 在这一发展趋势下，传统的约束满足求解方法已经不能适应分布式的约束满 足问题。随着2 0 世纪9 0 年代，多a g e n t 系统研究的开展，分布式约束满足问题 被正式提出。此后，分布式约束满足问题的模型、求解方法、隐私保护和求解效 率等理论问题都得到了相当广泛的关注。分布式约束满足问题中的求解效率、隐 私安全等核心问题的解决将是分布式问题求解走向实际应用的关键，因而分布式 约束满足问题的研究具有重要的理论意义和应用价值。 1 1 约束满足问题 现实世界中的很多问题都可以归结为组合求解问题，这些问题都是从可能的 组合和序列中搜索到所需的答案。然而现实生活和生产活动中的许多问题往往都 比较复杂，因此要从可能的组合或者序列中寻找出某种最佳调度方案，需要很大 第一章前击 中同年 学投术人学博i 学位论义 的搜索空间，可能产生组合爆炸f 2 1 ，导致问题难以求解。因此，研究者不断地探 索求解问题的有效算法，例如状态空间搜索的深度优先( 回溯法) 、宽度优先和 a + 算法、问题规约、动态规划、贪心算法、局部搜索、模拟退火、神经网络、 遗传算法等等。它们在不同问题中取得了一定的成效，具有各自的优缺点，但没 有哪一种算法完全占上风【“。 约束满足问题是问题求解中的一个研究领域，关于它的研究在人工智能领域 有着很长的历史和独特的地位1 5 1 。自1 9 7 4 年，m o n t a n a r i 在图像处理中首先提出 约束满足问题6 1 以来，约束满足作为一种重要的求解方法在计算机视觉1 7 。1 0 】、真 值维护 h - t j l 、调度 t 4 - 1 9 j 、时序推理f 砒4 1 、图形问题【2 5 06 1 、平面图设计【2 7 】、遗传实 验设计【2 8 1 、可满足性问题【2 9 1 、电路设计【、机械设计和制造【3 1 3 3 j 以及诊断推理 等3 4 1 人工智能和计算机其他领域都有应用f 3 5 1 。正因为在人工智能领域中的广泛 适用，约束满足问题一直是人工智能权威期刊a r t i f i c i a li n t e l l i g e n c e 的热点，并 有多个专题对此进行讨论；国内也有很多学者致力于约束满足问题的研究：主要 的工作有约束程序理论、设计与应用的研究【3 6 3 7 1 、约束归纳逻辑程序设计等方面 的研究1 3 8 , 3 9 1 以及约束满足问题的求解研究【4 h 2 噜等。 约束满足问题由一系列变量、变量相应的值域以及变量之问的约束关系组 成。每个约束关系都定义在变量集合的一个子集上，规定了子集中的变量可能的 取值组合。目标是为这些变量找到一组或多组满足所有约束关系的赋值。回溯搜 索以及约束一致性检查两种基本思想和引入它们中的各种启发式方法构成了多 种约束满足问题求解算法。 1 1 1 约束满足问题定义 问题求解一般包括三个基本概念：表示方式( 问题建模) 、目标以及评估函 数。表示方式可对选择的候选解进行编码；目标描述了要达到的目的；评估函数 则给出了给定表示方式下的任意特定解的质量。 根据目标可将问题求解分为以下4 类： 1 判定问题( d e c i s i o n p r o b l e m ) ：找一个解； 2 优化问题( o p t i m i z a t i o np r o b l e m ) ：找最优解( 组合优化和函数优化) ： 3 找所有解问题( s e a r c h f o r - a 1 1 s o l u t i o n sp r o b l e m ) ：找所有解： 中圈科学技术大学博十学位论文 第一节前矗 4 过强约束问题( o v e r - c o n s t r a i n t e dp r o b l e m ) ：找近似解。 研究最多的是1 、2 两种问题。第3 类问题因为其求解方法必须遍历整个搜 索空间，因此研究意义不大，除非计算机本身的计算方式有所突破【4 i 。 约束满足问题属于组合问题的判定问题，约束通常是指包含若干变量的关系 表达式，用来表示这些变量所必须满足的条件。下面给出约束满足问题的定义和 相关概念。 定义1 1 赋值 赋值是一个“变量一值”对，表示将某值赋给此变量，用s ( v ) = d ，( ded ) 表示将值d 赋给变量v ，其中d 是v 的值域。 定义1 2 约束 一个变量集合矿上的一个约束c 是该变量集合上的一个赋值集合 s ( v t ，k ) = 4 ，以 ，( d r 日，以乜) 。约束体现了变量集合中各变量之 间的逻辑关系，限制了变量的可能赋值。例如变量m ，屹之间的关系 i ；芝：l 。 就是一种约束。 定义1 3 约束满足问题 一个约束满足问题可以用三元组( 矿，d ，c ) 来表示，其中： 1 矿是变量的集合矿= h ， ； 2 d 是所有变量的值域的集合，d = d i ，d j ，) ，p 是变量v i 的所有可能 取值的有限域： 3 c 是变量之间的约束关系的集合c = c i ，q ) ，其中每个约束包含一个 矿的子集 m ， 和一个约束关系re q d j 。 约束满足方法是一种有效的问题求解方法，它为每个变量在其值域中寻找一 个赋值，使得所有约束被满足。 定义1 4 约束满足问题的解 约束满足问题的解是分配给问题中所有变量的一组满足任何约束的赋值。也 即一组对所有变量矿的赋值s ( h ，) = 喃， ，( 矗，习- - - d 。或) ， v e c 都有s ( ， ) = 以，矗) 辟。 第一章前言 中同科学技术大学博t 学位论文 定义l 5 约束网( 图) m 一个约束满足问题的约束网g ( n ，e ) 是一个无向图，j v 是结点集合，e 是边 集合。中的每个结点表示v 中的一个变量，变量之间存在的约束c 由每一对 相应结点问的边来表示。如图1 1 所示，变量v l 、v 2 之间，h 、v 3 之闯，心、b 之 间，v 2 、v 4 之间存在着约束关系。 图1 1 约束网 根据约束关系的变量集合中变量的个数，可以将约束分为一元约束c 1 、二 元约束c 2 与多元约束c i i ，因为约束关系的传递性，多元约束可以划分成多个二 元约射删。图1 2 表示了约束关系的分类，其中( a ) 表示一元约束，( b ) 表示二元 约束，( c ) 表示三元约束划分为三个二元约束。 俨i 二 图1 2 约束关系分类 约束满足问题有很多扩展问题，比如只要求取得局部解的局部约束满足问题 ( p a r t i a lc s p ) 4 5 1 ：要求所有约束都被满足，同时使代价函数取得最大或最小的约 束优化问题( c o n s t r a i n ts a t i s f a c t i o no p t i m i z a t i o np r o b l e m ，c s o p ) 【4 6 】：在变量或者 值域动态增减的条件下求解的动态约束满足问题( d y n 锄i cc s p ) 【4 7 1 等等。 1 1 2 问题建模 下面以两个经典的约束满足问题：n 皇后和图染色问题为例，介绍如何将组 合求解问题形式化为约束满足问题。 奎辞 中国科学技术大学博十学位论文 第一章前言 i 以一皇后问题( - q u e e np r o b l e m ) 以一皇后问题描述为要在n n 的棋盘上摆放n 个皇后，要求皇后两两之间不互 相攻击，也即每一行、每一列和每条对角线上只能有一个阜后存在。图1 3 是4 皇后问题的示例以及相应的约束网。 她渤她洒 ( a ) 洒 图i 3 4 皇后及相应的约束满足问题 渤 ， 洒 洒 幽 ( d ) 图1 3 中( a ) 表示在4 4 的棋盘上放置4 个皇后q l q 4 ，即为变量集合：图( b ) 表示任意行、列、对角线上不能同时有两个皇后，即为约束关系；图( c ) 是相对 应的约束满足关系网；图( d ) 是该问题的一个解。 由约束满足问题的定义，可得n 皇后问题的等价约束满足问题是： 1 变量v = 0 1 ，0 2 ，q ； 2 值域d = ( d l ，d 2 ，乜 ，v f ，d l = 1 ，n 】( 皇后在列中的位置) ： 3 约束c = c ，i v ， 1 ，甩】，c = i q ( ) d ，q ( ) q ， q ( f ) q ( ) ，q ( f ) 一q ( j ) i - _ ，q ( i ) - q ( j ) j f 图1 3 中4 皇后问题的一个解是 q l = 3 ，9 2 = l ，q 3 = 4 ，q 4 = 2 。 图染色问题( c o l o r i n gp r o b l e m ) 图染色问题描述为对给定地图上的不同区域染色，要求相邻的区域是由不同 的颜色来标识的。这个问题有两种形式，一种是寻找最少的颜色数，属于优化问 题；一种是判断能否用给定的颜色数来按照要求给地图着色，属于判定问题，可 以等价为约束满足问题。 第章前言 中田羊f 学技术人学博卜学位论史 ( b ) 图1 4 图染色及相应的约束满足问题 ( c ) 如图1 4 ( a ) 中的地图被划分为7 个区域，用红、绿、蓝三种颜色为这些区域 着色，要求相邻区域的颜色不同；图( b ) 是该问题的一个解；r e ( c ) 是相对应的约 束满足关系网，约束网中的结点表示图中的区域，用边连接的结点表示对应区域 是相邻的。 用约束图g ( n ，e ) 表示待染色的问题，是变量对应结点的集合，是边的 集合，变量表示各个区域的颜色，每个变量的值域为k 种颜色，图染色等价的约 束满足问题为： 1 变量v = “，v 2 ， ； 2 值域d = d i ，d 2 ，见) ，v i ，口= c o l o r l ，c o l o r 2 ，c o l o r k ； 3 约束c = e i v f ，_ ，e ( v i ，) ，c o l o r , c o l o r j 图1 4 所示图染色问题的一个解是 a = 红，b = 绿，c = 红，d = 蓝，e = 绿， f = 红，g = 绿 。 1 2约束满足问题求解概述 对有限域而言，约束满足问题是典型的n p 完全问题【4 8 j 。求解的复杂度是与 问题的规模指数相关的。最简单直观的搜索算法是生成一测试法 ( g e n e r a t e a n d t e s t , g t ) ，该方法系统地产生每一种可能的赋值组合。然后测试该 赋值组合是否满足所有的约束，第一个满足所有约束的赋值组合就是问题的解。 这是一种非常直观但是很没有效率的求解方法。对有个变量，每个变量的值 域大小为m 的问题而言，所有的赋值组合的规模为m “，也即求解搜索空阃大 中国科学技术大学博士学位论文 第一章前言 小足o ( m ”) ( 如图1 5 为4 - 垒后问题的搜索空间) ，当问题的规模逐渐变大时， 程序的运行时间呈指数增长，问题将变得难以解决。 图1 54 - 皇后问题的搜索空间( 部分) 为了让问题的求解更高效，可以从两个方面来考虑设计算法：一是减少所有 赋值组合的状态数目；二是不必搜索每一个解状态。经过几十年的研究，约束满 足问题目前已经拥有了各种数量丰富的求解算法，其中搜索算法作为最终解决方 法，在吸收了一致性算法等新技术后，产生了许多新的搜索算法f 4 9 1 。 1 2 1 系统搜索 系统搜索( s y s t e m a t i cs e a r c h ) 是指按照一定的次序和规则能够系统化地、完整 地搜寻问题的赋值空间。系统搜索具有求解完备性，但是效率偏低。完备性是指 在问题的解存在时，能够保证找到解，或者证明该问题不可解。 回溯法【5 舡5 2 1 是比生成一测试方法高效的一种系统搜索方法，其本质上是深度 优先搜索【5 3 1 。算法的基本思想是，对变量按照固定顺序赋值，对当前的部分赋 值进行约束冲突检查，一旦约束不满足，则算法回溯，最近被赋值的那个变量重 新进行赋值。 在回溯搜索基础上进行改进，引入启发式方法，得到的搜索算法有： 回跳搜索( b a e k j u m p i n g , b j ) 1 5 0 l ：首先对造成冲突的原因进行识别，然后在搜 第一章前言 中国科学技术大学博士学位论文 索过程中，根据冲突的原因，直接跳回与当前变量造成冲突的变量，而不是像回 溯搜索算法一样，只是简单地跳回上一个变量。回跳搜索的缺陷在于在跳跃时会 丢失一部分有用的信息，造成对效率的影响。 动态回溯搜索( d y n a m i cb a c k t r a c k i n g , d b ) 5 4 1 ：在回跳搜索的基础上，避免了 回跳的缺陷，作如下改进：记录冲突发生的原因；根据冲突情况，对变量的赋值 顺序进行重新排序。这样就避免了有效信息的丢失。 回记搜索( b a c k m a r k i n g ，b m ) s s ：使用函数m a r k ( v , 力记录当v 为d 时，与矿 发生冲突的最远的一个变量。数据结构b a c k t o ( 记录最近一次由于为v 赋值而 发生回溯的变量中最远的一个。b m 利用所记录的信息，在m a r k _ b a c k t o 两种情况下，分别对一些无效搜索进行省略。由于使用了附加的数 据结构，因此算法的复杂性明显增加。 有限差异搜索( l i m i t e dd i s c r e p a n c ys e a r c h , l d s ) 5 6 1 ：这里的差异指的是与启 发函数指定方向的差异。首先按照启发函数指定的方向进行搜索，如果搜索失败， 则从发生冲突的结点开始，以1 为步长对其它路径进行搜索，如果再次发生搜索 失败，加大搜索步长，再对其它路径进行搜索。有限差异搜索的效率完全依赖于 启发函数的优劣，而且影响效率的因素也较多。 1 2 2 局部搜索 克服系统搜索低效率的一个途径就是放弃算法的完备性，采用个易于操作 且常常能得到正确结果的过程。局部搜索的基本思路是：首先生成一个全部的、 但可能是不一致的变量赋值，然后针对所出现的约束矛盾改变某个变量的值，以 减少所违反约束的个数，如此反复，直到达到一个约束一致的赋值。局部搜索牺 牲了完备性，可以在搜索空间中自由移动，从而提高求解效率，但是它不能证明 一个问题是不可解的，甚至即便问题有解，也不能保证找到解，而且其最大的问 题在于容易陷入局部最优。 爬山搜索( h i l lc l i m b i n g , h c ) t 5 7 1 ：爬山搜索是局部搜索算法中最著名的一种。 爬山搜索可以从任意状态开始，向具有最优状态的临近状态移动。所谓临近状态， 是指被赋值的变量中任何一个变量取值的变动。 最小冲突搜索( m i n - c o n f l i c t s ，m c ) t 锯1 ：爬山搜索中，临近状态的数量太多， 中国科学技术大学博士学他论文第一章前高 共有n ( d - 1 ) 个，n 为变量数，d 为变量的可能取值数。最小冲突搜索算法在选定 临近状态时，选择引起冲突的变量。这只需变动该变量的值来得到临近状态，将 临近状态的数目降低到( 击1 ) 个。 任意步长搜索( r a n d o mw a l k ，r w ) t 5 7 1 ：无论是爬山搜索还是最小冲突搜索， 都无法避免局部最优。为了避免陷入局部最优，可以采用从临近状态中任意选择 一个状态，但是，如果没有启发函数的指导，将很难找到最终解。于是可以按 一定概率p 来指导搜索路径的选择，以p 为概率进行任意步长搜索，以( i - p ) 为概 率进行启发式搜索。启发路径通常采用最小冲突原则或最大梯度原则。 禁忌搜索( t 曲u ) f 5 9 邡】：采用禁忌列表( t a b ul i s t ) 记录已经被访问过的状态，在 以后的搜索中，不再访问这部分空间。当然与其相配套的还有一系列机制，保证 其合理有效的运行。 1 2 3 约束传播 为了降低求解约束满足问题的计算复杂度，引入了一致性技术来降低问题的 规模。将搜索算法与一致性技术结合起来的算法称为约束传播算法( c o n s t r a i n t p r o p a g a t i o n ) t 3 5 1 ，经过二十多年的改进，以弧一致性算法和路径一致性算法为基 础的约束传播算法己经越来越成熟和完善，在许多领域的应用中取得了良好的效 果。 一致性技术1 6 t l 主要包括结点一致性( n o d ec o n s i s t e n c y , n c ) 、弧一致性( a r c c o n s i s t e n c y , a c ) 和路径一致性( p a t hc o n s i s t e n c y , p c ) _ - - 2 种。此外，还有一些特殊 情况下的一致性算法，例如具有单向性的弧一致性算法( d i r e c t i o n a la r c c o n s i s t e n c y , d a c ) ，以及由几种一致算法结合起来的一致性算法，例如受限路径 一致性算法( r e s t r i c t e dp a t hc o n s i s t e n c y ) 1 6 2 1 ，单独一致性( s i n g l e t o nc o n s i s t e