יחידה 4: בעיות סיפוק אילוצים (CSP)

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

מבוא לבעיות סיפוק אילוצים (CSP)

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

מודל בעיית סיפוק אילוצים (CSP)

כל בעיית CSP מוגדרת על ידי שלושה מרכיבים עיקריים:

• משתנים (Variables): קבוצה לא ריקה של משתנים, נסמן אותם ב-X₁, X₂, ..., X_n.
• תחומים (Domains): עבור כל משתנה X_i, קיים תחום D_i המכיל את כל הערכים האפשריים ש-X_i יכול לקבל.
• אילוצים (Constraints): קבוצה של אילוצים C₁, C₂, ..., C_m. כל אילוץ C_j מגדיר קבוצת משתנים (היקף האילוץ) וקבוצת צירופי ערכים חוקיים עבור משתנים אלו. אילוץ יכול להיות אונארי (על משתנה אחד), בינארי (על שני משתנים) או מסדר גבוה יותר.

אלגוריתם Backtracking (חיפוש עם נסיגה)

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

כיצד Backtracking עובד:

1. בוחר משתנה שטרם הוקצה לו ערך.
2. בוחר ערך מתוך התחום של המשתנה.
3. בודק אם הקצאה זו עקבית עם האילוצים הקיימים (כלומר, האם היא אינה מפרה אף אילוץ בינארי או אונארי עם משתנים שכבר הוקצו להם ערכים).
4. אם ההקצאה עקבית: מקצה את הערך למשתנה וממשיך באופן רקורסיבי למשתנה הבא.
5. אם ההקצאה אינה עקבית (או אם החיפוש הרקורסיבי נכשל): מבטל את ההקצאה הנוכחית ובוחר ערך אחר עבור אותו משתנה. אם אין יותר ערכים לנסות עבור המשתנה הנוכחי, האלגוריתם "נסוג" (backtrack) למשתנה הקודם ובוחר עבורו ערך אחר.

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

שיפורים לאלגוריתם Backtracking: עקביות קשתות והיוריסטיקות

כדי לשפר את יעילות ה-Backtracking, משלבים בו טכניקות המפחיתות את מרחב החיפוש:

עקביות קשתות (Arc Consistency - AC)

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

אלגוריתם AC-3 (או AC-4, AC-5) פועל על ידי בדיקה חוזרת ונשנית של עקביות קשתות, עד שלא ניתן להסיר יותר ערכים מתחומים. הפעלת AC לפני החיפוש (pre-processing) או במהלך החיפוש (כמו ב-Forward Checking) יכולה לצמצם משמעותית את גודל עץ החיפוש.

היוריסטיקות בחירה

היוריסטיקות אלו מכוונות את אלגוריתם Backtracking בבחירת המשתנה הבא להקצאה ובבחירת הערך הבא למשתנה.

שאלות לדיון

• הסבירו את שלושת המרכיבים העיקריים של מודל CSP. תנו דוגמה לבעיה יומיומית ומדלו אותה כ-CSP.
• תארו את אלגוריתם Backtracking. מהם יתרונותיו וחסרונותיו בהשוואה לאלגוריתמי חיפוש כלליים?
• כיצד עקביות קשתות (Arc Consistency) משפרת את ביצועי אלגוריתם Backtracking? הדגימו את השפעתה על תחומי משתנים בבעיה פשוטה.
• השוו בין היוריסטיקת MRV ל-LCV. מתי נשתמש בכל אחת מהן, ומהי תרומתן הכוללת ליעילות פתרון בעיות CSP?
• הסבירו מדוע שילוב של טכניקות סינון (כמו עקביות קשתות) עם היוריסטיקות בחירה הוא קריטי לפתרון יעיל של בעיות CSP מורכבות.

נקודות לתשובת מודל

• מודל CSP: הגדרה ברורה של משתנים, תחומים ואילוצים. דוגמה קונקרטית (למשל, צביעת מפה, N-מלכות) עם פירוט המרכיבים.
• Backtracking: הסבר על תהליך החיפוש לעומק, נסיגה, ונקודות כשל. ציון היותו שלם ונכון, אך לא יעיל ללא שיפורים.
• עקביות קשתות: הגדרת קשת עקבית. הסבר על הסרת ערכים לא עקביים. הדגמה של צמצום תחומי משתנים והשפעה על עץ החיפוש (זיהוי מוקדם של כישלונות).
• היוריסטיקות: הסבר על MRV כבחירת המשתנה הקשה ביותר, ו-LCV כבחירת הערך הפחות מגביל. ניתוח תרומתן לקיצור החיפוש.
• שילוב טכניקות: הדגשה כי סינון (AC) מצמצם את מרחב החיפוש לפני או במהלך הקצאה, והיוריסטיקות מכוונות את החיפוש בתוך המרחב המצומצם. שילוב זה מאפשר התמודדות עם בעיות גדולות ומורכבות יותר.