The effect of nogood learning in distributed constraint satisfaction
The effect of nogood learning in distributed constraint satisfaction
复制标题
分布式约束满足中不良学习的影响
DOI：
10.1109/icdcs.2000.840919
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
K. Hirayama
中科院分区：
文献类型：
--
作者：
M. Yokoo;K. Hirayama
我们提出了基于分解的学习作为一个新的分布式约束满足算法的nogood学习方法。该方法基于约束满足算法中的回看技术，可以有效地产生有效的无用信息。我们联合收割机异步弱承诺搜索算法（AWC）的方法和分布式3-着色问题和分布式3SAT问题的结果算法的性能进行评估。因此，我们发现，基于分解的学习效果很好，与以前的学习方法相比，分布式约束满足算法。我们还发现，AWC与基于解析式的学习能够找到一个解决方案，比分布式突破算法，这是已知的最有效的算法（在周期方面）解决分布式约束满足问题的周期更少。
We present resolvent-based learning as a new nogood learning method for a distributed constraint satisfaction algorithm. This method is based on a look-back technique in constraint satisfaction algorithms and can efficiently make effective nogoods. We combine the method with the asynchronous weak-commitment search algorithm (AWC) and evaluate the performance of the resultant algorithm on distributed 3-coloring problems and distributed 3SAT problems. As a result, we found that the resolvent-based learning works well compared to previous learning methods for distributed constraint satisfaction algorithms. We also found that the AWC with the resolvent-based learning is able to find a solution with fewer cycles than the distributed breakout algorithm, which was known to be the most efficient algorithm (in terms of cycles) for solving distributed constraint satisfaction problems.