版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Dep. Comp. Sci. and Eng. Univ. California at San Diego La Jolla CA 92093 USA
出 版 物:《INFORMATION PROCESSING LETTERS》 (信息处理快报)
年 卷 期:1992年第43卷第1期
页 面:53-55页
核心收录:
学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
主 题:ANALYSIS OF ALGORITHMS SATISFIABILITY GREEDY ALGORITHM PROBABILISTIC ANALYSIS
摘 要:We show that for the vast majority of satisfiable 3CNF formulae, the local search heuristic that starts at a random truth assignment and repeatedly flips the variable that improves the number of satisfied clauses the most, almost always succeeds in discovering a satisfying truth assignment.