יסודות פורמליים, מרחב המצבים וסוגי אילוצים ב-CSP
לפצח את עולם האילוצים מתוך הסתכלות שקופה
שלום חברים! בארבעת הפרקים הקודמים התרגלנו להתייחס למצבי עולם כאל "קופסאות שחורות" אטומיות (Atomic State Representation). באלגוריתמים כמו BFS, $A^*$ או מינימקס, המצב היה שלם ובלתי ניתן לחלוקה: יכולנו רק לשאול האם הגענו ליעד ($IsGoal(s)$), ולקבל את המצבים הבאים ($Successors(s)$), מבלי להבין מדוע מצב מסוים נכשל.
בפרק זה אנו מבצעים קפיצת מדרגה מהפכנית אל עבר ייצוג מפורק (Factored Representation): המצב אינו עוד מחרוזת סתומה בזיכרון, אלא אוסף שקוף של משתנים, שלכל אחד מהם תחום אפשרויות (Domain), הפועלים תחת רשת של אילוצים (Constraints).
שקיפות זו היא "קרן הרנטגן" של ה-AI: היא מאפשרת למנוע ההסקה לחשוף סתירות כבר בהשמות חלקיות, לגזום מיליארדי ענפי סרק עוד לפני שנבדקו, ולפתור בעיות מורכבות מסודוקו ועד שיבוץ רכבות עולמי באותו אלגוריתם גנרי בדיוק! בואו נצלול פנימה!
💡 אינטואיציה בגובה העיניים: אנלוגיית סידור הושבה בחתונה
תארו לעצמכם שאתם מפיקים חתונה וצריכים להושיב 100 אורחים ב-10 שולחנות. בחיפוש קלאסי, הייתם צריכים לסדר את כל 100 האורחים, ורק בסוף לבדוק: "האם דודה שרה יושבת ליד דוד משה שהיא ברוגז איתו?". אם כן – כל הסידור נזרק לפח ומתחילים מחדש!
במודל CSP, המשתנה הוא $Guest_i$, והתחום שלו הוא השולחן $Table \in \{1 \dots 10\}$. ברגע שהושבתם את דודה שרה בשולחן 3, האילוץ מפפעל מיד ומוחק את שולחן 3 מהתחום של דוד משה! המערכת לעולם לא תנסה אפילו להושיב אותו שם. זהו כוחה של הסקה מבוססת אילוצים!
1. ההגדרה הפורמלית של בעיית סיפוק אילוצים (CSP)
מבחינה מתמטית פורמלית, בעיית סיפוק אילוצים מוגדרת כשלשה סדורה:
$\mathcal{X} = \{X_1, X_2, \dots, X_n\}$: קבוצה סופית של $n$ משתנים המגדירים את המערכת (למשל: תאי סודוקו, צביעת מחוזות במפה, אותיות במילון).
$\mathcal{D} = \{D_1, D_2, \dots, D_n\}$: לכל משתנה $X_i$ תחום ערכים אפשריים $D_i$ (למשל צבעים $\{R, G, B\}$, ערכים בוליאניים $\{T, F\}$, או מילים בנות 3 אותיות).
$\mathcal{C} = \{C_1, C_2, \dots, C_m\}$: קבוצת אילוצים המגדירים שילובים חוקיים. כל אילוץ מוגדר ע"י טווח המשתנים (Scope) והיחס המותר (Relation).
🔢 תחומים בדידים: סופיים מול אינסופיים
תחום בדיד וסופי (Finite Discrete): גודל התחום חסום ע"י $d$. מספר המצבים השלמים הוא $O(d^n)$. למרות שהמרחב סופי, בעיות אלו (כגון 3-צביעה או 3-SAT) הן NP-Complete ומחייבות חיפוש נסיגה ויוריסטיקות חכמות.
תחום בדיד אינסופי (Infinite Discrete): משתנים בשלמים ($\mathbb{Z}$). לא ניתן למנות את הערכים, והפתרון נשען על בדיקת ספיקות לוגית (כגון Presburger Arithmetic).
📏 תחומים רציפים ושיטת Bounds Propagation
במשתנים רציפים בממשיים ($\mathbb{R}$, כגון זמני טיסה או כמויות דלק), התחום מיוצג ע"י קטע חסום $D_i = [l_i, u_i]$.
הפצת גבולות (Bounds Propagation): אילוצים לינאריים מכווצים את הקצוות: חסם עליון יורד וחסם תחתון עולה. כאשר כל האילוצים לינאריים, שיטות תכנות לינארי (Linear Programming) מוצאות פתרון בזמן פולינומי!
🧬 סיווג היררכי של אילוצים: מאונארי ועד גלובלי
מגביל משתנה בודד: $SA \ne green$. מיושם מיידית כקדם-עיבוד (Node Consistency).
מקשר בין שני משתנים: $X_1 \ne X_2$. מהווה קשת בגרף האילוצים הקלאסי.
מערב שלושה משתנים או יותר ($T + T = O$). ניתן להמרה לבינארי ע"י משתני עזר (Hidden Variables).
חל על קבוצה שרירותית: $\text{AllDifferent}(X_1 \dots X_n)$. מאפשר אלגוריתמי סינון ייעודיים רבי-עוצמה.
🎯 מדוע AllDifferent גלובלי עדיף על 45 אילוצי שונות בינאריים? (אלגוריתם Régin 1994)
נניח שנתונים שלושה משתנים $X_1, X_2, X_3$ עם התחומים $\{1, 2\}$. אם נפרק את הדרישה שכולם שונים ל-3 אילוצים בינאריים ($X_1 \ne X_2, X_2 \ne X_3, X_1 \ne X_3$), אלגוריתם עקביות קשת מקומי (AC-3) לא יסנן אף ערך! לכל ערך יש תומך בשכן.
אולם ממעוף הציפור ברור שהמצב בלתי אפשרי עקב עקרון שובך היונים: אי אפשר לשבץ 3 משתנים ב-2 ערכים בלבד! אלגוריתם רוגין (Régin, 1994) ממפה את האילוץ הגלובלי לבעיית שידוך מקסימלי בגרף דו-צדדי (Maximum Bipartite Matching). באמצעות מציאת רכיבים קשירים היטב (SCC) באלגוריתם Tarjan בסיבוכיות מרשימה של $O(\sqrt{n}|E|)$, האלגוריתם מוכיח חוסר ספיקות מיד או מוחק קשתות שאינן משתתפות באף שידוך חוקי!
מעבדה אינטראקטיבית 5.1: מעבדת האילוצים השקופה (Factored Representation Lab)
מנגנוני הסקה, עקביות והפצת אילוצים (Constraint Propagation)
למה לנחש כשאפשר לדעת בוודאות?
שלום לכולם! בחיפוש קלאסי, הדרך היחידה לדעת אם נתיב מסוים מוביל למבוי סתום הייתה לצעוד בו פיזית עד לקיר. ב-CSP יש לנו נשק סודי שנקרא הפצת אילוצים (Constraint Propagation).
הרעיון הבסיסי הוא פשוט וגאוני: לפני שאנחנו מנחשים אפילו ערך אחד בעץ החיפוש, אנחנו מפעילים מנוע הסקה לוגי מקומי שרץ על רשת האילוצים. המנוע בודק אילו ערכים אינם יכולים להשתתף בשום פתרון חוקי, ומוחק אותם ללא רחמים מהתחומים! לעיתים קרובות, סינון זה פותר את הבעיה כולה באפס זמן, או מוכיח שאין לה פתרון (Domain Wipeout).
ביחידה זו נחקור את עקביות הצומת, עקביות הקשת, ונבין את הקרב המרתק בין אלגוריתמי AC-3, AC-4 ו-AC-2001. בואו נתחיל!
💡 אינטואיציה בגובה העיניים: אפקט הדומינו בסינון אפשרויות
תארו לעצמכם שורה של קוביות דומינו. מחיקת ערך ממשתנה $X$ עקב אילוץ גורמת לכך שלערך של משתנה שכן $Y$ כבר אין תמיכה! לכן גם הערך של $Y$ נמחק. אך כעת, לשכן של $Y$ (משתנה $Z$) אין תמיכה, וגם אצלו נמחק ערך! זהו אפקט הפצת האילוצים: גל צונאמי של צמצומים שמתפשט בכל הרשת עד להגעה למצב יציב (עקבי) או לקריסה מוחלטת.
1. עקביות צומת (Node Consistency - NC)
משתנה $X$ הוא עקבי צומת אם כל ערך בתחומו $D(X)$ מקיים את כל האילוצים האונאריים החלים עליו.
סיבוכיות: $O(nd)$ בלבד. תמיד מבוצע כצעד קדם-עיבוד (Pre-processing) ראשוני.
2. עקביות קשת (Arc Consistency - AC)
קשת מכוונת $X \to Y$ היא עקבית קשת אם ורק אם לכל ערך $x \in D(X)$ קיים לפחות ערך תומך אחד $y \in D(Y)$ המקיים את האילוץ הבינארי ביניהם.
קריטי: עקביות קשת היא כיוונית! הקשת $X \to Y$ יכולה להיות עקבית בעוד הקשת ההפוכה $Y \to X$ אינה עקבית. גרף נקרא עקבי קשת אם כל הקשתות המכוונות שבו עקביות.
⚡ האבולוציה של אלגוריתמי עקביות קשת: מ-AC-3 ועד AC-2001
כיצד בודקים ומתחזקים עקביות קשת ביעילות? התפתחות האלגוריתמים משקפת מאבק קלאסי במדעי המחשב בין סיבוכיות זמן לסיבוכיות זיכרון:
מנהל תור של קשתות לבדיקה. כאשר ערך נמחק מ-$X$, מחזיר לתור את כל הקשתות הנכנסות לשכניו של $X$.
מתעד במפורש רשימת תמיכה לכל צמד משתנה-ערך ($S_{y,v}$) ומחזיק מונה תומכים ($counter[(X, Y), x]$).
מהפכת ה-Last Support (Residue): שומר מצביע יחיד לתומך האחרון שנמצא. חידוש החיפוש נעשה אך ורק מאותו מצביע והלאה!
| אלגוריתם | זמן במקרה הגרוע | זיכרון במקרה הגרוע | עקרון פעולה מרכזי |
|---|---|---|---|
| AC-3 | $O(c \cdot d^3)$ | $O(c + n \cdot d)$ | סורק תחומים מחדש מתחילתם בכל פעם שקשת נכנסת לתור. |
| AC-4 | $O(c \cdot d^2)$ | $O(c \cdot d^2)$ | בונה רשימות תמיכה ומערכי מונים מפורשים; כבד מדי בזיכרון. |
| AC-2001 (AC-3.1) | $O(c \cdot d^2)$ | $O(c \cdot d)$ | שומר מצביע תומך אחרון (Residue) וממשיך תמיד קדימה בסדר קבוע. |
📐 עקביות מסלול (Path Consistency) ו-k-Consistency: מדוע נזהרים מהן?
עקביות קשת בודקת רק זוגות מבודדים. עקביות מסלול (3-Consistency) בודקת שלשות: לכל השמה עקבית של זוג משתנים $\{X_i, X_j\}$, קיים ערך במשתנה שלישי $X_m$ העקבי עם שניהם בו-זמנית.
מדוע פותרנים מעדיפים AC? סיבוכיות הזמן של PC-2 היא $O(n^3 d^5)$, והיא מוסיפה אילוצים בינאריים חדשים המשנים את טופולוגיית הגרף. העלות החישובית של שמירת עקביות מסלול עולה בהרבה על התועלת ברוב המוחלט של הבעיות המעשיות!
מעבדה אינטראקטיבית 5.2: מפלי ההסקה (AC-3 vs AC-2001 Propagation Cascades)
חיפוש נסיגה (Backtracking), יוריסטיקות בחירה ומבט לאחור (CBJ)
כשהחיפוש נתקע בקיר – איך קופצים מעל הסתירה?
שלום חברים! גם מנועי ההסקה החזקים ביותר כמו AC-3 אינם פותרים בעיות NP-Complete ללא חיפוש. בשלב מסוים, אין ברירה אלא לבצע ניחוש מבוקר (Branching).
אבל שימו לב להבדל העצום בין חיפוש רגיל ל-CSP: בעץ החיפוש של CSP העומק תמיד קבוע ($n$), וגורם ההסתעפות תמיד חסום ($d$). אין כאן שום סכנה ללולאות אינסופיות!
השאלה הקריטית היא באיזה סדר לבחור את המשתנים והערכים, ומה לעשות כשנקלעים למבוי סתום:
האם נחזור עיוורת צעד אחד אחורה ונתפלש בטעויות סרק (נסיגה כרונולוגית), או שנבצע "קפיצה קוונטית" היישר אל המשתנה האשם בסתירה (Conflict-Directed Backjumping)?
ביחידה זו נלמד את עקרונות הברזל Fail-First ו-Fail-Last, את אלגוריתמי ה-Look-back, ואת מודל ה-dom/wdeg המודרני!
💡 אינטואיציה בגובה העיניים: איתור התקלה האמיתית במוסך
נניח שהרכב שלכם נעצר. המכונאי הרכיב גלגל, החליף שטיח, ניקה את השמשה, ואז גילה שהמנוע לא מקבל דלק. נסיגה כרונולוגית טיפשית תחזור להחליף שוב את השטיח, שוב את הגלגל, ושוב תיכשל! חזרה מונחית קונפליקטים (CBJ) אומרת מיד: "השטיח והגלגל כלל לא קשורים לסתימת הדלק! נחזור מיד למשאבת הדלק שהרכבנו בהתחלה!".
⚖️ 1. עקרונות העל: Fail-First בבחירת משתנים מול Fail-Last בבחירת ערכים
המטרה: להיכשל מוקדם ככל האפשר! אם ענף נועד לכישלון, אנו רוצים לגלות זאת מיד בשורש העץ, ולא אחרי שירדנו עומק 50.
המטרה: להצליח בניסיון הראשון! מאחר שאנו זקוקים רק לפתרון חוקי בודד, אנו רוצים לבחור את הערך בעל הסיכוי המרבי להוביל להשלמה.
🧠 2. הסקה תוך כדי חיפוש: Forward Checking מול MAC ו-dom/wdeg המודרני
בכל פעם שמשתנה מוצב, בודק עקביות קשת רק בינו לבין שכניו הישירים. מהיר וזול, אך אינו מפעפע הלאה (עיוור לאפקט הדומינו בין השכנים).
לאחר כל השמה, מריץ AC-3 מלא על כל הקשתות שעלולות להיות מושפעות! מזהה סתירות עמוקות בהרבה מ-FC, ומקצר את עץ החיפוש בסדרי גודל.
מעלה משקל ($weight + 1$) לאילוץ שגרם להתרוקנות תחום (DWO). בוחרת משתנה הממזער את $\frac{|D(X)|}{\sum w(e)}$. לומדת אונליין את האזורים הקשים!
🚀 3. מנגנוני מבט לאחור (Look-back): Conflict-Directed Backjumping ו-Nogoods
כאשר כל הערכים של משתנה $X_i$ נפסלים (Dead End), נסיגה כרונולוגית חוזרת תמיד ל-$X_{i-1}$. אך אם $X_{i-1}$ אינו קשור כלל לסתירה, החיפוש ייכשל שוב ושוב!
1. לכל משתנה מנוהלת קבוצת קונפליקט (Conflict Set): $CS(X_i)$, המכילה את כל המשתנים שכבר הושמו ואחראים למחיקת ערכים מ-$D(X_i)$.
2. בעת כשל, האלגוריתם מוצא את המשתנה העמוק ביותר בקבוצת הקונפליקט: $$h = \max \{ \text{level}(X_j) \mid X_j \in CS(X_i) \}$$ 3. **קפיצת ה-Backjump:** מדלגים ישירות לרמה $h$ ומבטלים את כל ההשמות שבאמצע!
4. ספיגת קונפליקטים (Conflict Absorption): קבוצת הקונפליקט של המשתנה שנכשל מתמזגת לתוך קבוצת הקונפליקט של המשתנה שאליו קפצנו: $$CS(X_h) \leftarrow CS(X_h) \cup (CS(X_i) \setminus \{X_h\})$$
מעבדה אינטראקטיבית 5.3: זירת החיפוש והיוריסטיקות המתקדמות (Heuristics Arena & CBJ)
טופולוגיית גרף, עצים, חיפוש מקומי ומעברי פאזה
כשהטופולוגיה מוחקת את הסיבוכיות המעריכית
שלום לכולם! עד כה התייחסנו לגרף האילוצים כמבנה כללי ושרירותי. אבל מתברר שלצורה הגאומטרית של רשת האילוצים יש השפעה דרמטית על זמן החישוב:
אם גרף האילוצים הוא עץ (נטול מעגלים), קורה נס אלגוריתמי אמיתי – ניתן לפתור את הבעיה כולה בזמן לינארי $O(nd^2)$ בלבד, ללא צורך באף צעד נסיגה בודד (Backtrack-free)!
ומה אם יש מעגלים? נלמד איך "לחתוך" אותם בעזרת קבוצת Cycle Cutset או לפרק את הגרף לצבירי עצים (Tree Decomposition).
בהמשך, נחקור את הקצה השני: כיצד אלגוריתם חיפוש מקומי פשוט כמו Min-Conflicts פותר בעיות של מיליון מלכות בתוך שניות ספורות, ומדוע קושי החישוב של בעיות אקראיות קורס לתוך "מעבר פאזה" קריטי סביב היחס 4.26. בואו נגלה!
💡 אינטואיציה בגובה העיניים: היררכיה צבאית ללא סתירות מול פקק תנועה מעגלי
בעץ היררכי (מפקד $\to$ קצינים $\to$ חיילים), פקודה יורדת מלמעלה למטה ואין שום אפשרות לסתירה פנימית במעגל. אבל כשנוצר מעגל (א' תלוי ב-ב', ב' תלוי ב-ג', ו-ג' תלוי ב-א'), נוצר "פקק תנועה": כל החלטה של גורם אחד עלולה לסתור את ההחלטה של הגורם שממנו יצאה! לכן חיסול מעגלים הוא המפתח למהירות שיא ב-CSP.
🌳 1. גרף אילוצים בצורת עץ: פתרון בזמן לינארי $O(nd^2)$ והוכחת Backtrack-free
כאשר גרף האילוצים הוא עץ (קשיר ונטול מעגלים), אלגוריתם מבריק בן שני שלבים פותר את הבעיה ללא כל חיפוש נסיגה:
1. בוחרים צומת שרירותי כשורש ומסדרים את המשתנים במיון טופולוגי: $X_1, X_2, \dots, X_n$ כך שכל אב מופיע לפני בניו.
2. עבור $i = n$ עד 2 (מעלים לשורש):
מפעילים RemoveInconsistentValues(Parent(Xi), Xi) ומסננים ערכים מהאב שאין להם תומך בבן.
1. מציבים ערך חוקי כלשהו בשורש $X_1$.
2. עבור $i = 2$ עד $n$ (בסדר יורד מהאב לבנים):
לכל בן $X_i$, בוחרים ערך בתחומו העקבי עם הערך שכבר נקבע לאביו $Parent(X_i)$.
מובטח מתמטית שתמיד יימצא ערך תומך כזה!
✂️ מפריד מעגלים (Cycle Cutset) והתניה
אם הגרף אינו עץ, ניתן לבחור תת-קבוצה קטנה של משתנים $S \subset \mathcal{X}$ (קבוצת Cutset) שהסרתם מותירה את שאר הגרף כעץ!
האלגוריתם: מנסים את כל $d^c$ ההשמות האפשריות לקבוצה $S$ (כאשר $|S| = c$). לכל השמה כזו, מריצים את אלגוריתם העץ הלינארי על $n-c$ המשתנים הנותרים ב-$O((n-c)d^2)$.
סיבוכיות כוללת: $O(d^c \cdot (n-c)d^2)$ – מהיר לאין שיעור מ-$O(d^n)$ כאשר $c \ll n$!
🌲 פירוק לעצים ורוחב עץ (Tree Decomposition & Treewidth)
שיטה מתקדמת המקבצת משתנים לצבירים (Mega-Variables) המאורגנים בעץ, תוך שמירה על רציפות (Connected Running Intersection).
אם הצביר הגדול ביותר מכיל $w+1$ משתנים ($w$ נקרא רוחב העץ - Treewidth), הבעיה נפתרת בסיבוכיות: $$O(n \cdot d^{w+1})$$ אם רוחב העץ חסום ע"י קבוע, ה-CSP נפתר בזמן פולינומי!
⚡ 3. חיפוש מקומי (Min-Conflicts), WalkSAT ומעברי פאזה קריטיים
במקום לבנות פתרון מאפס, מתחילים בהשמה שלמה אקראית לכל המשתנים. בכל צעד, בוחרים משתנה המעורב בקונפליקט, ומעבירים אותו לערך הממזער את מספר ההתנגשויות הכולל. בבעיות צפופות בפתרונות כמו N-Queens, האלגוריתם פותר מיליון מלכות בכ-50 צעדים בלבד!
בבעיות 3-SAT אקראיות, יחס הפסוקיות למשתנים ($\alpha = m/n$) מכתיב את הקושי: עבור $\alpha < 4.2$: כמעט תמיד יש פתרון קל. עבור $\alpha > 4.3$: כמעט תמיד אין פתרון ונפסל מיד. בדיוק באזור $\alpha \approx 4.26$: זמן החיפוש מזנק מעריכית לשיא (The Hard Region)!
מעבדה אינטראקטיבית 5.4: חיפוש מקומי ומעברי פאזה (Min-Conflicts & Phase Transitions Lab)
ניתוח מקרי בוחן ותרגילי מאסטר יישומיים
פירוק וניתוח תרגילים מורכבים בדיוק כירורגי
שלום לכולם! הגענו ליחידת השיא המעשית של הפרק: שני מקרי בוחן קלאסיים ומורכבים ברמת בחינה מעמיקה.
שאלות ותרגילים אלו משלבים את כל התיאוריה שלמדנו – מודלים, גרפי אילוצים, אלגוריתמי עקביות קשת AC-3, חיפוש נסיגה מונחה היוריסטיקות (MRV, Degree, LCV) ו-Forward Checking.
במדריך שלפניכם נפתור כל שאלה שלב-אחר-שלב, נסביר את שיקולי המידול, נציג מעקב אלגוריתמי מדויק עם טבלאות מצב, ונוכיח את הטענות הלוגיות העמוקות (כגון תופעת ה-Vacuously True שסטודנטים רבים נופלים בה). בואו נתחיל!
💡 אינטואיציה בגובה העיניים: שפת המידול הנכונה חוסכת 99% מהמאמץ
תארו לעצמכם שאתם צריכים לתאר תשבץ: האם תגדירו כל משבצת בודדת כמשתנה עם 26 אותיות (מרחב של $26^9 \approx 5.4 \times 10^{12}$ מצבים), או שתגדירו 6 מילים כמשתנים מתוך מאגר של 40 מילים ($40^6 \approx 4 \times 10^9$ מצבים)? הבחירה בייצוג הנכון מקטינה את המרחב ומאפשרת לאלגוריתם AC-3 לכווץ את התחום לשתי מילים בלבד תוך שניות ספורות!
🧩 מקרה בוחן 1: תשבץ מילים בגודל $3 \times 3$ מתוך מאגר 40 מילים
תרגיל מאסטר 1נתון לוח תשבץ ריק בגודל $3 \times 3$. יש לשבץ בו 3 מילים אופקיות ($A_1, A_2, A_3$) ו-3 מילים אנכיות ($D_1, D_2, D_3$) מתוך מאגר נתון בן 40 מילים בנות 3 אותיות באנגלית, כאשר כל מילה מופיעה לכל היותר פעם אחת (אילוץ AllDiff).
• משתנים: $\mathcal{X} = \{A_1, A_2, A_3, D_1, D_2, D_3\}$ (6 משתנים).
• תחומים: לכל $X \in \mathcal{X}$, $D(X) = \text{מאגר 40 המילים}$.
• אילוצים בינאריים: 9 אילוצי הצטלבות אותיות:
$$A_i[j] = D_j[i] \quad \forall i, j \in \{1, 2, 3\}$$
גרף האילוצים הוא גרף דו-צדדי מלא $K_{3,3}$ (בתוספת אילוץ שוני גלובלי AllDiff).
בבעיה זו לא נתון שום אילוץ אונארי על משתנה בודד (אין הגבלה מראש על אות ראשונה או מילה ספציפית). לכן, עקביות צומת אינה מוחקת אף מילה, וכל התחומים נשארים בגודל מלא: $|D(X)| = 40$.
הפעלת AC-3 בודקת התאמות הצלבה הדדיות. מילים רבות נמחקות כי אין להן תומך בהצטלבויות (למשל מילה עם אות נדירה במיקום 2 שאינה מופיעה כראשונה באף מילה). בתום פעפוע AC-3, מתרחש צמצום פנומנלי – לכל משתנה נותרות בדיוק 2 מילים חוקיות בלבד:
1. בחירת משתנה: כל התחומים בגודל 2 (תיקו ב-MRV) ובדרגה 3 מול המאונכים (תיקו ב-Degree). שוברים שוויון לפי סדר לקסיקוגרפי ובוחרים ב-$A_1$.
2. בחירת ערך ב-$A_1$: מציבים $A_1 = boa$.
3. הפעלת Forward Checking:
• מול $D_1$: האות הראשונה של $A_1$ היא 'b' $\implies$ ב-$D_1$ נשארת רק bee ('b' ראשונה), המילה boa נפסלת!
• מול $D_2$: האות השנייה של $A_1$ היא 'o' $\implies$ ב-$D_2$ נשארת רק oaf ('o' ראשונה), ear נפסלת!
• מול $D_3$: האות השלישית של $A_1$ היא 'a' $\implies$ ב-$D_3$ נשארת רק art ('a' ראשונה), eft נפסלת!
4. המשך השמות דטרמיניסטי: כעת כל העמודות קבועות יחידנית! השמתן קובעת מיידית את $A_2 = ear$ ואת $A_3 = eft$.
5. הפתרון השלם והיחיד:
עמודות: $D_1 = \text{bee}, \ D_2 = \text{oaf}, \ D_3 = \text{art}$
🔢 מקרה בוחן 2: תת-קבוצת מספרים זרים (Coprime Subset) כ-CSP בוליאני
תרגיל מאסטר 2נתונה קבוצת מספרים: $S = \{4, 6, 10, 12, 25, 32, 40, 57\}$. עלינו למצוא תת-קבוצה בגודל $p = 3$ מספרים שהם זרים זה לזה בזוגות ($\gcd(x, y) = 1$).
• משתנים: $x_i \in \{T, F\}$ לכל מספר ב-$S$ (8 משתנים בוליאניים). $x_i = T$ פירושו שהמספר נבחר לתת-הקבוצה.
• אילוץ גלובלי: בדיוק 3 משתנים מקבלים $T$: $\sum_{i=1}^8 \mathbb{I}(x_i = T) = 3$.
• אילוצים בינאריים: לכל זוג שאינו זר ($\gcd(a_i, a_j) > 1$), אסור לבחור את שניהם במקביל:
$$\neg (x_i \land x_j) \iff (\neg x_i \lor \neg x_j)$$
• עיוורון MRV בשורש: בשורש עץ החיפוש, אף משתנה טרם הושם. התחום של כל 8 המשתנים הוא $\{T, F\}$ (גודל 2 בדיוק). לכן MRV אינו מסוגל לבחור ומוחזר שוויון מלא בין כל 8 המשתנים!
• שבירת שוויון ע"י Degree Heuristic: סופרים כמה אילוצי אי-זרות חלים על כל משתנה:
למספרים 6, 10, 12, 40 יש דרגה 6 (הם מתחלקים ב-2 ולכן יש להם קשת מול כל הזוגיים האחרים!).
לכן Degree Heuristic תבחר אחד מהם מיד כמשתנה הראשון בשורש!
שאלה מרכזית בבחינה: אם הפעלנו Forward Checking, האם הפעלת AC-3 מלאה נוספת תצמצם תחומים נוספים? התשובה היא: לא! שום ערך נוסף לא יימחק לעולם!
1. אם משתנה קיבל $x_i = True$, Forward Checking כבר מוחק את $True$ מכל שכניו (קובע אותם ל-$False$).
2. עבור כל משתנה שקיבל $x_i = False$: האילוץ הבינארי מול כל שכן $x_j$ הוא $\neg(x_i \land x_j)$.
נציב $x_i = False$: $$\neg(False \land x_j) = \neg False = True$$ האילוץ מתקיים תמיד בזהות, ללא שום תלות בערך שייבחר ל-$x_j$ (מתקיים באופן ריק - Vacuously True)!
3. מאחר שכל האילוצים של המשתנים שהושמו מסופקים באופן ריק, אף קשת אינה יכולה להפר עקביות, ו-AC-3 לא ימחק אף ערך.
🏛️ מקרה בוחן 3: שיבוץ 4 מבנים ברשת 6 משבצות קמפוס והרצת AC-3 מלאה וחיפוש נסיגה
שאלת דגל ממבחני הקורסתרגיל זה מהווה את שאלת המפתח הקלאסית ביותר להבנה מעמיקה של אלגוריתם עקביות קשת AC-3 בשילוב חיפוש נסיגה (Backtracking) עם Forward Checking ו-MRV.
הנהלת הקמפוס מעוניינת לשבץ 4 מבנים חדשים: $A$ (אודיטוריום), $B$ (ספרייה), $C$ (קפיטריה) ו-$D$ (מעבדות מחשבים) בתוך רשת של 6 מגרשים ממוספרים ($2 \times 3$).
• משתנים: $\mathcal{X} = \{A, B, C, D\}$.
• תחומים ראשוניים: $D_A = D_B = D_C = D_D = \{1, 2, 3, 4, 5, 6\}$.
📜 שבעת האילוצים הפורמליים של הבעיה:
כל מבנה חייב להיות במגרש נפרד: $A \neq B, A \neq C, A \neq D, B \neq C, B \neq D, C \neq D$.
מבנה $A$ חייב להימצא בשורה העליונה: $A \in \{1, 2, 3\}$.
מבנה $B$ חייב להימצא בשורה התחתונה: $B \in \{4, 5, 6\}$.
עמודת מבנה $B$ גדולה מעמודת מבנה $A$: $col(B) > col(A)$.
מבנה $C$ חייב להיות שכן צמוד של $A$: $Adjacent(A, C) = True$.
מבנה $D$ אסור שיהיה צמוד למבנה $A$: $Adjacent(A, D) = False$.
מבנה $C$ חייב להימצא בעמודה 2 או 3 בלבד: $col(C) \in \{2, 3\} \implies C \in \{2, 3, 5, 6\}$.
⚙️ שלב א': הרצת אלגוריתם AC-3 על תור הקשתות וצמצום התחומים
תחילה מופעלת עקביות צומת (אילוצים אונאריים 2, 3, 7):
$D_A = \{1, 2, 3\}, \quad D_B = \{4, 5, 6\}, \quad D_C = \{2, 3, 5, 6\}, \quad D_D = \{1, 2, 3, 4, 5, 6\}$.
כעת נכנסות הקשתות הבינאריות לתור ומעובדות בסדר AC-3:
| קשת שנבדקת | בדיקת תמיכה והסבר לוגי | ערכים שנמחקים | תחום מעודכן |
|---|---|---|---|
| (A, B) |
עבור $a \in D_A$, נדרש $b \in D_B$ כך ש-$col(b) > col(a)$. אם $a=3$, עמודתו היא 3 (העמודה המרבית). אין ב-$D_B$ שום משבצת עם עמודה גדולה מ-3! |
מחיקת 3 מ-D_A | D_A = {1, 2} |
| (B, A) |
עבור $b \in D_B$, נדרש $a \in D_A = \{1, 2\}$ כך ש-$col(b) > col(a)$. אם $b=4$, עמודתו היא 1. אין ב-$D_A$ אף משבצת עם עמודה קטנה מ-1! |
מחיקת 4 מ-D_B | D_B = {5, 6} |
| (C, A) |
עבור $c \in D_C$, נדרש $a \in D_A = \{1, 2\}$ כך ש-$Adjacent(a, c)$. השכנים של 1 הם $\{2, 4\}$; השכנים של 2 הם $\{1, 3, 5\}$. משבצת 6 אינה שכנה של 1 ואינה שכנה של 2! אין לה שום תומך ב-$D_A$. |
מחיקת 6 מ-D_C | D_C = {2, 3, 5} |
| (A, C) | לכל $a \in \{1, 2\}$ קיים לפחות שכן אחד ב-$D_C = \{2, 3, 5\}$ (עבור 1 יש את 2; עבור 2 יש את 3 ו-5). | אין מחיקות | D_A = {1, 2} |
🌳 שלב ב': חיפוש נסיגה (Backtracking) מונחה MRV ו-Forward Checking
התחומים הקטנים ביותר הם של $A$ (גודל 2) ושל $B$ (גודל 2). שוויון ב-MRV.
לפי Degree Heuristic, על המשתנה $A$ חלים 4 אילוצים פעילים (מול $B, C, D$ ושונות), לעומת 3 על $B$. לכן בוחרים ב-$A$.
• מציבים $A = 1$.
• Forward Checking על C: $C$ חייב להיות שכן של 1 $\implies C \in \{2, 4\} \cap \{2, 3, 5\} = \{2\}$.
נקבע $C = 2$ בכפייה!
• Forward Checking על D: $D$ אסור שיהיה שכן של 1 (אסור 2, 4), ואינו יכול להיות 1 או 2 (AllDiff) $\implies D \in \{3, 5, 6\}$.
• Forward Checking על B: $col(B) > 1 \implies B \in \{5, 6\}$.
אם $B=5$, נותר $D \in \{3, 6\}$. אולם $C=2$ מחייב שונות ומיקום חוקי. ענף זה מייצר פתרון חלופי או נסיגה לפי אילוצי המשך.
• מציבים $A = 2$.
• Forward Checking על B: $col(B) > col(A)=2 \implies col(B)=3$. מאחר ש-$B \in \{5, 6\}$, המגרש היחיד בעמודה 3 הוא $B = 6$!
• Forward Checking על D: $D$ אסור שיהיה שכן של $A=2$ (אסור $\{1, 3, 5\}$). כמו כן אסור שיהיה 2 או 6 (AllDiff).
מתוך $\{1, 2, 3, 4, 5, 6\}$ נפסלים: $\{1, 2, 3, 5, 6\}$.
נותר עבור D ערך יחיד בלבד: $D = 4$!
• Forward Checking על C: $C$ חייב להיות שכן של $A=2 \implies C \in \{1, 3, 5\}$. המגרשים 1, 3 נפסלים או נתפסים, והמגרש הפנוי היחיד הוא $C = 5$!
🏆 הפתרון הסופי המאומת של בעיית הקמפוס:
A=2, B=6, C=5, D=4מעבדה אינטראקטיבית 5.5: פותרן הבחינות האינטראקטיבי (Crossword & Coprime Solvers)
סיכום מנהלים, מפת דרכים וגשר לקראת פרק 6
לסגור את מעגל החיפוש ולהביט אל העתיד
ברכות חמות! השלמתם את אחד הפרקים העשירים, המרתקים והמאתגרים ביותר בקורס מבוא לבינה מלאכותית.
עברתם דרך מרתקת: מהבנת המבנה המפורק של בעיות, דרך אלגוריתמי סינון מתוחכמים (AC-3, AC-2001 ו-Régin), יוריסטיקות בחירה מונחות כישלון, מנגנוני נסיגה מדויקים, ועד לפתרון מלא של בחינות מאסטר.
כדי לעשות סדר מושלם בראש לפני המבחן, ריכזנו עבורכם ביחידה זו את The Master CSP Cheat-Sheet – טבלת השוואת-על המאגדת את כלל האלגוריתמים, הסיבוכיות שלהם ומתי להשתמש בהם, לצד צ'ק-ליסט של המלכודות הנפוצות ביותר במבחנים, וגשר לקראת פרק 6.
📊 טבלת השוואת-על של אלגוריתמי סיפוק אילוצים (The Master CSP Cheat-Sheet)
| אלגוריתם / שיטה | סיבוכיות זמן | סיבוכיות זיכרון | יתרון מרכזי ושימוש מומלץ |
|---|---|---|---|
| AC-3 | $O(c \cdot d^3)$ | $O(c + nd)$ | פשוט מאוד למימוש, זיכרון מינימלי. מתאים לרוב המערכות. |
| AC-4 | $O(c \cdot d^2)$ | $O(c \cdot d^2)$ | זמן אופטימלי במקרה הגרוע, אך בזבזני בזיכרון. כמעט לא בשימוש. |
| AC-2001 (AC-3.1) | $O(c \cdot d^2)$ | $O(cd)$ | השילוב המושלם: זמן אופטימלי עם זיכרון לינארי (Last Support). הסטנדרט כיום. |
| Tree-structured CSP | $O(n \cdot d^2)$ | $O(nd)$ | זמן לינארי מוחלט! השמה ללא נסיגות (Backtrack-free) בגרפים ללא מעגלים. |
| Cycle Cutset | $O(d^c \cdot (n-c)d^2)$ | $O(nd)$ | מצוין כאשר קבוצת מפריד המעגלים קטנה ($c \ll n$). חוסך חיפוש מעריכי מלא. |
| Tree Decomposition | $O(n \cdot d^{w+1})$ | $O(n \cdot d^w)$ | פתרון פולינומי כאשר רוחב העץ $w$ קטן וחסום. |
| Min-Conflicts | משתנה (מקומי) | $O(n)$ | פותר בעיות ענק (מיליון מלכות) בשניות בבעיות צפופות בפתרונות. |
| MAC + dom/wdeg + CBJ | $O(d^n)$ חסום מעשית | $O(cd + n^2)$ | חוד החנית של הפותרנים התעשייתיים בעולם לבעיות NP-Hard קשות. |
⚠️ צ'ק-ליסט קריטי ומלכודות נפוצות ב-CSP
🌉 גשר לקראת פרק 6: מחיפוש קלאסי למהפכת הלמידה החישובית
בחמשת הפרקים הראשונים של הקורס שלט פרדיגמת החיפוש וההסקה המפורשת: המודל היה ידוע מראש, החוקים נוסחו במדויק, והסוכן תכנן את מהלכיו באופן דטרמיניסטי.
אך מה קורה כשהעולם רועש, אי-ודאי, והחוקים אינם ידועים מראש? בפרק 6 נחצה את הקווים אל עבר תורת ההסתברות, מודלים של קבלת החלטות בתנאי אי-ודאות (Markov Decision Processes - MDPs) ולמידת חיזוק (Reinforcement Learning). נתראה בפרק הבא!