Nogood-FC for solving partitionable constraint satisfaction problems |
| |
Authors: | Montserrat Abril Miguel A Salido Federico Barber |
| |
Affiliation: | 1. Department of Information Systems and Computation, Technical University of Valencia, Camino de Vera s/n, 46022, Valencia, Spain
|
| |
Abstract: | Many real problems can be naturally modelled as constraint satisfaction problems (CSPs). However, some of these problems are of a distributed nature, which requires problems of this kind to be modelled as distributed constraint satisfaction problems (DCSPs). In this work, we present a distributed model for solving CSPs. Our technique carries out a partition over the constraint network using a graph partitioning software; after partitioning, each sub-CSP is arranged into a DFS-tree CSP structure that is used as a hierarchy of communication by our distributed algorithm. We show that our distributed algorithm outperforms well-known centralized algorithms solving partitionable CSPs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|