• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Asynchronous Forward-checking for DisCSPs
【24h】

Asynchronous Forward-checking for DisCSPs

机译：DisCSP的异步转发检查

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A new search algorithm for solving distributed constraint satisfaction problems (DisCSPs) is presented. Agents assign variables sequentially, but perform forward checking asynchronously. The asynchronous forward-checking algorithm (AFC) is a distributed search algorithm that keeps one consistent partial assignment at all times. Forward checking is performed by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and its correctness proven. The sequential assignment method of AFC leads naturally to dynamic ordering of agents during search. Several ordering heuristics are presented. The three best heuristics are evaluated and shown to improve the performance of AFC with static order by a large factor. An experimental comparison of AFC to asynchronous backtracking (ABT) on randomly generated DisCSPs is also presented. AFC with ordering heuristics outperforms ABT by a large factor on the harder instances of random DisCSPs. These results hold for two measures of performance: number of non-concurrent constraints checks and number of messages sent.
机译：提出了一种新的求解分布式约束满足问题的搜索算法。代理顺序分配变量，但异步执行前向检查。异步前向检查算法（AFC）是一种分布式搜索算法，该算法始终保持一个一致的部分分配。通过将部分分配的副本同时发送到所有未分配的代理来执行前向检查。详细描述了该算法，并证明了其正确性。 AFC的顺序分配方法自然会导致在搜索过程中对代理进行动态排序。介绍了几种排序试探法。对三种最佳启发式方法进行了评估，并显示它们在很大程度上改善了静态顺序AFC的性能。还介绍了AFC与随机生成的DisCSP上的异步回溯（ABT）的实验比较。具有顺序试探法的AFC在较难的随机DisCSP实例上比ABT大得多。这些结果适用于两种性能度量：非并发约束检查次数和发送的消息数。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号