【摘 要】
：
约束满足问题(ConstraintSatisfactionProblem,简称CSP)简而言之就是由一组变量和一组约束组成的约束关系,求解约束满足问题就要为变量找到一组赋值而并不违反任何一个约束。
论文部分内容阅读
约束满足问题(ConstraintSatisfactionProblem,简称CSP)简而言之就是由一组变量和一组约束组成的约束关系,求解约束满足问题就要为变量找到一组赋值而并不违反任何一个约束。目前研究约束满足问题有两个方向,一方面研究高效的求解算法;另一方面研究随机CSP模型,如何利用随机模型生成更难解的约束满足问题。生成难解随机约束满足问题不仅能够为设计更为高效的求解算法提供更好的测试样例(Benchmark),而且能够对难解实例的内部结构和缺陷加以了解,为研究算法和实际应用提供借鉴意义和基础。 RB模型是一种值域可变的随机约束满足问题的模型,基于RB模型生成的难解实例被广泛应用于算法竞赛和理论研究。文献[1]中,作者证明了RB模型的相变现象,并且给出了相变点。 本文在RB模型的基础上研究一种新模型,即平衡RB模型。平衡RB模型是保证每个变量均匀分布在约束上,即在约束图中每个顶点的度均匀分布(正则图)。这种新模型不但能够生成难解实例,而且存在相变现象,本文在理论上证明了平衡RB模型存在相变现象,并计算出了精确的相变点。通过实验验证了平衡RB模型的难解性和相变现象。
其他文献
随着普适计算的发展,上下文感知作为普适计算的核心部分,越来越得到大家的关注。上下文感知研究的是如何获取上下文、上下文的表示、以及上下文的推理等,其目的是为了利用上
数字图像处理系统在大图像处理性能与数据展示效果方面具有一定的缺陷,综合考虑系统本身的GIS背景以及GIS技术面向海量数据的特性,本文拟通过引入GIS技术来弥补这些缺陷。经
随着手写文字识别技术的快速发展,阿拉伯语文字分类已日益引起研究者的关注。有两种阿拉伯语文字识别系统:联机和脱机文字识别。对于联机文字识别系统,需要使用特殊的数字化
随着Web2.0的兴起,软件开发正在转变传统的服务观念,个性化业务大量涌现。然而移动性差、硬件成本高、资源扩展性差等问题制约了第三方业务开发的发展。而云计算恰恰在实现服
随着Internet的流行和发展，人们对于Internet的依赖也越来越强，对Web应用也有了更多的需求。传统Web应用的客户端主要是用来渲染服务端返回的HTML页面，功能单一，难以满足用户的交
互联网的蓬勃发展使距离不再成为人们认识彼此、交流信息的障碍，基于地域、爱好和理想等多种元素交汇的网络社区逐渐成为人们更加方便地获取信息的手段。虚拟的网络社区延续并
随着互联网技术的迅速发展和普及,尤其是社交网站和图像共享网站的不断推广和应用,网络上的图像数量呈现快速增长趋势。如何快速、准确地从海量的图像数据中检索到用户所需要
在计算环境从静态、封闭、可控逐步走向动态、开放、难控的过程中,软件呈现出一种新的形态——网构软件。网构软件的开放性给其服务质量的保障带来深层次的技术挑战。首先,网
粒计算是研究如何在问题求解过程中使用人类“粒度”和“粒”的思想的一门新兴学科，致力于探索基于粒度的理论、技术和工具，在过去十年中，它得到了很多研究者的关注。粒计算三元
随着移动技术的发展,智能手机等移动设备在日常生活中起到越来越重要的作用,但受限的资源始终制约着智能手机的计算能力。为了扩展移动设备的计算能力,弹性计算的概念被应用