论文部分内容阅读
约束满足可以很好地描述组合求解问题,在人工智能和计算机其他领域都有着广泛的应用,因而成为人工智能中成功的问题求解范例之一。近来,计算机网络和分布式计算环境在各领域的快速发展,使得很多现实世界中的组合求解问题都具有了分布式的特点。在这一趋势下,传统的约束满足求解方法已经不能适应分布式的组合问题求解,特别是对自治Agent间需要协商求解的多Agent系统更是无法应用。随着多Agent系统研究的深入开展,分布式约束满足问题被正式提出后,其模型、求解方法、隐私保护和求解效率等理论问题已引起人们的广泛关注。本文基于约束满足求解策略,提出了一种针对网络环境下半结构化数据模式变化检测的快速方法;此外,在对分布式约束满足问题及其求解方法的系统研究和分析基础上,针对应用中新出现的隐私安全需求,提出了高效的、真正分布式的隐私安全分布式约束满足求解方法:最后,我们用该方法对基于多Agent虚拟企业中的隐私安全协商的求解问题进行了有益的探讨。论文的主要贡献和创新有:1.提出了一种快速的基于约束满足求解的半结构化数据模式变化检测方法。在约束满足求解基础上,以XML文档为研究对象,为了有效地对XML数据进行模式变化检测,提出了一种快速的半结构化数据模式变化检测方法。该方法使用了有向标记无序树来表示XML文档,从中抽取出频繁子树作为模式,并用树型模式来描述它。在此基础上,把XML数据模式变化检测问题转化为约束满足求解问题,不仅针对该问题提出了一种较高效的求解算法,而且克服了一般方法要求在有序树上进行的限制。2.提出了一种基于权值加密的隐私安全分布式约束满足问题的求解算法。针对分布式约束满足问题中的隐私安全保护,从求解效率角度考虑,提出了一种基于权值加密的隐私安全分布式约束满足问题的求解算法。该算法通过对Agent内和Agent间不同的约束关系进行隐私安全性分析,在加密求解过程中使用不同的处理方式来获得更高的求解效率,利用Agent自身的计算和交互特点,不再引入额外的控制器来参与求解,真正实现分布式的安全策略,进一步减少了可能的信息泄漏,因而可以在确保隐私安全的前提下引入更好的启发式搜索策略。3.提出一种基于隐私安全分布式约束满足求解的多Agent虚拟企业合作伙伴选择协商模型。以基于多Agent的虚拟企业中各候选企业的隐私安全为出发点,提出一种利用隐私安全分布式约束满足求解的多Agent虚拟企业合作伙伴选择协商模型。在该模型中,将市场各部分需求或服务建模为Agent,将需求或服务之间的关系建模为各个Agent内部或Agent之间的约束,Agent之间通过隐私安全分布式约束满足求解方法来实现彼此间隐私安全的协商,进而完成满足需求的合作伙伴选择任务。分布式问题求解的应用将依赖于分布式约束满足问题中的求解效率、隐私安全等关键问题的有效解决,因而这些问题的研究具有重要的理论意义和应用价值。本文针对其中的一些问题展开了研究和探讨,如何进一步研究适应分布性从而减少通信需求和开销的分布式约束满足方法;如何平衡隐私安全性和算法效率,在两者间取得最佳折衷等,将为分布式约束满足更好地推向实际应用奠定基础,这也是本文今后工作的期望和目标。