תנאי אופטימליות בחיפוש מיודע ($A^*$) ועקביות היוריסטית
💡 מבוא פדגוגי: הקסם של $A^*$ והמלכודת הנסתרת
שלום חברים! בפרק הקודם פגשנו את אלגוריתם $A^*$ והתפעלנו מפונקציית ההערכה ההרמונית שלו: $f(n) = g(n) + h(n)$. הרעיון הוא פשוט וגאוני: לקחת את עלות העבר המוכחת $g(n)$ ולחבר אליה הערכה של שארית הדרך $h(n)$. אך כאן נשאלת שאלת מיליון הדולר: באילו תנאים מתמטיים מובטח ש-$A^*$ יחזיר תמיד את הפתרון האופטימלי הזול ביותר? כפי שנראה מיד, הדרישה משתנה באופן דרמטי בין חיפוש עץ (Tree Search) הדורש רק קבילות, לבין חיפוש גרף (Graph Search) המחייב תכונה מחמירה בהרבה: עקביות (מונוטוניות). בואו נצלול פנימה ונפרק את המתמטיקה שלב אחר שלב.
🎯 1. היוריסטיקה קבילה (Admissible Heuristic) - התנאי לחיפוש עץ
הגדרה פורמלית: היוריסטיקה $h(n)$ נקראת קבילה אם לכל צומת $n$ במרחב המצבים, היא לעולם אינה מעריכה הערכת יתר (Never Overestimates) את עלות ההגעה האמיתית המינימלית למטרה.
כאשר $h^*(n)$ מייצגת את העלות האמיתית והמדויקת של המסלול הזול ביותר מ-$n$ אל היעד. המודל המנטלי: היוריסטיקה קבילה היא פונקציה "אופטימית תמידית". היא עשויה לחשוב שהדרך קצרה מכפי שהיא באמת (הערכת חסר), אך לעולם אינה מפחידה את האלגוריתם בהערכה מוגזמת שתגרום לו לפסול נתיב מבטיח.
נניח בשלילה ש-$A^*$ בחר לסיים עם יעד סאב-אופטימלי $G_2$ שעלותו $g(G_2) > C^*$. מאחר ש-$G_2$ הוא מטרה, מתקיים $f(G_2) = g(G_2) > C^*$.
אולם, לאורך המסלול אל היעד האופטימלי קיים צומת $n$ שטרם הורחב ונמצא בחזית (Frontier). מאחר ש-$h$ קבילה:
$$f(n) = g(n) + h(n) \le g(n) + h^*(n) = C^*$$
לפיכך מתקיים תמיד $f(n) \le C^* < f(G_2)$. תור הקדימויות יעדיף בהכרח להרחיב את $n$ לפני שליפת $G_2$, ולכן $G_2$ לעולם לא יישלף לפני מציאת הפתרון האופטימלי!
📐 2. היוריסטיקה עקבית / מונוטונית (Consistent / Monotonic Heuristic) - התנאי לחיפוש גרף
הגדרה פורמלית: היוריסטיקה $h(n)$ נקראת עקבית (Consistent) אם לכל צומת $n$ ולכל עוקב $n'$ של $n$ שנוצר על ידי פעולה $a$ בעלות $c(n, a, n')$, מתקיים אי-שוויון המשולש (Triangle Inequality):
המשמעות האינטואיטיבית: הערכת המרחק למטרה מצומת נוכחי אינה יכולה לרדת בשיעור העולה על עלות הצעד הפיזי שבוצע בפועל. אם צעד בודד עולה 1, המרחק המוערך למטרה אינו יכול להתקצר בפתאומיות ב-5!
נחשב את ערך ה-$f$ של הצומת העוקב $n'$: $$f(n') = g(n') + h(n') = g(n) + c(n, a, n') + h(n') \ge g(n) + h(n) = f(n)$$ ערכי ה-$f(n)$ לאורך כל נתיב חיפוש הם מונוטוניים עולים (אי-יורדים). המשמעות המעשית הקריטית: כאשר צומת נשלף מה-Frontier, מובטח שנמצא המסלול האופטימלי הזול ביותר אליו. לכן ניתן להכניסו ל-Explored Set (רשימה סגורה) ולעולם לא לפתוח אותו מחדש!
• ההפך אינו נכון: קיימות היוריסטיקות קבילות לחלוטין שאינן עקביות! בחיפוש גרף, חוסר עקביות מוביל לאסון אלגוריתמי.
⚠️ 3. הדוגמה הנגדית הקלאסית: כשל $A^*$ בחיפוש גרף עם היוריסטיקה קבילה שאינה עקבית
להלן ניתוח מלא של גרף הדוגמה הנגדית הקלאסי. נבחן שלב אחר שלב כיצד היוריסטיקה קבילה שוברת את עקביות אי-שוויון המשולש, ומכשילה את אלגוריתם $A^*$ בגרסת חיפוש גרף ממציאת הפתרון האופטימלי:
קשת מ-B (עלות 2)
(צומת מטרה)
✓ הוכחת קבילות ההיוריסטיקה (Admissibility)
- $h^*(C) = 10 \ge h(C) = 5$ (קביל).
- $h^*(B) = c(B,C) + c(C,G) = 2 + 10 = 12 \ge h(B) = 0$ (קביל).
- $h^*(A) = c(A,C) + c(C,G) = 1 + 10 = 11 \ge h(A) = 10$ (קביל).
- $h^*(S) = 1 + 1 + 10 = 12 \ge h(S) = 0$ (קביל).
מסקנה: אין שום הערכת יתר באף צומת, ולכן h קבילה לחלוטין!
✗ הוכחת חוסר עקביות (Inconsistency)
נתבונן בקשת $A \to C$ שעלותה $c(A,C) = 1$:
$$h(A) - h(C) = 10 - 5 = 5$$
אך אי-שוויון המשולש דורש $h(A) \le c(A,C) + h(C) = 1 + 5 = 6$.
מכיוון ש-$h(A) = 10 > 6$, אי-השוויון אינו מתקיים!
מסקנה: ההיוריסטיקה אינה עקבית (מונוטוניות נשברת)!
💥 מהלך הרצת החיפוש בגרף (Graph Search) צעד-אחר-צעד:
- הרחבת $S$: נוצרים $B$ עם $f(B) = g(B) + h(B) = 1 + 0 = \mathbf{1}$, ו-$A$ עם $f(A) = 1 + 10 = \mathbf{11}$. החזית: $\{B(f=1), A(f=11)\}$.
- הרחבת $B$: $B$ נשלף (הקטן ביותר). יורשו הוא $C$ במסלול התחתון: $g(C) = 1 + 2 = 3$, $f(C) = 3 + 5 = \mathbf{8}$. החזית כעת: $\{C(f=8), A(f=11)\}$.
- הרחבת $C$ (המלכודת!): $C$ נשלף (כי $8 < 11$) ומוכנס ל-Explored Set! יורשו הוא המטרה $G$ עם $g(G) = 3 + 10 = 13$, $f(G) = 13$. החזית כעת: $\{A(f=11), G(f=13)\}$.
- הרחבת $A$ (האסון): $A$ נשלף ($f=11$). יורשו הוא הצומת $C$ במסלול העליון הזול: $g(C) = 1 + 1 = \mathbf{2}$. אבל בחיפוש גרף רגיל, מאחר ש-$C$ כבר נמצא ב-Explored Set, האלגוריתם מתעלם ממנו ומסרב לפתוח אותו מחדש! הנתיב הזול נזרק לפח!
- עצירה וסיום: הצומת הבא שנשלף מהחזית הוא $G$. האלגוריתם מחזיר את המסלול הנחות $S \to B \to C \to G$ בעלות 13 במקום 12!
⚙️ 4. אלגוריתם $A^*$ הפורמלי בגרף: פסאודוקוד ומנגנון הפתיחה מחדש (Re-opening)
בספרות האקדמית של בינה מלאכותית, אלגוריתם $A^*$ בגרף מוגדר בקפדנות באמצעות שתי קבוצות צמתים מרכזיות: $\text{OPEN}$ (תור קדימויות של צמתים שנמצאו וטרם הורחבו, ממוין לפי $f(n)$ עולה) ו-$\text{CLOSE}$ (קבוצת הצמתים שכבר נשלפו והורחבו בעבר).
function ASTAR(s_0):
// s_0 is the initial state
OPEN = PriorityQueue() sorted by f(n) ascending
CLOSE = Set()
// Initialize root node
g(s_0) = 0
f(s_0) = g(s_0) + h(s_0)
parent(s_0) = null
OPEN.insert(s_0)
while not OPEN.isEmpty():
n = OPEN.extractMin() // node with lowest f(n)
if isGoal(n):
return constructPath(n) // SUCCESS: return optimal path
CLOSE.add(n)
for each successor n' of n generated by action a with cost c(n, a, n'):
new_g = g(n) + c(n, a, n')
if n' in OPEN:
if new_g < g(n'):
// Found a cheaper path to an unexpanded frontier node!
g(n') = new_g
f(n') = g(n') + h(n')
parent(n') = n
OPEN.decreaseKey(n')
else if n' in CLOSE:
if new_g < g(n'):
// CRITICAL EDGE-CASE: Found cheaper path to an already-closed node!
// This can ONLY happen if h is NOT consistent!
g(n') = new_g
f(n') = g(n') + h(n')
parent(n') = n
CLOSE.remove(n')
OPEN.insert(n') // RE-OPENING node from CLOSE to OPEN!
else:
// Brand new undiscovered state
g(n') = new_g
f(n') = g(n') + h(n')
parent(n') = n
OPEN.insert(n')
return FAILURE // No path exists to goal
הבחינו בבלוק else if n' in CLOSE: אם ההיוריסטיקה אינה עקבית (כמו בדוגמה הנגדית עם צומת $C$), ייתכן שנגלה מאוחר יותר מסלול זול יותר לצומת שכבר הורחב ונסגר!
כדי ש-$A^*$ יישאר אופטימלי במקרה כזה, הוא חייב לשלוף את $n'$ מתוך CLOSE ולהחזירו ל-OPEN.
אולם, פתיחה מחדש זו עלולה לגרום לאותו צומת להיפתח ולהיסגר שוב ושוב מספר אקספוננציאלי של פעמים במקרה הגרוע!
📜 5. הוכחה מתמטית פורמלית: למה 1 ומשפט הקבילות (Admissibility Theorem)
ההוכחה המלאה לכך שקבילות גוררת אופטימליות מבוססת על למה מתמטית מרכזית:
ניסוח הלמה: אם $h$ היוריסטיקה קבילה, אזי בכל צעד של אלגוריתם $A^*$ לפני עצירתו, קיים בתור $\text{OPEN}$ לפחות צומת אחד $n$ הנמצא על מסלול אופטימלי כלשהו מ-$s_0$ אל צומת מטרה אופטימלי $G^*$, כך שערך ה-$f$ שלו חסום על ידי העלות האופטימלית:
- יהי $P = (s_0 = v_0, v_1, v_2, \dots, v_k = G^*)$ מסלול אופטימלי מפתח מצב ההתחלה אל מטרה $G^*$, שעלותו הכוללת היא $C^*$.
- בתחילת הריצה $s_0 \in \text{OPEN}$, ולכן עבור $n = s_0$: $$f(s_0) = g(s_0) + h(s_0) = 0 + h(s_0) \le h^*(s_0) = C^*$$ (נובע ישירות מקבילות $h$).
- בכל צעד שבו $A^*$ שולף צומת מ-$\text{OPEN}$ ומכניסו ל-$\text{CLOSE}$, אם הצומת הוא על המסלול $P$, לפחות עוקב אחד שלו על המסלול $P$ מוכנס ל-$\text{OPEN}$ (או שכבר נמצא בו).
- לפיכך, כל עוד היעד האופטימלי טרם נשלף, תמיד קיים צומת $n \in P$ הנמצא ב-$\text{OPEN}$, כך שכל אבותיו על המסלול $P$ כבר הורחבו ונמצאים ב-$\text{CLOSE}$.
- מאחר ש-$n$ הגיע דרך המסלול האופטימלי $P$, העלות שנצברה אליו היא אופטימלית במדויק: $g(n) = g^*(n)$.
- מהגדרת הקבילות של $h$, מתקיים $h(n) \le h^*(n)$. נחבר את שני האגפים: $$f(n) = g(n) + h(n) = g^*(n) + h(n) \le g^*(n) + h^*(n) = C^*$$ מש"ל למה 1!
הוכחה בשלילה: נניח בשלילה ש-$A^*$ עצר והחזיר צומת מטרה סאב-אופטימלי $G_2$ שעלותו $g(G_2) > C^*$.
ברגע שליפת $G_2$ מתוך $\text{OPEN}$, מכיוון שהוא צומת מטרה מתקיים $h(G_2) = 0$, ולכן:
$$f(G_2) = g(G_2) + h(G_2) = g(G_2) > C^*$$
אולם לפי למה 1, באותו רגע ממש היה קיים ב-$\text{OPEN}$ צומת $n$ הנמצא על המסלול האופטימלי כך ש-$f(n) \le C^*$.
מכאן נובעת שרשרת אי-השוויונים:
$$f(n) \le C^* < f(G_2)$$
היות ש-$\text{OPEN}$ הוא תור קדימויות השולף תמיד את הצומת בעל ערך $f$ המינימלי, האלגוריתם היה חייב לשלוף את $n$ לפני שישלוף אי-פעם את $G_2$! סתירה להנחה ש-$G_2$ נשלף.
לפיכך, $A^*$ לעולם לא ישלוף מטרה סאב-אופטימלית. $A^*$ מחזיר תמיד פתרון אופטימלי!
💎 6. משפט העקביות / מונוטוניות: מדוע לעולם לא פותחים מחדש מ-CLOSE?
כאשר ההיוריסטיקה $h(n)$ מקיימת את אי-שוויון המשולש ($h(n) \le c(n, a, n') + h(n')$), מתרחשת תופעה אלגוריתמית בעלת חשיבות עליונה:
לכל צומת $n$ ועוקב $n'$: $$f(n') = g(n') + h(n') = g(n) + c(n, a, n') + h(n')$$ מאי-שוויון המשולש נובע $c(n, a, n') + h(n') \ge h(n)$, ולכן: $$f(n') \ge g(n) + h(n) = f(n)$$ ערכי $f$ לאורך כל ענף הם מונוטוניים אי-יורדים!
מסקנה ישירה: צמתים נשלפים מ-$\text{OPEN}$ בסדר שאינו יורד של ערכי $f$. ברגע שצומת $n$ נשלף מ-$\text{OPEN}$ ונכנס ל-$\text{CLOSE}$, מובטח שנמצא המסלול הקצר והזול ביותר אליו ($g(n) = g^*(n)$)! אין שום צורך לפתוח מחדש צמתים מ-CLOSE, וכל צומת מורחב בדיוק פעם אחת!
👑 7. משפט השליטה (Dominance) ושילוב היוריסטיקות ($\max$)
כיצד נשווה בין שתי היוריסטיקות קבילות שונות, ואיך נוכל להפיק את המרב ממספר היוריסטיקות זמינות? ניתוח הדומיננטיות המדויק:
אם $h_1(n)$ ו-$h_2(n)$ שתיהן היוריסטיקות קבילות, ולכל צומת $n$ מתקיים: $$h_2(n) \ge h_1(n)$$ אזי נאמר ש-$h_2$ שולטת ב-$h_1$ ($h_2$ dominates $h_1$).
אם יש לנו $k$ היוריסטיקות קבילות שונות $h_1, h_2, \dots, h_k$ (שאף אחת מהן אינה שולטת באחרת בכל המרחב), נגדיר היוריסטיקה חדשה: $$\hat{h}(n) = \max\{h_1(n), h_2(n), \dots, h_k(n)\}$$
📊 8. השוואת תכונות וסיבוכיות של אלגוריתמי חיפוש (עיוור ומיודע)
מתוך דוח המחקר המקיף: השוואה רב-ממדית של ארבעת המדדים האלגוריתמיים המרכזיים ומקרי הקצה שמופיעים בשאלות המבחן.
| אלגוריתם | שלמות (Completeness) | אופטימליות (Optimality) | סיבוכיות זמן | סיבוכיות מקום (זיכרון) |
|---|---|---|---|---|
| DFS (עומק) | לא (אם יש מעגלים/אינסוף) | לא מובטחת | O(bᵐ) | O(bm) - לינארי! |
| BFS (רוחב) | כן (אם b סופי) | כן (אם עלות קשתות אחידה) | O(bᵈ) | O(bᵈ) - פיצוץ RAM! |
| IDS (מעמיק איטרטיבי) | כן | כן (כמו BFS) | O(bᵈ) | O(bd) - לינארי! |
| UCS (עלות אחידה) | כן (אם c(e) ≥ ε > 0) | כן (תמיד אופטימלי!) | O(b¹⁺⌊C*/ε⌋) | O(b¹⁺⌊C*/ε⌋) - מעריכי |
| A* (חיפוש עץ) | כן | מותנה בקבילות (Admissible) | תלוי באיכות היוריסטיקה | מעריכי (שומר חזית) |
| A* (חיפוש גרף) | כן | מותנה בעקביות (Consistent) | O(bᵈ) במקרה הגרוע | מעריכי (חזית + Explored) |
פונקציית ההערכה מתנוונת ל-$f(n) = g(n) + 0 = g(n)$. האלגוריתם הופך במדויק ל-חיפוש בעלות אחידה (UCS)!
מרחבים רציפים עוברים דיסקרטיזציה שיטתית (חלוקה לתאים, מפות דרכים הסתברותיות PRM או גרפי נראות), ואז $A^*$ מוחל עליהם באופטימליות מלאה.
BFS שומר על שלמות (תלוי רק בעומק), אך UCS עלול להיתקע בלולאה אינסופית אם לא מתקיים התנאי $c(e) \ge \epsilon > 0$.
אינו קביל! צריח גומא 10 משבצות בצעד יחיד בעלות 1, בעוד שמרחק מנהטן יעריך 10 (הערכת יתר חמורה הפוסלת אופטימליות).
אלגוריתם IDS מבצע $1+2+...+n$ פיתוחים ומפגין סיבוכיות ריבועית $O(n^2)$, לעומת DFS שמגיע ליעד בזמן לינארי מהיר $O(n)$.
התנסות מעשית: מעבדת אי-שוויון המשולש וכשל עקביות ב-$A^*$
בסימולציה אינטראקטיבית זו תוכלו לעקוב שלב אחר שלב אחר ריצת האלגוריתם על גרף הדוגמה הנגדית, לראות כיצד צומת C ננעל ב-Closed Set, לשנות את היוריסטיקת הצומת A בזמן אמת, ולהשוות בין חיפוש גרף לחיפוש עץ.
טופולוגיית מרחב מצבים והמרות ייצוג (Reformulation)
💡 כוחו של ייצוג הבעיה (Data Representation)
ברוכים הבאים לאחת התובנות המרתקות והעמוקות ביותר בכל מדעי המחשב והבינה המלאכותית! בפרק הקודם למדנו כיצד להריץ אלגוריתמי חיפוש עיוורים ומיודעים: בונים תור, מרחיבים צמתים, מחזיקים רשימת סגורים, ונלחמים בפיצוץ האקספוננציאלי. אך כאן נשאלת שאלה פילוסופית עמוקה: האם אנו באמת חייבים "לחפש"? נלמד דרך שאלת המופת של ראסל ונורוויג (שאלה 3.15) כיצד הבנה טופולוגית של מרחב הבעיה מאפשרת לבצע חיפוש דו-כיווני עם מקדם הסתעפות פלאי של $b=1$, ואיך רפורמולציה (ניסוח מחדש) בבסיס בינארי מעלימה לחלוטין את החיפוש ומספקת פתרון ישיר ב-$O(1)$!
🌳 1. הגדרת הבעיה: מרחב המספרים השלמים (Russell & Norvig 3.15)
נתונה בעיית חיפוש מתמטית פשוטה לכאורה:
📋 2. ניתוח מעקב יבש (Dry Trace) של אלגוריתמי החיפוש עבור יעד $G = 11$
בבחינות נדרש לפרט במדויק את סדר הצמתים המפותחים על פי האלגוריתמים השונים. נפרק כל אחד מהם:
BFS סורק את העץ שכבה אחר שכבה (רמות עומק מהשורש), משמאל לימין:
- • רמה 0 (עומק 0): [1]
- • רמה 1 (עומק 1): [2, 3]
- • רמה 2 (עומק 2): [4, 5, 6, 7]
- • רמה 3 (עומק 3): [8, 9, 10, 11] ← עצירה מידית במטרה!
DLS צולל לעומק הענף השמאלי עד למגבלת העומק 3, ואז מבצע נסיגה (Backtrack):
- ירידה שמאלה: $1 \to 2 \to 4 \to 8$ (הגענו לעומק 3, נסוגים חזרה ל-4).
- פנייה ליורש הימני של 4: הצומת 9 (עומק 3, נסוגים חזרה ל-2).
- פנייה ליורש הימני של 2: הצומת 5 (עומק 2).
- ירידה שמאלה מ-5: הצומת 10 (עומק 3, נסוגים חזרה ל-5).
- פנייה ליורש הימני של 5: הצומת 11 ← הגענו למטרה!
IDS מריץ סדרת חיפושי DLS מוגבלי עומק הולכים וגדלים מ-$l = 0$ ועד למציאת המטרה:
- • איטרציה $l=0$: 1
- • איטרציה $l=1$: 1, 2, 3
- • איטרציה $l=2$: 1, 2, 4, 5, 3, 6, 7
- • איטרציה $l=3$: 1, 2, 4, 8, 9, 5, 10, 11 (עצירה במטרה!)
↔️ 3. החיפוש הדו-כיווני (Bidirectional Search): עקרון הפעולה הכללי ומקדם ההסתעפות $b=1$ לאחור
בפרק הקודם פגשנו את אלגוריתמי החיפוש החד-כיווניים (הסורקים מההתחלה ליעד). חיפוש דו-כיווני (Bidirectional Search) מציע תפיסה מהפכנית: להריץ שני חיפושים מקבילים בו-זמנית – אחד קדימה ממצב ההתחלה $s_0$, והשני אחורה מצב/י המטרה $G$, עד שהחזיתות שלהם נפגשות באמצע!
כדי לחפש אחורה מהמטרה, חייבת להתקיים פונקציית קודמים יעילה $Succ^{-1}(s)$: $$\forall a: s \xrightarrow{a} s' \iff s \in Succ^{-1}(s')$$ אם הפעולות אינן הפיכות בקלות, חיפוש לאחור הופך לבלתי אפשרי.
האלגוריתם בודק בכל צעד האם הצומת שנשלף בחזית האחת כבר קיים בחזית או בקבוצת הסגורים של הכיוון הנגדי: $$\text{Frontier}_F \cap \text{Frontier}_B \neq \emptyset \quad \lor \quad n \in \text{Explored}_{\text{Opposite}}$$
במקום חיפוש עמוק אחד בעומק $d$ בעל סיבוכיות $O(b^d)$, אנו מחפשים בשני חצאי עצים עד לעומק $d/2$:
$$\text{Time \& Space} = O(b^{d/2} + b^{d/2}) = O(2 \cdot b^{d/2}) \ll O(b^d)$$
דוגמה מספרית: עבור מקדם הסתעפות $b = 10$ ועומק מטרה $d = 8$:
• חיפוש חד-כיווני מייצר: $10^8 = \mathbf{100,000,000}$ צמתים.
• חיפוש דו-כיווני מייצר: $2 \times 10^{8/2} = 2 \times 10^4 = \mathbf{20,000}$ צמתים בלבד!
קיצוץ של פי 5,000 במספר הצמתים ובזיכרון ה-RAM!
בבעיית המספרים השלמים שלנו, הקסם הדו-כיווני מתעצם עוד יותר: בעוד שקדימה מקדם ההסתעפות הוא $b_{\text{forward}} = 2$ (לכל $k$ יש $2k$ ו-$2k+1$), הרי שלאחור מתרחש נס מתמטי:
- אם $n = 11$ (אי-זוגי): $11 // 2 = 5$ (נוצר מ-$2 \times 5 + 1$).
- אם $n = 10$ (זוגי): $10 // 2 = 5$ (נוצר מ-$2 \times 5$).
ההשלכה העצומה: חיפוש אחורנית מהמטרה לעבר השורש 1 אינו מתפצל כלל! זהו מסלול ישר ודטרמיניסטי של חלוקה ב-2: $$11 \xrightarrow{//2} 5 \xrightarrow{//2} 2 \xrightarrow{//2} 1$$ החיפוש הדו-כיווני מוצא את הפתרון באפס חיפושי סרק ובסיבוכיות זמן אופטימלית של: $$O(\log n) = O(d)$$
⚡ 4. שיא העומק: רפורמולציה (Reformulation) דרך ייצוג בינארי ישיר
כאן מתגלה הגאונות האמיתית של מהנדס בינה מלאכותית: החלפת ייצוג הבעיה (Change of Representation) מייתרת לחלוטין את פעולת החיפוש!
• קוראים ביט ראשון '0': $1 \times 2 = \mathbf{2}$ (פנייה שמאלה).
• קוראים ביט שני '1': $2 \times 2 + 1 = \mathbf{5}$ (פנייה ימינה).
• קוראים ביט שלישי '1': $5 \times 2 + 1 = \mathbf{11}$ (פנייה ימינה).
הגענו ישירות למטרה 11 באפס חיפושים! זמן ריצה: $O(\log n)$ (אורך הייצוג הבינארי).
לפני שרצים לכתוב אלגוריתם חיפוש מורכב וזולל משאבים (כמו A* או BFS), מהנדס AI חכם תמיד שואל את עצמו: האם המרחב מאפשר ניסוח מחדש (Reformulation)? כאשר מבינים את המתמטיקה של הבעיה, פעמים רבות ניתן לעקוף את "קללת הממדיות" ולהגיע לפתרון מיידי, כפי שהוכחנו כאן!
התנסות מעשית: מפענח המבנים הבינאריים וסייר העץ האינסופי
בסימולציה הבאה תוכלו להזין כל מספר מטרה שתרצו (קטן או עצום!), לצפות בעץ החיפוש מתפתח שלב אחר שלב באלגוריתמי BFS, DLS, ו-IDS, לראות את כוחו של החיפוש הדו-כיווני ($b=1$), ולחזות באנימציית הפיענוח הבינארי המנווטת ישירות למטרה ללא שגיאות.
מידול בעיות וקבילות: בעיית ששת החצים ומשחק לוח $8\times 8$
💡 המלכודת של "נראה כמו היוריסטיקה טובה"
אחד האתגרים הגדולים בבחינות ובפיתוח מערכות AI הוא תכנון פונקציה היוריסטית $h(n)$ לבעיה חדשה שמעולם לא פגשתם. האינסטינקט הראשוני שלנו תמיד אומר: "בוא נספור כמה אלמנטים נמצאים במצב לא נכון, או נסכום את המרחקים". אך ביחידה זו נלמד דרך שתי בעיות בחינה קלאסיות מדוע האינטואיציה הזו שגויה ומטעה! נכיר את בעיית ששת החצים ונבין מדוע מרחק המינג אינו קביל, וננתח לעומק את משחק לוח $8\times 8$, שבו כל פעולה מייצרת אפקט אדווה (Ripple Effect) המשנה בו-זמנית את מצבן של 4 שכנות סביבה!
🏹 1. בעיית ששת החצים (The Six Arrows Problem)
בבעיה זו נתונים שישה חצים מסודרים בשורה אופקית.
⚠️ ניתוח היוריסטיקה מוצעת: מרחק המינג (ספירת חצים שגויים)
נניח שהוצעה פונקציה היוריסטית $h(n)$ הסופרת את מספר החצים שאינם תואמים את תבנית המטרה.
האם היוריסטיקה זו קבילה (Admissible)?
תשובה: לא! ההיוריסטיקה אינה קבילה בעליל.
נניח שהמצב הנוכחי שונה מהמטרה אך ורק בשני חצים סמוכים (למשל, חצים 2 ו-3 שגויים, וכל השאר נכונים).
• היוריסטיקת המינג תספור 2 שגיאות ותחזיר: $h(n) = \mathbf{2}$.
• אולם, מאחר ששני החצים הללו צמודים, פעולת היפוך אחת ויחידה על הזוג (2-3) בעלות של $1$ מתקנת את שני החצים ומביאה אותנו ישירות למטרה!
• העלות האמיתית המינימלית היא: $h^*(n) = \mathbf{1}$.
• מכיוון ש-$h(n) = 2 > h^*(n) = 1$, ההיוריסטיקה מעריכה הערכת יתר (Overestimation) ושוברת את תנאי הקבילות!
במרחב מצבים זעיר של 64 מצבים עם $b=5$, שימוש ב-$A^*$ עם היוריסטיקה מורכבת הוא שגיאת תכנון מערכתית (Over-engineering). אלגוריתם חיפוש לרוחב (BFS) פשוט יסרוק את כל המרחב תוך אלפית השנייה, ימצא את הפתרון האופטימלי בוודאות, ויחסוך את כל תקורת החישוב של תורי עדיפויות וסיכון לשגיאות בהיוריסטיקה!
♟️ 2. משחק לוח משבצות $8\times 8$ עם היפוך צבעים (Exam Passage 2)
שאלת מבחן קלאסית ומעמיקה במיוחד: נתון לוח משובץ בגודל $8\times 8$ (64 משבצות), שבו כל משבצת צבועה בשחור (1) או בלבן (0).
מצב שבו לכל משבצת בלוח יש לפחות 2 משבצות שכנות (למעלה, למטה, ימין, שמאל) בעלות צבע זהה לצבע שלה!
הפיכת הצבע של משבצת בודדת $(i,j)$ על גבי הלוח:
- • היפוך מלבן לשחור ($W \to B$): עלות = מספר השורה $i \in \{1,\dots,8\}$.
- • היפוך משחור ללבן ($B \to W$): עלות = מספר העמודה $j \in \{1,\dots,8\}$.
🏆 הוכחה מתמטית ריגורוזית: קיום צמתי מטרה בעומק 32 ומטה!
טענה (מופיעה בבחינות): מובטח כי מכל מצב התחלתי שרירותי על הלוח, קיים מצב מטרה חוקי בעומק של לכל היותר 32 צעדים בעץ החיפוש!
- למשבצת פינתית יש בדיוק 2 שכנות, ושתיהן באותו הצבע $\implies 2 \ge 2$ (עומד בתנאי!).
- למשבצת על השפה יש 3 שכנות באותו הצבע $\implies 3 \ge 2$ (עומד בתנאי!).
- למשבצת פנימית יש 4 שכנות באותו הצבע $\implies 4 \ge 2$ (עומד בתנאי!).
נסמן ב-$W$ את מספר המשבצות הלבנות ובו-$B$ את מספר המשבצות השחורות בלוח ההתחלתי. מאחר שבסך הכל יש 64 משבצות: $$W + B = 64 \implies \min(W, B) \le 32$$
נבחר להפוך את צבען של כל משבצות המיעוט אל צבע הרוב. מאחר שמספר משבצות המיעוט אינו עולה על 32, נדרשות לכל היותר 32 פעולות היפוך בלבד כדי להגיע למצב שבו כל הלוח אחיד בצבעו!
💥 ניתוח שאלת המבחן: היוריסטיקת סכימת השכנות הלקויות ואפקט האדווה
מוצעת ההיוריסטיקה הבאה: סוכמים לכל משבצת $(i,j)$ את הפער $(2 - x_{ij})$ במידה ויש לה פחות מ-2 שכנות באותו צבע:
האם היוריסטיקה זו קבילה (Admissible)?
תשובה חד-משמעית: לא! ההיוריסטיקה אינה קבילה.
נניח לוח שבו כל המשבצות שחורות, למעט משבצת לבנה בודדת ומבודדת בשורה 1, עמודה 2:
- עבור המשבצת הלבנה הזו, יש $x = 0$ שכנות לבנות, ולכן היא תורמת להיוריסטיקה: $2 - 0 = \mathbf{2}$.
- בנוסף, עבור כל אחת מ-4 השכנות השחורות שלה, הימצאות המשבצת הלבנה גרעה מהן שכן שחור. אם לאחת השכנות הללו יש רק שכן שחור אחד נוסף ($x=1$), היא תתרום להיוריסטיקה: $2 - 1 = \mathbf{1}$.
- לפיכך, ערך ההיוריסטיקה המצטבר עבור הלוח יהיה: $h(n) \ge 2 + 1 = \mathbf{3}$.
בפעולה בודדת אחת של היפוך המשבצת הלבנה לשחורה ($W \to B$) בשורה $1$, עלות הצעד היא בדיוק 1 (מספר השורה)! היפוך זה פותר באחת את הבעיה עבור המשבצת עצמה ומשפר את תנאי השכנות של כל 4 שכנותיה במקביל (כל הלוח הופך לשחור אחיד וחוקי!).
לכן העלות האמיתית היא: $h^*(n) = \mathbf{1}$.
מכיוון ש-$h(n) \ge 3 > h^*(n) = 1$, ההיוריסטיקה מעריכה הערכת יתר (Overestimation) ולכן אינה קבילה!
התנסות מעשית: מעבדת היוריסטיקות (Heuristics Lab) ולוח $8\times 8$
בסימולציה זו תוכלו לשחק ישירות על לוח ה-$8\times 8$, להפוך צבעי משבצות בקליק, לחזות באנימציית "אדוות ההשפעה" (Ripple Effect) על 4 השכנות, לבחון את עלויות הפעולה המשתנות לפי שורה/עמודה, וללחוץ על כפתור "טען דוגמה נגדית" כדי לראות במו עיניכם מתי $h(n) > h^*(n)$ והקבילות קורסת!
מעקב וניתוח אלגוריתמי בגרף מבחן ובחינת עקביות
💡 איך לבצע מעקב יבש אלגוריתמי בדיוק מוחלט
שאלות מעקב יבש (Traces) על גרף מרובה צמתים הן שאלות "מתנה" בבחינה – אך רק אם עובדים בשיטה קרה ומסודרת ללא קיצורי דרך! ביחידה זו ננתח לפרטי פרטים את גרף המבחן המלא בן 10 הצמתים (מתוך Passage 8). נריץ עליו בזה אחר זה את ארבעת אלגוריתמי החיפוש המרכזיים: BFS, UCS, Greedy Best-First, ו-$A^*$. נראה בדיוק מי מוכנס לתור, מי נשלף ראשון, כיצד שוברים שוויונות אלפביתית, ולבסוף נוכיח מתמטית מדוע ההיוריסטיקה הנתונה בגרף היא קבילה לחלוטין אך אינה עקבית!
🗺️ 1. נתוני גרף המבחן (Exam Graph Specification)
נתון גרף מכוון הכולל צומת התחלה $S$, שני צמתי מטרה $G_1, G_2$, וערכי היוריסטיקה $h(n)$ הרשומים לצד כל צומת:
⚡ 2. פירוק מעקב מלא צעד-אחר-צעד (Four Algorithms Dry Trace)
BFS מפתח צמתים לפי סדר הגעתם לתור (עומק עץ), ואינו מתחשב במשקלי הקשתות או בהיוריסטיקה:
- הרחבת $S$: יורשיו מתווספים לפי סדר אלפביתי. חזית: $\{A, B, C\}$.
- הרחבת $A$: יורשיו $\{E, H\}$. חזית כעת: $\{B, C, E, H\}$.
- הרחבת $B$: יורשו $\{D\}$. חזית כעת: $\{C, E, H, D\}$.
- הרחבת $C$: יורשו $\{G_2\}$. חזית כעת: $\{E, H, D, G_2\}$.
- הרחבת $E$: יורשו $H$ כבר בחזית. חזית כעת: $\{H, D, G_2\}$.
- הרחבת $H$: אין יורשים חוקיים. חזית כעת: $\{D, G_2\}$.
- הרחבת $D$: יורשו $\{G_1\}$. חזית כעת: $\{G_2, G_1\}$.
- הרחבת $G_2$: נשלף צומת מטרה! עצירה וסיום.
UCS ממיין את החזית בקפדנות לפי עלות המסלול המצטברת $g(n)$ מהשורש:
- הרחבת $S$ ($g=0$): יורשים $B(g=1), A(g=3), C(g=5)$. חזית: $\{B(1), A(3), C(5)\}$.
- הרחבת $B$ ($g=1$): יורש $D$ עם $g = 1 + 4 = 5$. חזית: $\{A(3), C(5), D(5)\}$.
- הרחבת $A$ ($g=3$): יורשים $E(g=3+7=10), H(g=3+10=13)$. חזית: $\{C(5), D(5), E(10), H(13)\}$.
- הרחבת $C$ ($g=5$): יורש $G_2$ עם $g = 5 + 11 = 16$. חזית: $\{D(5), E(10), H(13), G_2(16)\}$.
- הרחבת $D$ ($g=5$): יורש $G_1$ עם $g = 5 + 5 = 10$. חזית: $\{E(10), G_1(10), H(13), G_2(16)\}$.
- הרחבת $E$ ($g=10$): מוצא מסלול זול יותר ל-$H$ ($g = 10 + 2 = 12$). מעדכן את $H$. חזית: $\{G_1(10), H(12), G_2(16)\}$.
- הרחבת $G_1$ ($g=10$): נשלף צומת מטרה! עצירה וסיום.
החיפוש החמדן מסתמך אך ורק על הציון היוריסטי $h(n)$ ומתעלם מכל עלות ששולמה בעבר:
- הרחבת $S$ ($h=8$): יורשים $B(h=1), C(h=7), A(h=9)$. חזית: $\{B(1), C(7), A(9)\}$.
- הרחבת $B$ ($h=1$): יורש $D(h=4)$. חזית כעת: $\{D(4), C(7), A(9)\}$.
- הרחבת $D$ ($h=4$): יורש $G_1(h=0)$. חזית כעת: $\{G_1(0), C(7), A(9)\}$.
- הרחבת $G_1$ ($h=0$): נשלף צומת מטרה! עצירה וסיום.
$A^*$ משקלל את העבר עם העתיד וממיין לפי ערך $f(n)$:
- הרחבת $S$ ($f = 0 + 8 = 8$): יורשים:
• $B: g=1, h=1 \implies f(B) = 1 + 1 = \mathbf{2}$חזית: $\{B(f=2), A(f=12), C(f=12)\}$.
• $A: g=3, h=9 \implies f(A) = 3 + 9 = \mathbf{12}$
• $C: g=5, h=7 \implies f(C) = 5 + 7 = \mathbf{12}$ - הרחבת $B$ ($f=2$): יורש $D$ עם $g=1+4=5, h=4 \implies f(D) = 5 + 4 = \mathbf{9}$.
חזית כעת: $\{D(f=9), A(f=12), C(f=12)\}$. - הרחבת $D$ ($f=9$): יורש $G_1$ עם $g=5+5=10, h=0 \implies f(G_1) = 10 + 0 = \mathbf{10}$.
חזית כעת: $\{G_1(f=10), A(f=12), C(f=12)\}$. - הרחבת $G_1$ ($f=10$): נשלף צומת מטרה! עצירה וסיום.
⚖️ 3. הוכחה מתמטית: האם ההיוריסטיקה בגרף קבילה ועקבית?
- $h^*(G_1) = 0 \ge h(G_1) = 0$ (מתקיים).
- $h^*(G_2) = 0 \ge h(G_2) = 0$ (מתקיים).
- $h^*(D) = 5 \ge h(D) = 4$ (מתקיים).
- $h^*(B) = 4 + 5 = 9 \ge h(B) = 1$ (מתקיים).
- $h^*(C) = 11 \ge h(C) = 7$ (מתקיים).
- $h^*(S) = 1 + 4 + 5 = 10 \ge h(S) = 8$ (מתקיים).
-
ומה לגבי צמתים $A, E, H$?
מצמתים אלו אין שום מסלול אפשרי אל אף אחד מצמתי המטרה! לפיכך, העלות האמיתית להגעה למטרה היא אינסופית: $$h^*(A) = h^*(E) = h^*(H) = \infty$$ ומכיוון ש-$\infty \ge h(n)$, התנאי מתקיים גם עבורם!
נבדוק את אי-שוויון המשולש עבור הקשת $S \to B$ שעלותה $c(S,B) = 1$:
ההפרש בהערכה ההיוריסטית הוא: $$h(S) - h(B) = 8 - 1 = 7 > c(S,B) = 1$$ ההערכה צונחת ב-7 יחידות לאורך קשת שעלותה 1 בלבד!
🏃 4. חיפוש חמדן פורמלי (Greedy Best-First Search): פסאודוקוד ומגבלות תיאורטיות
אלגוריתם חיפוש חמדן (Greedy Best-First Search) מונחה על ידי עקרון פשוט: בכל שלב, הרחב את הצומת שנראה הקרוב ביותר למטרה לפי פונקציית ההיוריסטיקה $h(n)$, תוך התעלמות מוחלטת מעלות המסלול שנצברה בעבר: $$f(n) = h(n)$$
function Best-first(init):
OPEN = PriorityQueue() sorted by h(n) ascending
CLOSE = Set()
OPEN.insert(init)
while not OPEN.isEmpty():
n = OPEN.extractMin() // node with lowest h(n)
if isGoal(n):
return constructPath(n) // Return solution path
CLOSE.add(n)
for each successor n' of n:
// Loop prevention check
if n' not in OPEN and n' not in CLOSE:
parent(n') = n
OPEN.insert(n')
return FAILURE⚖️ 5. אלגוריתם $A^*$ ממושקל (Weighted A*) וחיפוש $\epsilon$-קביל (Bounded Suboptimality)
לעיתים קרובות בעולם האמיתי, אנו מוכנים להתפשר מעט על שלמות האופטימליות (למשל, להסתפק במסלול היקר ב-10% מהאופטימלי) בתמורה לקיצוץ אדיר של 95% מזמן החישוב והזיכרון! לשם כך פותח אלגוריתם $A^*$ ממושקל (Weighted A*), המשתמש בפונקציית הערכה פרמטרית עם משקל $w \in [0, 1]$:
$$f_0(n) = g(n)$$ אופטימליות מוחלטת, עיוור לעתיד, סורק צמתים רבים ואיטי.
$$f_{0.5}(n) = 0.5(g(n) + h(n))$$ איזון מושלם בין עבר לעתיד. קביל ואופטימלי (שקול ל-$g+h$).
$$f_1(n) = h(n)$$ מהיר ותוקפני ביותר, אך מאבד כל הבטחה לאופטימליות.
- עבור $w \le 0.5$: אם $h$ קבילה, האלגוריתם קביל ואופטימלי לחלוטין (כי המשקל היחסי הניתן ל-$h$ אינו עולה על משקל $g$).
- עבור $w > 0.5$: האלגוריתם מאבד אופטימליות מוחלטת, אך מקיים תכונה מופלאה הנקראת $\epsilon$-קבילות ($\epsilon$-Admissibility): $$Cost(\text{Solution}) \le (1 + \epsilon) \cdot C^*, \qquad \text{where } \epsilon = \frac{w}{1 - w} - 1 = \frac{2w - 1}{1 - w}$$
- דוגמה מספרית מהמבחן: אם בוחרים $w = 0.6$: $$\epsilon = \frac{2(0.6) - 1}{1 - 0.6} = \frac{0.2}{0.4} = 0.5$$ האלגוריתם מתחייב למצוא פתרון שעלותו לא תעלה על $1.5 \cdot C^*$ (לא יותר מ-50% מעל האופטימום), תוך הפחתת כמות הצמתים המפותחים במאות אחוזים!
🎛️ 6. שקלול דינמי (Dynamic Weighting): מניעת הסתבכות בענפים עמוקים
ב-Weighted A* קבוע עם $w > 0.5$, אם ההיוריסטיקה שוגה בעומק העץ, האלגוריתם עלול "להיתקע" בענף שגוי ועמוק מבלי לחזור אחורה. כדי לפתור זאת, הוצע מנגנון שקלול דינמי (Dynamic Weighting), שבו משקל ההיוריסטיקה משתנה כפונקציה של עומק הצומת $d(n)$:
- $d(n)$: עומק הצומת הנוכחי מהשורש.
- $N$: הערכה לחסם עליון על עומק פתרון המטרה האופטימלי ($d(G^*) \le N$).
- $\epsilon \ge 0$: מקדם עודף משקל היוריסטי.
פונקציית ההערכה הופכת ל-$g(n) + (1+\epsilon)h(n)$. האלגוריתם מתנהג בחמדנות יתרה וטס קדימה במהירות עצומה!
המשקל העודף מתאפס, והפונקציה מתכנסת חזרה ל-$f(n) = g(n) + h(n)$. האלגוריתם חוזר להיות $A^*$ קלאסי ומבטיח דיוק מרבי ליד היעד!
🔄 7. אלגוריתם מעמיק איטרטיבי מיודע ($IDA^*$ - Iterative Deepening A*)
החיסרון הקטלני של $A^*$ בעולם האמיתי אינו זמן הריצה – אלא צוואר בקבוק הזיכרון (RAM): שמירת כל הצמתים שנוצרו ברשימת OPEN גוזלת זיכרון מעריכי $O(b^d)$ שמפיל שרתים תוך שניות. אלגוריתם $IDA^*$ (Iterative Deepening A*) מציג את השילוב המנצח: יעילות זיכרון לינארית $O(b \cdot d)$ כמו של DFS, יחד עם אופטימליות מלאה של $A^*$!
בניגוד ל-IDS עיוור המגביל את עומק העץ ($l = 0, 1, 2 \dots$), אלגוריתם $IDA^*$ קובע חסם סף על ערך ה-$f$ (Threshold Bound):
- איטרציה ראשונה: החסם נקבע להיות ההיוריסטיקה של השורש: $\text{bound} = h(s_0)$.
- מהלך האיטרציה: מריצים חיפוש DFS מוגבל סף (הנקרא
DFS-C). כל ענף שבו $f(n) > \text{bound}$ נגזם מיד ואינו מפותח! - הקביעה הגאונית של הסף הבא: אם היעד לא נמצא, הסף הבא נקבע להיות הערך המינימלי מבין כל ערכי ה-$f$ של הצמתים שנגזמו באיטרציה הנוכחית! (ולא סתם $\text{bound} + 1$).
function IDA_star(root):
bound = h(root)
while true:
(status, val) = DFS_C(root, 0, bound)
if status == FOUND:
return val // Optimal solution path found!
if val == INFINITY:
return FAILURE // Exhausted space without reaching goal
bound = val // Advance threshold to smallest exceeded f-value
function DFS_C(n, g, bound):
f = g + h(n)
if f > bound:
return (NOT_FOUND, f) // Pruned by threshold: report exceeded f
if isGoal(n):
return (FOUND, constructPath(n))
min_cutoff = INFINITY
for each successor n' of n with step cost c(n, n'):
(status, val) = DFS_C(n', g + c(n, n'), bound)
if status == FOUND:
return (FOUND, val)
if val < min_cutoff:
min_cutoff = val // Track smallest f exceeding current bound
return (NOT_FOUND, min_cutoff)8 אלגוריתמי חיפוש מוגבלי-זיכרון: $RBFS$ ו-$SMA^*$ (Memory-Bounded Heuristic Search)
מעבר ל-$IDA^*$, הספר (Russell & Norvig, פרק 3) מציג שני אלגוריתמים בולטים שמטרתם להתגבר על מגבלת הזיכרון המעריכית של $A^*$ תוך שמירה על יתרונות היוריסטיים:
אלגוריתם רקורסיבי שמחקה את התנהגותו של $A^*$ הסטנדרטי אך צורך זיכרון לינארי בלבד $O(b \cdot d)$.
- מנגנון ה-$f\_limit$: האלגוריתם עוקב אחר ערך ה-$f$ של האלטרנטיבה הטובה ביותר השנייה הזמינה לאבותיו של הצומת הנוכחי.
- נסיגה לאחור וגיבוי ערכים (Backing up): כאשר כל היורשים של הצומת הנוכחי חורגים מה-$f\_limit$, האלגוריתם נסוג לאחור, אך שומר בצומת האב את ערך ה-$f$ של היורש הטוב ביותר שנשכח!
- יתרון ואופטימליות: מוצא מסלול אופטימלי אם $h$ קבילה.
- חיסרון: "תזזיתיות" (Thrashing) – פיתוח מחדש חוזר ונשנה של צמתים כאשר ערכי ה-$f$ של ענפים מתחרים קרובים זה לזה.
מנצל במלואו את כל הזיכרון הפנוי בשרת (מגבלה של $M$ צמתים ב-RAM) ולא קילובייט פחות.
- פעולה בתוך מגבלת הזיכרון: פועל בדיוק כמו $A^*$ כל עוד הזיכרון אינו מלא.
- מחיקת העלה הגרוע ביותר (Drop Worst): כאשר הזיכרון מתמלא, האלגוריתם מוחק מתור העדיפויות את העלה בעל ערך ה-$f$ הגבוה ביותר (הכי פחות מבטיח).
- גיבוי ערך לתוך האב (Backed-up f-cost): לפני המחיקה, ערך ה-$f$ של הבן שנמחק נרשם בצומת האב שלו! אם בעתיד כל שאר המסלולים יתבררו כגרועים עוד יותר, האב יוכל לשחזר ולפתח מחדש את הבן שנמחק.
- שלמות ואופטימליות: שלם אם עומק הפתרון $d \le M$. אופטימלי אם המסלול האופטימלי כולו נכנס ב-$M$ צמתים.
| אלגוריתם | סיבוכיות זיכרון | שלמות (Completeness) | אופטימליות ($h$ קבילה) | עומס פיתוח חוזר (Re-expansion) |
|---|---|---|---|---|
| $A^*$ (סטנדרטי) | $O(b^d)$ (מעריכי קורס!) | כן | כן | אפס (אם $h$ עקבית) |
| $IDA^*$ | $O(b \cdot d)$ (לינארי) | כן | כן | בינוני עד גבוה (בכל איטרציה) |
| $RBFS$ | $O(b \cdot d)$ (לינארי) | כן | כן | גבוה (Thrashing בין ענפים) |
| $SMA^*$ | $O(M)$ (מוגבל ע"י RAM) | כן (אם $d \le M$) | כן (אם המסלול $\le M$) | נמוך אם $M$ גדול; תזזיתי אם $M$ קטן מדי |
התנסות מעשית: מרוץ האלגוריתמים ומעקב גרף המבחן
בסימולציה הבאה תוכלו לצפות בגרף המבחן המלא בן 10 הצמתים, להריץ עליו במקביל או צעד אחר צעד את BFS, UCS, Greedy, ו-$A^*$, לעקוב בזמן אמת אחר תכולת תור העדיפויות וה-Explored Set, וללחוץ על כפתור "בדיקת עקביות" כדי לראות את הקשת $S \to B$ מהבהבת באדום עם חישוב אי-שוויון המשולש!
פרדיגמת החיפוש המקומי: טיפוס הרים וגרסאותיו
💡 כשהמסלול אינו מעניין – רק היעד קובע!
עד כה, בכל אלגוריתמי החיפוש שלמדנו (BFS, DFS, UCS, $A^*$), החזקנו בזיכרון עצי חיפוש שלמים כדי לשחזר את מסלול הפעולות המדויק מההתחלה עד הסוף. אבל חישבו על בעיות רבות בעולם האמיתי: בעיית $N$ המלכות, שיבוץ מערכת שעות שנתית באוניברסיטה, תכנון מעגלים מודפסים (VLSI), או קיפול חלבונים בביולוגיה. בבעיות אלו, המסלול שבו סודרו המלכות אינו מעניין איש! כל מה שמעניין אותנו הוא להגיע לקונפיגורציה הסופית הטובה ביותר. כאן נכנסת פרדיגמת החיפוש המקומי (Local Search): מוחקים את כל היסטוריית העבר, שומרים בזיכרון רק את המצב הנוכחי ($O(1)$ זיכרון!), ומטפסים לעבר הפסגה.
⛰️ 1. עקרונות היסוד של חיפוש מקומי (Local Search Principles)
בניגוד לחיפוש קלאסי, בחיפוש מקומי פועלים תחת המאפיינים הבאים:
מחזיק רק את המצב הנוכחי ($State$). אין רשימת חזית, אין רשימת סגורים ואין שמירת ענפי עץ.
לכל מצב מחושב ציון $f(s)$. במקסימיזציה שואפים לפסגה הגבוהה ביותר, ובמינימיזציה (Cost) שואפים לשפל.
בכל איטרציה בוחנים את קבוצת השכנים של המצב הנוכחי ועוברים לשכן שנבחר לפי אסטרטגיית האלגוריתם.
🧗 2. חמש הווריאציות המרכזיות של אלגוריתם טיפוס גבעה (Hill-Climbing)
לפניכם 5 הווריאציות המרכזיות והמוגדרות היטב של חיפוש מקומי. נסקור כל אחת מהן עם היתרונות, החסרונות והתנהגותה במרחב הבעיה:
כיצד פועל: סורק את כל האופרטורים החוקיים ומייצר את כל השכנים האפשריים של המצב הנוכחי. מתוכם, הוא בוחר ועובר לשכן שמציג את השיפור המקסימלי (המדרון התלול ביותר).
הוא נעצר מיד כאשר אין אף שכן שטוב מהמצב הנוכחי.
חיסרון מרכזי: חמדן וקצר-רואי לחלוטין. נתקע במהירות בפסגה המקומית הראשונה הנקרית בדרכו.
כיצד פועל: מאפשר מעבר לשכנים בעלי ערך שווה בדיוק ($\Delta E = 0$), כדי לאפשר לאלגוריתם "לזחול" על פני מישורים (Plateaus) או כתפיים (Shoulders) בתקווה למצוא שיפוע עלייה חדש.
המנגנון ההכרחי: כדי למנוע לולאה אינסופית על גבי המישור, חובה לקבוע חסם עליון קשיח (Limit) למספר מהלכי הצד הרצופים (למשל, עד 100 מהלכי צד). אם החסם נחצה – האלגוריתם נכנע ועוצר.
כיצד פועל: במקום לייצר ולמיין את כל אלפי השכנים, הוא מייצר שכנים באופן אקראי בזה אחר זה. ברגע שהוא נתקל בשכן הראשון שמשפר את המצב הנוכחי ($\Delta E > 0$), הוא מבצע את המעבר מיד!
מתי נשתמש: חיוני במרחבים בעלי מקדם הסתעפות עצום (עשרות אלפי שכנים), שבהם עלות הערכת כל השכנים משתקת את המחשב.
כיצד פועל: מאתר את כל השכנים המשפרים, אך אינו בוחר בהכרח בתלול ביותר. במקום זאת, הוא בוחר שכן באופן הסתברותי, כאשר ההסתברות לבחור בשכן $i$ היא יחסית לעוצמת השיפור שלו:
יתרון: מאזן בין ניצול מידע (Exploitation) לבין חקירה מגוונת (Exploration) ומסייע להימנע מכיסי מקסימום צרים.
כיצד פועל: מתגבר על בעיית המקסימום המקומי באמצעות סדרת ריצות עצמאיות: בכל פעם שטיפוס גבעה נתקע במקסימום מקומי, מאתחלים את המערכת ממצב התחלתי אקראי חדש לגמרי, וחוזרים חלילה עד למציאת המטרה.
משפט מתמטי חשוב: אם ההסתברות להגיע למקסימום הגלובלי ממצב התחלה אקראי היא $p > 0$, תוחלת מספר האתחולים הנדרשת עד להצלחה היא:
במרחב מצבים סופי, אלגוריתם זה הוא שלם (Complete) בהסתברות 1!
⚠️ 3. המכשולים הטופולוגיים במרחבי חיפוש מקומי
שלושת המכשולים המרכזיים שמכשילים אלגוריתמי טיפוס גבעה פשוטים:
פסגה הגבוהה מכל שכנותיה הישירות, אך נמוכה משמעותית מהפסגה הגלובלית האמיתית. כל צעד ממנה מהווה ירידה, ולכן האלגוריתם נכלא בה ללא מוצא.
רצף של פסגות מקומיות המחוברות לאורך קו רכס תלול. השיפוע האמיתי מתקדם באלכסון, אך מאחר שהאופרטורים מאפשרים רק צעדים בכיווני הצירים, כל צעד יחיד נראה לאלגוריתם כירידה!
אזור נרחב שבו לכל השכנים יש ציון זהה לחלוטין ($\Delta E = 0$). אין שום גרדיאנט המכוון את תנועת האלגוריתם, מה שעלול להוביל לשוטטות סרק אינסופית.
התנסות מעשית: זירת החיפוש המקומי והנוף הטופולוגי (Simulation Arena)
בסימולציה הבאה מוצגת מפת גבהים מרובת פסגות (הכוללת פסגות מקומיות, מישורים ורכסים). תוכלו לשגר סוכני טיפוס הרים שונים (Steepest Ascent, Sideways Moves, Simulated Annealing, ו-Local Beam Search), לצפות בזמן אמת כיצד החמדן נתקע במקסימום מקומי, ואיך מטא-היוריסטיקות מתקדמות נחלצות ומגיעות לפסגה הגלובלית!
מטא-היוריסטיקות מתקדמות: חישול מדומה וחיפוש אלומה
💡 כשהאלגוריתם שואב השראה מתנורי פלדה ומתורת האבולוציה
כיצד נחלצים ממלכודת מקסימום מקומי מבלי לאפס את החיפוש בכל פעם מחדש? חוקרי הבינה המלאכותית פנו לשני תחומי מדע עתיקים: התרמודינמיקה (תורת הפיזיקה הסטטיסטית) והביולוגיה האבולוציונית. ביחידה זו נלמד על חישול מדומה (Simulated Annealing) – אלגוריתם המאפשר לבצע "צעדים גרועים" בהסתברות מבוקרת טמפרטורה, ועל חיפוש אלומה (Local Beam Search) – המנהל צי של $k$ סוכנים במקביל ומגייס משאבים לאזורים פוריים, לצד גרסתו הסטוכסטית המצילה אותו מאובדן גיוון קטלני!
🔥 1. חישול מדומה (Simulated Annealing - SA)
האנלוגיה הפיזיקלית: בתהליך חישול מתכות במטלורגיה, מחממים מתכת לטמפרטורה גבוהה מאוד, ומקררים אותה באופן איטי ומבוקר. בטמפרטורה גבוהה האטומים נעים בחופשיות רבה, וככל שהחום יורד הם מתגבשים במבנה גבישי מושלם בעל אנרגיה פנימית מינימלית נטולת פגמים. אם נקרר מהר מדי ("Quenching") – המתכת תישבר עקב פגמים גבישיים.
הטמפרטורה $T$ יורדת בהדרגה עם התקדמות הזמן לפי פונקציית דעיכה (למשל: $T_{k+1} = \alpha T_k$ כאשר $0.85 \le \alpha < 1$):
- בתחילת החיפוש ($T$ גבוה מאוד): היחס $\frac{\Delta E}{T} \approx 0 \implies P \approx e^0 = \mathbf{1}$. האלגוריתם מקבל כמעט כל צעד רע, ומתנהג כמו הילוך אקראי (Random Walk) החוקר את מרחב המצבים לרוחבו ומדלג בקלות מעל פסגות ומכשולים!
- בסוף החיפוש ($T \to 0$): עבור מהלך רע מתקיים $\frac{\Delta E}{T} \to -\infty \implies P \approx e^{-\infty} = \mathbf{0}$. האלגוריתם מסרב לבצע צעדים רעים, ומתנוון לטיפוס גבעה חמדן רגיל (Greedy Hill-Climbing) ש"נועל" את הפסגה הגבוהה ביותר ומבצע אופטימיזציה מקומית מדויקת.
💡 2. חיפוש אלומה מקומי (Local Beam Search) ואפקט הגיוס
במקום לנהל מצב בודד, אלגוריתם חיפוש אלומה מחזיק ומנהל בו-זמנית $k$ מצבים נבחרים (ה"אלומה" - Beam).
בכל איטרציה, האלגוריתם מייצר את כל היורשים האפשריים של כל $k$ המצבים גם יחד לתוך מאגר (Pool) משותף אחד גדול.
מתוך מאגר כלל היורשים, האלגוריתם בורר את $k$ המצבים הטובים ביותר, והם בלבד מהווים את הדור הבא של האלומה.
בהרצת $k$ חיפושי טיפוס הרים עצמאיים במקביל (Parallel Runs), אין שום שיתוף מידע או תקשורת בין המסלולים. סוכן אחד עשוי להתקדם לעבר אזור צחיח, בעוד שעמיתו מצא מכרה זהב, ואף אחד אינו מסייע לשני.
לעומת זאת, בחיפוש אלומה מתרחש אפקט גיוס משאבים גלובלי (Collective Recruitment): אם אחד מהסוכנים מגלה גבעה פורה ומבטיחה במיוחד, שכניה של אותה גבעה יתפסו את מרבית המקומות ב-$k$ המצבים הנבחרים של הדור הבא! סוכנים שנתקעו באזורים שוממים ננטשים ונמחקים, וכל משאבי החישוב מופנים לסביבה המבטיחה!
⚠️ הסכנה המובנית: אובדן גיוון (Loss of Diversity) והפתרון הסטוכסטי
הבעיה: בשל אופיו החמדני של חיפוש האלומה הדטרמיניסטי, מהר מאוד כל $k$ המצבים עלולים להתקבץ בצפיפות סביב אותה פסגה בודדת (שהיא במקרה מקסימום מקומי גבוה). האלומה מאבדת את הפיזור המרחבי שלה, וכל $k$ הסוכנים עושים עבודה מיותרת וכפולה באותו שטח צר!
במקום לבחור בקשיחות את $k$ השכנים הטובים ביותר, בוחרים $k$ שכנים באופן הסתברותי, בדומה לתהליך הברירה הטבעית באבולוציה: לשכנים מצטיינים יש סיכוי גבוה בהרבה להיבחר, אך לשכנים פחות טובים יש סיכוי שאינו אפס להיבחר! רכיב אקראיות זה שומר על מגוון גנטי ומרחבי של האלומה, ומונע ממנה לקרוס כולה לתוך גבעה מקומית יחידה.
📊 3. טבלת השוואה כוללת של מטא-היוריסטיקות החיפוש המקומי
| אלגוריתם | מספר מצבים בזיכרון | מנגנון חילוץ ממקסימום מקומי | השראה מדעית | מגבלה / סיכון מרכזי |
|---|---|---|---|---|
| טיפוס גבעה (SAHC) | 1 | אין (נתקע מיד) | חמדנות ישירה | רגישות מוחלטת למקסימום מקומי ומישורים |
| חישול מדומה (SA) | 1 | קבלת צעדים גרועים לפי $P = e^{\Delta E / T}$ | פיזיקה סטטיסטית ומטלורגיה | קירור מהיר מדי (Quenching) יוביל לתקיעה |
| חיפוש אלומה (LBS) | k | שיתוף מידע וגיוס משאבים לאזורים פוריים | אינטליגנציית נחיל | אובדן גיוון (התכנסות כל ה-$k$ לאותה נקודה) |
| אלומה סטוכסטית | k | בחירה הסתברותית משמרת גיוון | ברירה טבעית ואבולוציה | רעש אקראי עלול לעכב מעט את ההתכנסות |
4 5 שאלות המלכודת הקלאסיות במבחן: מקרי קצה אסימפטוטיים באופטימיזציה
שאלות בחינה רבות באופו-יו מציגות פרמטריזציה קיצונית לאלגוריתמי החיפוש המקומי ובודקות לאיזה אלגוריתם בסיסי הם קורסים. להלן 5 מקרי הקצה הנפוצים ביותר:
בכל איטרציה מוחזק מצב בודד ($k=1$), מייצרים את כל שכניו ובוחרים מתוכם את השכן הטוב ביותר בלבד ($k=1$). זוהי בדיוק ההגדרה של טיפוס גבעה חמדני תלול ביותר (Steepest-Ascent Hill Climbing)!
כאשר רוחב האלומה $k$ אינו מוגבל (שומרים את כל השכנים שנוצרו ללא קיצוץ), האלגוריתם מפתח את כל המצבים ברמה הנוכחית לפני המעבר לרמה הבאה. זהו למעשה חיפוש לרוחב מלא ללא חסם זיכרון!
עבור צעד מדרדר ($\Delta E < 0$), הסתברות הקבלה היא $P = e^{\Delta E / T}$. כאשר $T \to 0^+$, החזקה שואפת ל-$-\infty$ ולכן $e^{-\infty} = 0$. צעדים מדרדרים אינם מתקבלים לעולם! צעדים משפרים מתקבלים מיד בהסתברות 1.
כאשר הטמפרטורה שואפת לאינסוף ($T \to \infty$), לכל צעד מדרדר מתקיים $\Delta E / T \to 0$, ולכן $P = e^0 = 1$! כל שכן שנבחר אקראית מתקבל בהסתברות ודאית, והאלגוריתם מתעלם לחלוטין מפונקציית המטרה.
באלגוריתם גנטי עם פרט בודד ($N=1$), לא ניתן לבצע הכלאה (Crossover) מכיוון שאין הורה שני. הפעולה היחידה שפועלת היא מוטציה על הפרט הבודד, ולכן האלגוריתם הופך לחיפוש מקומי של סוכן יחיד המבוסס על הפרעות אקראיות בלבד.
מילון מושגים וסיכום פרק 2
💡 חיבור כל חלקי הפאזל והכנה מקיפה
כל הכבוד! סיימתם בהצלחה את פרק 2 – אחד הפרקים המרכזיים, המעמיקים והעשירים ביותר בקורס מבוא לבינה מלאכותית. ביחידה מסכמת זו ריכזנו עבורכם מילון מושגים דו-לשוני מקיף עם כל המונחים והנוסחאות שחובה לשלוט בהם, צ'ק-ליסט של נקודות מפתח לבחינה, ואת הגשר הרעיוני אל פרק 3 שבו נצא מסביבות של סוכן יחיד אל עולם המשחקים והחיפוש היריבותי (Minimax וגיזום אלפא-ביתא)!
📖 מילון מושגים אקדמי דו-לשוני (Bilingual Academic Glossary)
היוריסטיקה שלעולם אינה מעריכה הערכת יתר את עלות ההגעה למטרה: $0 \le h(n) \le h^*(n)$. תנאי הכרחי ומספיק לאופטימליות $A^*$ בחיפוש עץ (Tree Search).
היוריסטיקה המקיימת את אי-שוויון המשולש: $h(n) \le c(n,a,n') + h(n')$. מבטיחה שערכי $f(n)$ מונוטוניים עולים. תנאי הכרחי לאופטימליות $A^*$ בחיפוש גרף (Graph Search).
שינוי בסיס ההצגה של מרחב הבעיה (כגון המרה לבסיס בינארי בבעיית $k \to 2k, 2k+1$) המאפשר פתרון דטרמיניסטי מיידי ב-$O(1)$ ללא כל צורך באלגוריתמי חיפוש.
חיפוש הפועל במקביל מנקודת המוצא קדימה ומהמטרה אחורה. כאשר מקדם ההסתעפות לאחור הוא $b=1$ (כגון חלוקה שלמה ב-2), החיפוש הופך לקו ישר מהיר במיוחד.
תופעה בבעיות לוח ורשתות שבה פעולה בודדת על איבר אחד משנה במקביל את מצבם של שכניו. שוברת קבילות של היוריסטיקות הסוכמות שגיאות באופן נאיבי.
משפחת אלגוריתמים הפועלת במרחבי אופטימיזציה שבהם המסלול אינו חשוב, אלא רק המצב הסופי. מחזיקה בזיכרון את המצב הנוכחי בלבד ($O(1)$ RAM).
מטא-היוריסטיקה בהשראת קירור מתכות. מקבלת צעדים משפרים תמיד, וצעדים מרעים בהסתברות $P = e^{\Delta E / T}$. ככל שהטמפרטורה $T$ יורדת, האלגוריתם מתכנס לחמדן.
חיפוש המחזיק $k$ מצבים במקביל, מייצר את כל צאצאיהם יחד, ובוחר את $k$ הטובים ביותר. שונה מהרצות מקבילות בזכות שיתוף המידע וגיוס המשאבים.
הסכנה שבה כל $k$ סוכני חיפוש האלומה קורסים ומתקבצים כולם סביב אותו מקסימום מקומי. נפתרת באמצעות אלומה סטוכסטית (Stochastic Beam).
מכשול טופולוגי המורכב מרצף של מקסימומים מקומיים לאורך קו רכס צר, המחייב תנועת זיגזג ומשתק אלגוריתמי טיפוס גבעה פשוטים.
🎯 צ'ק-ליסט: נקודות ברזל שחובה לזכור לבחינה!
הגשר לפרק 3: חיפוש יריבותי, תורת המשחקים ואלגוריתם Minimax
עד עתה, בפרקים 1 ו-2, פעלנו בסביבות של סוכן יחיד (Single-Agent Environment). העולם היה סטטי: הסוכן שקל פעולות, חישב מסלולים וקפץ בין גבעות, מבלי שאיש יפריע לו או ינסה להכשיל את תוכניותיו.
אך מה קורה כאשר בסביבה פועל יריב תבוני (Adversary) שמטרתו המדויקת היא הפוכה משלנו – להביא לתבוסתנו?
כיצד בונים סוכן תבוני המסוגל לנצח אלופי עולם בשחמט, דמקה, שש-בש ומשחקי אסטרטגיה מורכבים?
בפרק הבא נצלול לתוך חיפוש יריבותי (Adversarial Search): נלמד על עצי משחק, אלגוריתם Minimax ושיקולי עומק, נשלוט בטכניקת גיזום אלפא-ביתא ($\alpha$-$\beta$ Pruning) המכפילה את עומק החיפוש האפקטיבי, ונכיר את "אפקט האופק" (Horizon Effect) ופונקציות הערכה במשחקים!