constraint satisfaction problem

constraint satisfaction problem (tsz. constraint satisfaction problems)

1. (informatika) A Constraint Satisfaction Problem (röviden: CSP, magyarul: korlátozásos kielégítési probléma) egy formális modell, amelyben egy halmaz változóra keresünk olyan értékeket, amelyek kielégítenek adott korlátozásokat. A CSP-k a mesterséges intelligencia, logikai következtetés, ütemezés, konfigurációs problémák, játékmegoldás és optimalizálás területén gyakran előfordulnak.

Egy CSP három elemből áll:

• Változók halmaza:

  $${\displaystyle X=\{X_{1},X_{2},...,X_{n}\}}$$

• Tartományok (domain) minden változóhoz:

  $${\displaystyle D_{i}={\text{lehetséges értékek }}X_{i}{\text{-hez}}}$$

• Korlátozások halmaza:

  $${\displaystyle C=\{C_{1},C_{2},...,C_{m}\}}$$

  ahol minden korlátozás meghatároz egy relációt a változók egy részhalmazára.

Olyan értékeket rendelni minden ${\textstyle X_{i}}$-hez, amelyek mindegyik korlátozást kielégítik.

• Változók: a rács 81 mezője
• Tartomány: ${\textstyle D_{i}=\{1..9\}}$
• Korlátozások:
  • Soronként minden szám különböző
  • Oszloponként minden szám különböző
  • 3×3 blokkonként minden szám különböző

Típus	Példa
Bináris	Két változót összekötő korlátozások (pl. ${\textstyle X\neq Y}$)
Nem-bináris	Több változóra vonatkozó (pl. AllDifferent)
Szigorúan meghatározott	Minden változónak pontosan egy értéket kell kapnia
Kemény korlátozások	Meg kell felelni nekik (pl. Sudoku szabály)
Lágy korlátozások	Lehet megsérteni, de ára van (pl. preferenciák)

• Kipróbál egy értéket, ha nem jó: visszalép
• Bővíthető heurisztikákkal és propagációval

• Miután egy változónak értéket adtunk, eltávolítja az összeütköző értékeket a szomszédos változók tartományaiból

• Pl. Arc Consistency (AC-3): minden él mentén a változók tartományai konzisztenssé válnak

• Egy teljes (de hibás) értékadásból indul, és helyben javít
• Gyors, de nem garantált, hogy megtalálja a megoldást

from constraint import *

problem = Problem()

# Változók és tartományok
problem.addVariables(, )

# Korlátozások
problem.addConstraint(AllDifferentConstraint())
problem.addConstraint(lambda a, b: abs(a - b) > 1, ("A", "B"))

# Megoldás
solutions = problem.getSolutions()
print(solutions)

A CSP megoldása NP-teljes általános esetben. Viszont:

• Ha korlátok binárisak és a változók gráfja fa → lineáris időben megoldható
• Globális korlátozások hatékonyan feldolgozhatók (pl. AllDifferent)

• constraint satisfaction problem - Szótár.net (en-hu)
• constraint satisfaction problem - Sztaki (en-hu)
• constraint satisfaction problem - Merriam–Webster
• constraint satisfaction problem - Cambridge
• constraint satisfaction problem - WordNet
• constraint satisfaction problem - Яндекс (en-ru)
• constraint satisfaction problem - Google (en-hu)
• constraint satisfaction problem - Wikidata
• constraint satisfaction problem - Wikipédia (angol)