项目名称: 改进Max-SAT算法的关键技术研究

项目编号: No.60903054

项目类型: 青年科学基金项目

立项/批准年度: 2010

项目学科: 生物科学

项目作者: 林瀚

作者单位: 中山大学

项目金额: 18万元

中文摘要: SAT问题是理论计算机科学和人工智能领域中的基本问题. Max-SAT问题是SAT问题的一个很自然的扩展. 统计物理、生物信息学等领域中的许多问题都可以转化为Max-SAT问题. 近五年,Max-SAT求解的研究吸引了越来越多学者的关注. 每年举行的国际Max-SAT求解评比见证和推动了这一领域研究的发展. 申请人在2007年提出了分支定界算法中新的下界计算方法,基于这一方法的Max-SAT求解器Inc(W)Maxsatz在2008年的Max-SAT评比中表现优异. 在已有工作的基础上,本项目将研究如何将SAT求解中采用的two watched literals和clause learning技术结合进Max-SAT中求解中,研究将Max-SAT实例转化为SAT实例之后公式所具有的结构特性,研究适用于Max-SAT的局部搜索算法,以求进一步改进当前Max-SAT求解器的效率.

中文关键词: Max-SAT;分支定界;下界;最长公共子序列;NP难问题

英文摘要:

英文关键词: Max-SAT;branch and bound;lower bound;longest common subsequence;NP-hard problems

成为VIP会员查看完整内容
0

相关内容

基于深度学习的图像目标检测算法综述
专知会员服务
92+阅读 · 2022年4月15日
【博士论文】大数据相似查询关键技术研究
专知会员服务
23+阅读 · 2021年12月2日
专知会员服务
20+阅读 · 2021年9月23日
专知会员服务
37+阅读 · 2021年8月20日
专知会员服务
209+阅读 · 2021年8月2日
专知会员服务
30+阅读 · 2021年6月24日
专知会员服务
41+阅读 · 2020年7月29日
性能再升级,苹果新一代自研芯片 M2 要来了!
ZEALER订阅号
0+阅读 · 2022年3月7日
苹果 Mac Studio 新品曝光,将搭载 M1 Max 或更强芯片
ZEALER订阅号
0+阅读 · 2022年3月5日
深度学习技术在自动驾驶中的应用
智能交通技术
25+阅读 · 2019年10月27日
兴军亮Science评述:多人德州扑克博弈新突破
中国科学院自动化研究所
19+阅读 · 2019年7月15日
贝叶斯机器学习前沿进展
架构文摘
12+阅读 · 2018年2月11日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2022年4月19日
Max-Margin Contrastive Learning
Arxiv
17+阅读 · 2021年12月21日
Arxiv
26+阅读 · 2018年9月21日
小贴士
相关VIP内容
基于深度学习的图像目标检测算法综述
专知会员服务
92+阅读 · 2022年4月15日
【博士论文】大数据相似查询关键技术研究
专知会员服务
23+阅读 · 2021年12月2日
专知会员服务
20+阅读 · 2021年9月23日
专知会员服务
37+阅读 · 2021年8月20日
专知会员服务
209+阅读 · 2021年8月2日
专知会员服务
30+阅读 · 2021年6月24日
专知会员服务
41+阅读 · 2020年7月29日
相关资讯
性能再升级,苹果新一代自研芯片 M2 要来了!
ZEALER订阅号
0+阅读 · 2022年3月7日
苹果 Mac Studio 新品曝光,将搭载 M1 Max 或更强芯片
ZEALER订阅号
0+阅读 · 2022年3月5日
深度学习技术在自动驾驶中的应用
智能交通技术
25+阅读 · 2019年10月27日
兴军亮Science评述:多人德州扑克博弈新突破
中国科学院自动化研究所
19+阅读 · 2019年7月15日
贝叶斯机器学习前沿进展
架构文摘
12+阅读 · 2018年2月11日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
微信扫码咨询专知VIP会员