בעיית סיפוק אילוצים

בעיות סיפוק אילוצים הן בעיות של השמת ערכים למשתנים כך שיש אילוצים מסוימים בין ערכים של משתנים מסוימים.

הגדרות

משתנים - אחד או יותר משתנים. מרחב המצבים - כלל ההשמות האפשריות למשתנים. דומיין - דומיין של משתנה הוא הערכים האפשריים למשתנה זה. אילוצים - פונקציות שהערכים של המשתנים צריכים לקיים. כל פונקציה יכולה להכיל ערך אחד או יותר.

דוגמאות

חידת שמונה המלכות

ניתן להציג את חידת שמונה המלכות כבעיית סיפוק אילוצים בו יש שמונה משתנים, הדומיין הוא הצבה של כל הקומבינציות האפשריות של השמה של כלל מקומות הלוח לכל אחד מהמשתנים, ועבור כל זוג משתנים יש אילוץ שהם לא באותה שורה/טור/אלכסון.

מדוגמה זו ניתן לראות את חשיבותו של בחירת הדומיין, אם ייבחר הדומיין של כל הקומבינציות האפשריות כאשר לכל משתנה i מותר להיות רק על השורה מספר i אזי גודל הדומיין יקטן משמעותית וכן מספר הערכים האפשריים לכל משתנה.

אלגוריתמים

על מנת למצוא השמה מספקת יש צורך להפעיל אלגוריתם חיפוש שינסה השמות על המשתנים עד שיימצא פתרון, מאחר שידוע כמות ההשמות שצריך לבצע (ככמות המשתנים) אין יתרון לאלגוריתם חיפוש לרוחב שנועד על מנת למצוא פתרון עם כמה שפחות צעדים, ועל כן משתמשים באלגוריתם חיפוש לעומק שהוא מהיר יותר או באלגוריתם חיפוש מקומי.

AC-3

אלגוריתם AC-3 הוא אלגוריתם שנועד לצמצם את כמות הערכים האפשריים לכל משתנה על סמך הערכים שהושמו עד כה. האלגוריתם בודק עבור כל ערך של משתנה A האם עבור כל אחד מהמשתנים האחרים קיים ערך אפשרי כך שהאילוץ בין שני המשתנים לא מופר, אם קיים משתנה לו אין ערך כזה ניתן להסיר את הערך מהמשתנה A.

אלגוריתם גישוש נסוג

ערך מורחב – גישוש נסוג

אלגוריתם זה הוא אלגוריתם מבוסס חיפוש לעומק לפתרון בעיות סיפוק אילוצים. האלגוריתם בכל רמה מבצע השמה למשתנה אחר. ההיוריסטיקה לבחירת סדר המשתנים היא המשתנה בעל מספר הערכים הנמוך יותר, כדי להקטין את העץ כמה שיותר, שבירת שוויון מתבצעת על ידי בחירת המשתנה עם מספר האילוצים הרב ביותר, כדי שכמה שיותר מהר נמצא סתירות. ההיוריסטיקה לסדר השמת הערכים הערכים היא הערך שמאפשר כמה שיותר ערכים לשאר המשתנים בפעם הבאה, כדי לאפשר הכי הרבה סיכוי למצוא פתרון מוקדם. כמו כן בכל שלב מריצים את AC-3.