改进Max-SAT算法的关键技术研究

项目名称： 改进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