一种产生可满足性难解实例的模型  

A model to generate hard satisfiable instances

作　　者：沈静[1] 任耀峰[1] 梅丹[1] 杨美妮[1] 

机构地区：[1]海军工程大学理学院,武汉430033

出　　处：《海军工程大学学报》2016年第3期5-8,共4页Journal of Naval University of Engineering

基　　金：国家自然科学基金资助项目(61402516;61370052);海军工程大学自然科学基金资助项目(HGDQNEQJJ13002)

摘　　要：在d-k-CSP模型的基础上,给出了产生可满足性难解实例的两种方法。利用概率论分析了d-k-CSP模型在这两种方法下解的平均个数和解的分布情况,并用数值实验对两种方法产生的可满足性实例的求解难度进行了对比分析。结果表明:强迫有解实例和非强迫有解实例的求解难度相当,但产生强迫有解实例的方法更简单有效。Based on the model d-k-CSP,two methods for generating hard satisfiable instances are proposed.The expected number of solutions and distribution of solutions with respect to the two methods under model d-k-CSP are analyzed by the probability theory,and a series of experimental studies are carried out to analyze the hardness of satisfiable instances generated by the two methods.The results show that the forced and unforced satisfiable instances have a similar hardness,but the method for the generating forced satisfiable instances is easier than that for generating unforced satisfiable instances.

关 键 词：约束满足问题 强迫有解实例 相变 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]