Networks of constraints are a simple knowledge representation method, useful for describing those problems whose solution is required to satisfy several simultaneous constraints. The problem of solving a network of constraints with finite domains is NP-complete. The standard solution technique for such networks of constraints is the backtrack search, but many relaxation algorithms, to be applied before backtracking, have been developed: they transform a network in an equivalent but more explicit one. The idea is to make the backtrack search have a better average time complexity. In fact, if the network elaborated by the backtrack algorithm is more explicit, the algorithm backtracks less. In this paper we describe relaxation algorithms as sequences of applications of relaxation rules. Moreover, we define perfect relaxation algorithms as relaxation algorithms which not only return a more explicit network, but also exactly solve the given network of constraints by applying every relaxation rule only once. Finally, we characterize a family of classes of networks on which certain perfect relaxation algorithms are very efficient: the exact solution of each network in a class is found in linear time.

CONSTRAINT RELAXATION MAY BE PERFECT

MONTANARI, UGO GIOVANNI ERASMO;
1991

Abstract

Networks of constraints are a simple knowledge representation method, useful for describing those problems whose solution is required to satisfy several simultaneous constraints. The problem of solving a network of constraints with finite domains is NP-complete. The standard solution technique for such networks of constraints is the backtrack search, but many relaxation algorithms, to be applied before backtracking, have been developed: they transform a network in an equivalent but more explicit one. The idea is to make the backtrack search have a better average time complexity. In fact, if the network elaborated by the backtrack algorithm is more explicit, the algorithm backtracks less. In this paper we describe relaxation algorithms as sequences of applications of relaxation rules. Moreover, we define perfect relaxation algorithms as relaxation algorithms which not only return a more explicit network, but also exactly solve the given network of constraints by applying every relaxation rule only once. Finally, we characterize a family of classes of networks on which certain perfect relaxation algorithms are very efficient: the exact solution of each network in a class is found in linear time.
Montanari, UGO GIOVANNI ERASMO; Rossi, F.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/19811
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 44
social impact