SAT问题的随机算法的转移矩阵模型

来源 :中国科学技术大学 | 被引量 : 0次 | 上传用户:mrlee
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  本文对SAT问题的随机局部搜索算法的执行轨迹进行Markov建模,并推导出算法的转移矩阵模型,分析随机局部搜索算法的通用框架,及三种算法变种:GSAT、RandomWalk、WalkSAT在选取子句和翻转原子上的不同策略;选用Markov建模方法来建立我们的转移矩阵的理论模型;通过概率方法抽象和定义,给出RandomWalk算法的基本转移矩阵模型。然后进一步推导出其他策略上的转移概率模型,包括GSAT、GCWSAT、WalkSAT等策略;对搜索空间的某些属性进行实验统计分析,得出其概率分布,并代入上述模型中,得到模型上的转移矩阵概率;通过大量随机SAT实例上的实验统计,得到实例规模上的转移矩阵概率。通过和上述理论模型上概率之间的比较,实验结果进一步验证我们的转移矩阵模型的正确性。  
其他文献
  本文的工作基于Intel的开放式运行平台(OpenRuntimePlatform,简称ORP)。提出了对类型化低级语言语言(TypedLow-levelLanguage,简称TLL)的扩展,将利用类型信息所带来的类型安
当前,我国食品出口遇到诸多问题,食品生产、加工、出口企业遭受重大损失。在我国出口中,国外技术性贸易壁垒是对食品出口造成影响最为突出的问题,针对食品出口贸易面临的问题,国家
在传统IP网络中,QoS路由算法面临的问题有:对两个以上相互独立的参数提出要求时,容易导致NP-完全问题;现有的QoS路由算法往往只是针对某些特定类型的网络应用;IP网络不能同时承载
  本文从集合论角度讨论了课表问题,指出任何课表,都是集合论角度的“七值模型”,并以此为基础提出了初步的模型化教学管理思想。同时结合教学管理实际,采用Client/Server和Bro
生物特征识别作为一种新兴的身份鉴别技术,近年来得到了蓬勃的发展。掌纹作为一种生物特征,具有数据量大、通用性强的优点,在各个领域均有广泛的应用前景。本文面向刑侦领域的应
本文的研究背景是基于虚拟现实的虚拟养鱼系统,主要讨论了一个虚拟现实系统的研究、开发以及虚拟系统的实现。本文首先介绍了虚拟现实的发展现状、用于支持实时三维动画的计
本论文对基于嵌入式操作系统的嵌入式设备应用开发方式进行了深入的研究,重点研究了嵌入式设备的硬件驱动开发。 本文分三个阶段来阐述如何基于嵌入式操作系统来开发嵌入式
  本论文针对航天发射场信息安全问题进行了专题研究,目的是研究分析发射场信息安全风险和安全现状,建立发射场信息安全体系,提出符合实际、切实可行的信息安全问题解决方案,并
随着计算机技术的迅速发展和芯片制造工艺的不断进步,嵌入式操作系统(EOS-Embedded Operating Systems)的研究和应用日益广泛。从事EOS开发的厂商有上百家,成熟的产品有数百种
网络学习服务支持系统(Network-Learning Support System)是网络教育系统工程的一个重要组成部分,它把各具职能的学习支持服务功能移植到网络环境中,通过学习支持服务的知识