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

在d-k-CSP模型的基础上,给出了产生可满足性难解实例的两种方法。利用概率论分析了d-k-CSP模型在这两种方法下解的平均个数和解的分布情况,并用数值实验对两种方法产生的可满足性实例的求解难度进行了对比分析。结果表明:强迫有解实例和非强迫有解实例的求解难度相当,但产生强迫有解实例的方法更简单有效。