constraint programming

Angol

Főnév

constraint programming (tsz. constraint programmings)

1. (informatika, mesterséges intelligencia) A Constraint Programming (korlátozásos programozás, CP) egy erőteljes paradigmája a deklaratív programozásnak, amelyet bonyolult kombinatorikus problémák (pl. ütemezés, erőforrás-kezelés, puzzle-feladatok, konfigurációk stb.) megoldására használnak. Ebben a megközelítésben megoldáskeresés nem algoritmikus lépésekkel, hanem feltételek (korlátozások) megadásával történik, amelyek meghatározzák, milyen tulajdonságokkal rendelkezhet egy érvényes megoldás.

---

🧩 1. Mi az a Constraint Programming?

A Constraint Programming egy problémamegoldó keretrendszer, ahol:

• Megadunk egy változókészletet.
• Mindegyik változónak van egy tartománya (domain) – lehetséges értékeinek halmaza.
• Különféle korlátozásokat (constraints) definiálunk a változók között.
• A cél: olyan érékadásokat találni a változókhoz, amelyek mindegyik korlátozást kielégítik.

Példa:

Sudoku – a rács minden mezője egy változó, tartományuk: {1,2,…,9}. Korlátozás: minden sorban/oszlopban/blokkban minden szám csak egyszer szerepelhet.

---

🛠️ 2. A CP modell elemei

2.1 Változók (Variables)

Legyenek ${\textstyle X_{1},X_{2},...,X_{n}}$ változók.

2.2 Tartomány (Domain)

Minden változónak van egy értéktartománya ${\textstyle D_{i}}$, azaz ${\textstyle X_{i}\in D_{i}}$.

Például:

• ${\textstyle D_{1}=\{1,2,3,4,5\}}$
• ${\textstyle D_{2}=\{a,b\}}$

2.3 Korlátozások (Constraints)

Formálisan: ${\textstyle C(X_{i},X_{j},...,X_{k})}$ reláció, amely a változók bizonyos kombinációit engedélyezi.

Példák:

• ${\textstyle X_{1}\neq X_{2}}$
• ${\textstyle X_{3}+X_{4}\leq 10}$
• ${\textstyle {\text{AllDifferent}}(X_{1},...,X_{n})}$

---

🧠 3. CP megoldási folyamat

A constraint programming rendszer a következő lépéseket alkalmazza:

3.1 Keresési tér

Minden lehetséges értékadás a változókhoz. A keresési tér exponenciálisan nagy, de a korlátozások ezt nagymértékben szűkítik.

3.2 Keresési algoritmus (search)

A leggyakoribb módszer a backtracking (visszalépéses keresés), amely:

1. Választ egy változót.
2. Kipróbálja a lehetséges értékeket.
3. Ha valamelyik megsérti a korlátozást, visszalép.

3.3 Korlátozás propagáció (constraint propagation)

Ez egy intelligens tartományszűkítési eljárás. A cél: a változók értéktartományát csökkenteni a korlátozások alapján.

Pl.:

• Ha ${\textstyle X+Y=5}$, és ${\textstyle X=2}$, akkor ${\textstyle Y\in \{3\}}$
• Ha egy AllDifferent korlátozásban csak egy érték maradt, más változók nem vehetik fel azt

3.4 Heurisztikák

Hatékony CP rendszerek változó- és érték-választási heurisztikákat alkalmaznak:

• Minimum Remaining Values (válaszd azt a változót, amelyiknek legkevesebb lehetséges értéke van)
• Most Constraining Variable (válaszd azt, amelyik a legtöbb korlátozásban szerepel)

---

📚 4. Típusos korlátozások

4.1 Bináris korlátozás

Két változó között (pl. ${\textstyle X\neq Y}$)

4.2 Globális korlátozás

Több változóra ható magas szintű korlátozás. Például:

• AllDifferent: minden változó különböző
• Cumulative: erőforrás-használat korlátozása idő szerint (pl. gépek, memória)
• Element: indexelés (pl. ${\textstyle X_{i}=V}$)

---

💡 5. CP alkalmazások

✅ Ütemezés (Scheduling)

• Iskolai órarendek
• Gyártósor optimalizálás
• Repülőgép-karbantartási időpontok

✅ Erőforrás-kezelés

• Munkafolyamat-elosztás gépek között
• Energiafogyasztás optimalizálása

✅ Konfigurációs problémák

• Hardver-összeszerelés
• Termékopciók érvényessége

✅ Puzzle-k

• Sudoku
• N-queens
• Kakuro

---

🧮 6. Példa: 4-Queens probléma

Feladat: Tegyünk le 4 királynőt 4×4-es táblára úgy, hogy ne üssék egymást!

Modell:

• Változók: ${\textstyle Q_{1},Q_{2},Q_{3},Q_{4}}$ (oszloponként egy királynő, érték: sor)
• Tartomány: ${\textstyle D_{i}=\{1,2,3,4\}}$
• Korlátozások:
  • ${\textstyle {\text{AllDifferent}}(Q_{1},Q_{2},Q_{3},Q_{4})}$ (nem lehetnek egy sorban)
  • ${\textstyle |Q_{i}-Q_{j}|\neq |i-j|}$ (nem lehetnek egy átlóban)

A CP megoldó keres a feltételeket kielégítő értékadásokat.

---

🧰 7. Constraint Programming rendszerek

Nyelvek / könyvtárak:

• MiniZinc – deklaratív nyelv CP modellezéshez
• Choco Solver – Java alapú CP könyvtár
• Google OR-Tools – támogatja CP-t, MIP-et, SAT-ot
• Gecode – C++ CP könyvtár
• ECLiPSe, SICStus Prolog – logikai programozási nyelvek CP támogatással

---

🧾 8. CP vs más módszerek

Paradigma	Leírás	Példa
Constraint Programming	Korlátozásokkal definiált megoldáskeresés	Sudoku, órarend
Matematikai programozás	Célfüggvény maximalizálása/minimalizálása	Lineáris programozás
SAT Solving	Boole-formulák kielégíthetősége	Hardververifikáció
Heurisztikus módszerek	Keresés, optimalizálás nem garantált	Genetikus algoritmusok

---

🔮 9. Jövő és kutatás

A CP folyamatosan fejlődik:

• Hibrid megoldások: CP + MIP/SAT kombinációk
• Tanuló keresés (learning during search)
• Magas szintű modellezőnyelvek
• Magyarázatok (explanations): miért nincs megoldás?

---

📌 Összefoglalás

A Constraint Programming:

• Deklaratív megközelítés, a “mit”, nem a “hogyan”-t írjuk le.
• Alapja: változók, tartományok, korlátozások.
• Használ: backtracking, propagation, heurisztikák.
• Nagyon rugalmas és általános kombinatorikus problémákra.
• Sokféle ipari és kutatási alkalmazás van rá.

További információk

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