Tipos de CSPs con coste

Tutorial on Soft Constraints

A more general way of explaining over-constrained problems
has been proposed by Stefano Bistarelli. He calls this framework as the Semiring-based
Constraint Satisfaction problem.

OTHER SOFT CSP FRAMEWORKS

Bistarelli showed that some of the previous constraint satisfaction approaches can be seen as instances of this theory differing only in the choice of the semiring.

Classical:
Constraints in a classical CSP can be modeled with a semi-ring
containing only 1 and 0 in A. Also constraint combination can be modeled with
logical and the projection over some of the variables with logical or. Thus a
CSP can be seen as a SCSP with the following semiring

S (CSP) = ({0,
1}, ⋁,
⋀, 0, 1)

Fuzzy CSP:
Fuzzy CSP’s allow for associating a preference level with each tuple of values.
This level of preference lies between 0 and 1. The solution of a fuzzy CSP is
defined as a set of tuples of values for all the variables which have a maximal
value. Fuzzy CSP’s can be modeled in the SCSP framework by choosing the
following semiring.

S (FCSP) = ({x/x ∈ [0, 1]}, max,
min, 0, 1)

Probablistic CSP:
In Probabilistic CSP’s each constraint c has an associated probability p(c). c
has probability p means that the situation corresponding to c has probability p
of occurring in the real-life problem. The semi-ring corresponding to the
probabilistic CSP is as follows.

S (prob) = ({x/x ∈ [0, 1]}, max,
X, 0,1)

Weighted CSP: While Fuzzy CSPs’ come with preferences, Constraints are associated with
costs in weighted CSP’s. The solution to a problem in such models is the one
with minimum cost. The associated semiring for a weighted CSP is

S (WSCP) = (R^*, min,
+, ∞, 0)