ImageVerifierCode 换一换
格式:PPT , 页数:20 ,大小:423KB ,
资源ID:353845      下载积分:120 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-353845.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(浅谈3-sat问题的判定.ppt)为本站会员(ga****84)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

浅谈3-sat问题的判定.ppt

1、浅谈3-SAT问题,陈昕昀,SAT问题的定义,k-SAT,3-SAT,完备性算法非完备性算法一些拓展,完备性算法,根本思想:回溯法优化: (1)优先确定短的子句中包含的变量的值 (2)优先确定在较多子句中出现的变量的值,问题模型的转化,问题模型的转化,将X中所有变量的一个赋值方案记为 a=a1,a2,an令则原问题转化为判断上述函数最小值 能否达到0,非完备性算法,爬山法模拟退火遗传算法 ,粒子群优化算法,J.Kennedy,R. C. Eberhart(1995)第i个粒子的状态用三元组(ai,vi,pi)表示 ai:当前解 vi:粒子运动速度 pi:该粒子达到过的最优解,应用于3-SAT问

2、题,记ai=(xi1, xi2, xin) vi=(vi1,vi2, vin)(ai,vi,pi)的更新方式如下: 当sig(vij(t+1)r3时,xij(t+1)=0,反之为1 其中t为迭代次数,sig(x)=1/(1+e-x) (0,1),为惯性因子;c1,c2为事先确定的正常数 pg表示整个粒子群所达到过的最优解 r1,r2,r3为相互独立的(0,1)之间的随机数,单纯用这种方法求解容易使f(pg)停留在某个很小的正整数而无法得到0这个解有可能在最优解的附近记当前所得f(pg)=c;若最优解存在的话,至多需要改变 3c个变量的值将其余变量的值固定,对这几个变量使用局部随机搜索若仍无法达

3、到最优解,则认为当前解为局部极小值,更新其余解,应用于3-SAT问题,伪代码,maxTimes=200, vmax=2;size=100,c1=c2=2.0,w=0.8,i=1,currentTimes=0;initialize population;while ivmax)vij=vmax; get r3; if sig(vij)=maxTimes then while 1 do c=f(pg); c2=local_search(pg); if c2=0 then return pg; if c2=c then update pg else i=i+1,currentTimes=0,brea

4、k; end while end thenend while return (pg,f(pg);,一些拓展,转化为独立集问题对Xi中每个元素建立一个节点对应于相应变量 的取值,并两两之间相互连边假如Xi与Xj中同时存在xk和 xk,将对应的两个 点连边3-SAT问题有解当且仅当该图中存在点数为m 的独立集,一些拓展,转化为独立集问题举个例子:,一些拓展,一个8/7-近似算法假设在一个3-SAT问题中每个语句恰好包含3个 子句,如果我们只要求满足大部分语句的话,存在 一个确定性算法能够满足7/8的语句首先,考虑在一随机指派下满足语句个数的期望 值,记为E(X),每个语句记为Xi则P(Xi=1)=

5、7/8,P(Xi=0)=1/8,E(Xi)=7/8(1im)故 E(X)=7m/8因此,基于随机指派的算法的期望近似比m/(7m/8)=8/7,一些拓展,一个8/7-近似算法首先考虑变量x1由于E(X)=E(X|x1=1)P(x1=1)+E(X|x1=0)P(x1=0) =0.5E(X|x1=1) +0.5E(X|x1=0)故必存在对于x1的某个赋值a1(a10,1)使得 E(X|x1=a1)7m/8同理,可依次找到a2, a3 ,an0,1使得 E(X| x1=a1, xn=an)7m/8,则该方案即为所求该确定性算法的近似比m/(7m/8)=8/7,时间复 杂度为O(nm),结 语,References,Carla P. Gomes, Henry Kautz, Ashish Sabharwal, Bart Selman,“Satisfiability solvers”He Yichao,Wang Yanqi,Kou Yingzhan, “A New Method for Solving 3-SAT Problems”Riccardo Poli, James Kennedy, Tim Blackwell, “Particle swarm optimization”,Thanks for Listening!,

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。