constraint satisfaction problem

Angol

Főnév

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.

---

🧠 1. Formális definíció

Egy CSP három elemből áll:

• Változók halmaza:

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

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

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

• Korlátozások halmaza:

  $$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.

Cél:

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

---

🔢 2. Példa – Sudoku mint CSP

• 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ő

---

🧩 3. CSP típusai

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)

---

🛠️ 4. Megoldási módszerek

✅ 4.1 Backtracking (visszalépéses keresés)

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

✅ 4.2 Forward Checking

• 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

✅ 4.3 Constraint Propagation (korlátozás-terjesztés)

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

✅ 4.4 Local search (pl. min-conflicts)

• 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

---

⚙️ 5. Heurisztikák a kereséshez

Heurisztika	Jelentés
MRV (Minimum Remaining Values)	Válaszd azt a változót, aminek legkevesebb lehetősége van
Degree heuristic	Válaszd azt, amelyik a legtöbb másikat korlátozza
Least Constraining Value	Válaszd azt az értéket, amelyik a legkevesebb más tartományát csökkenti

---

📈 6. Példák CSP-kre

Probléma	Leírás
Sudoku	9×9-es rács, AllDifferent korlátozások
N Queens	Királynők ne üssék egymást → sor/átló korlátozások
Térképszínezés	Szomszédos országok nem lehetnek azonos színűek
Ütemezés	Feladatok ne fedjék egymást, előfeltételek stb.
Konfiguráció	Hardver/termékkomponensek kompatibilitása

---

🧪 7. Python példa (using python-constraint)

from constraint import *

problem = Problem()

# Változók és tartományok
problem.addVariables(["A", "B", "C"], [1, 2, 3])

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

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

---

📉 8. Bonyolultság

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)

---

📌 9. Összefoglalás

Fogalom	Leírás
CSP	Változók + tartományok + korlátozások
Cél	Minden változónak értéket adni úgy, hogy minden korlátozás teljesüljön
Megoldás típusa	Egy vagy több kielégítő értékadás
Algoritmusok	Backtracking, propagáció, heurisztikák, lokális keresés
Használat	AI, ütemezés, játékok, konfigurációk, logikai modellezés

További információk

• 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)