|
|
题目：
雅宝题库答案：
****此区域为收费内容**** 需支付 1 知识币后可查看，1币=0.01元查看答案
雅宝题库解析：
以大规模随机约束满足题目为代表的~$NP$~完全题目的复杂性研究是理论计算机科学、统计物理和数学领域所关注的核心基础题目，它与新千年的世界七大数学难题之一密切相关.对于这一题目的科学研究不仅可以从理论上探索计算复杂性形成的根本原因，而且可以从数学和物理的学科交叉观点解释相变现象的本质内涵.indent 本文主要对约束满足题目中的两个经典题目~(即随机~MAX$k$-SAT~和随机~$(2+p)$-SAT)~的边界进行研究，全文内容由五章组成.indent 第一章为引言，主要介绍约束满足题目的一些研究现状以及随机~MAX$k$-SAT~的研究进展，同时给出了本文所需的一些基本概念和符号.indent 第二章从一阶矩方法的角度研究了随机~MAX$k$-SAT~的上界~(即最大可满足子句个数均值~$f_k(n,alpha n)$~的上界).通过对放缩精度的提高，得到了比~D.Coppersmith~等人~cite{CGHS}~给出的上界更优的结论，将随机~MAX$2$-SAT~的子句密度临界点由~4.1589~cite{CGHS}~改进为~2.4094.indent 第三章从局部最大可满足赋值的角度研究了随机~MAX$k$-SAT~的上界. D.Achlioptas~等人~cite{AKKK}~通过~cite{KKKS}~的研究技巧来计算随机~$(2+p)$-SAT~中局部最大可满足赋值的平均个数.本章应用该方法对随机~MAX $2$-SAT~和随机~MAX$3$-SAT~中的局部最大可满足赋值个数进行统计，通过数值模拟得到了比用修正一阶矩方法给出的上界更优的结论，扩大了子句密度的有效范围.indent第四章从赋值空间几何理论~cite{MS,MMW}~的角度出发，对随机~MAX$k$-SAT~的有效局部赋值权重进行研究. 通过对随机~MAX$2$-SAT~和随机~MAX$3$-SAT~中有效局部赋值权重的计算得到了可满足子式存在的概率上界，进而应用数值模拟给出了~$f_2(n,alphan)$~和~$f_3(n,alpha n)$~的最新上界.indent 由于赋值空间权重计算的方法作用在随机~MAX$2$-SAT~上时，得到的~$f_2(n,alphan)$~的上界优于用统计局部最大可满足赋值的方法得到的~$f_2(n,alphan)$~的上界，而作用在随机~MAX $3$-SAT~上时，得到的结果却相反.第五章通过对随机~$(2+p)$-SAT~的阈值进行研究，找到了使两种方法有效性发生改变的临界点，这为研究此类题目不同实例的最优方法选择提供了依据. |
上一篇：论城市应急管理中存在的题目及对策下一篇：光学稀疏孔径系统的像质分析
|
发表于 2022-8-29 11:56:36
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
中发现Ni：
QQ登录
