%0 Journal Article
%T 概率最大受限路径相容算法
%A 李宏博？
%A 梁艳春？
%A 李占山？
%J 软件学报
%P 3140-3150
%D 2015
%R 10.13328/j.cnki.jos.004815
%X 研究了可用于求解约束满足问题的最大受限路径相容算法(maxrpc).maxrpc算法执行过程中有大量无效的寻找路径相容证明(pc-witness)的操作,有效地识别和避免这些无效的寻找pc-witness的操作,可以提高maxrpc算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在pc-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(pmaxrpc),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:pmaxrpc可以避免一部分无效的寻找pc-witness的操作,在求解约束满足问题时,pmaxrpc效率高于maxrpc.在某些测试用例上,pmaxrpc比maxrpc和最流行的弧相容算法效率更高.
%K 约束满足问题
%K 局部相容
%K 最大受限路径相容
%K 概率最大受限路径相容
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=4815&flag=1