מהי בינה מלאכותית? (What is AI?)
💡 מבוא פדגוגי: הדילמה המכוננת של התחום
ברוכים הבאים לעולם הבינה המלאכותית! לפני שאנחנו כותבים שורת קוד אחת או מריצים אלגוריתמי חיפוש, עלינו להתמודד עם שאלת היסוד: מה אנחנו בעצם מנסים לבנות? הקושי המרכזי נובע מכך שהמושג "בינה" עצמו חומק מהגדרה אחידה. האם המטרה שלנו היא לשכפל במדויק את המוח האנושי על פגמיו והטיותיו, או שמא לבנות ישות חישובית רציונלית מושלמת שפועלת תמיד לפי האופטימום המתמטי?
📊 מטריצת ארבע הגישות להגדרת בינה מלאכותית
תרשים מושגי מארגןהגדרות הבינה המלאכותית נחלקות לאורך שני צירים: ציר המטרה (אנושי מול רציונלי) וציר המוקד (חשיבה ותהליך פנימי מול פעולה והתנהגות חיצונית).
מערכות שחושבות כמו בני אדם
Thinking Humanly
התמקדות במידול תהליכי החשיבה והקוגניציה האנושיים. שואבת השראה עמוקה ממדעי הקוגניציה, פסיכולוגיה ניסויית ומחקר המוח (נוירוביולוגיה).
מערכות שחושבות בצורה רציונלית
Thinking Rationally
האסכולה הלוגיסטית: התמקדות בחשיבה לוגית מוחלטת ("חוקי המחשבה" - Laws of Thought) המבוססת על סילוגיזמים וכללי היסק דדוקטיביים פורמליים.
מערכות שפועלות כמו בני אדם
Acting Humanly
התמקדות בהתנהגות חיצונית בלבד שאינה נבדלת מזו של אדם. מזוהה באופן מובהק עם מבחן טיורינג (1950). התהליך הפנימי אינו חשוב, אלא הפלט הנצפה.
מערכות שפועלות בצורה רציונלית
Acting Rationally (The Agent Approach)
התמקדות בבניית סוכנים (Agents) הפועלים כדי להשיג את התוצאה הטובה ביותר (או את התוצאה הצפויה הטובה ביותר תחת אי-ודאות) בהינתן המידע והמשאבים.
⚖️ 1. הציר הראשון: חיקוי האדם (Humanly) מול שאיפה לרציונליות (Rationally)
כשבוחנים את ביצועי האדם, מגלים במהרה כי בני אדם אינם רציונליים באופן מושלם. אנחנו סובלים מהטיות קוגניטיביות, מגיבים מתוך רגש, עייפות או חוסר סבלנות, ומבצעים שגיאות חישוב בסיסיות.
הגישה האנושית (Human-Centered)
מדד ההצלחה מבוסס על השוואה ניסויית לאדם (התנהגותית או פסיכולוגית). מדע אמפירי הדורש תצפיות על בני אדם.
הגישה הרציונלית (Rationality-Centered)
מדד ההצלחה מבוסס על אידיאל מתמטי: פעולה נכונה מוגדרת כפעולה שממקסמת את תוחלת מדד הביצועים. מדע הנדסי ומתמטי מדויק.
⚡ 2. הציר השני: חשיבה ותהליך פנימי (Thinking) מול פעולה חיצונית (Acting)
האם אכפת לנו כיצד המחשב מקבל את ההחלטה (ה"קופסה השחורה"), או שמא רק מאיכות הפעולה שהוא מוציא אל הפועל בסביבה?
- חשיבה רציונלית מול פעולה רציונלית: הסקת מסקנות לוגיות היא אמנם כלי רב עוצמה לקבלת החלטות, אך לפעמים היא איטית מדי או בלתי אפשרית. לדוגמה, כאשר רכב אוטונומי מזהה ילד שקופץ לכביש, ביצוע הוכחה לוגית פורמלית של 10 שניות יסתיים באסון. בלימת חירום מבוססת רפלקס היא הפעולה הרציונלית ביותר באותו רגע, למרות שלא נגזרה מהוכחה לוגית מורכבת!
- מבחן טיורינג (Acting Humanly): הוצע על ידי אלן טיורינג ב-1950 כמשחק החיקוי (The Imitation Game). שופט אנושי מנהל שיחה טקסטואלית עם אדם ועם מחשב. אם השופט אינו מסוגל להבדיל ביניהם – המכונה עברה את המבחן. כיום, תחום ה-AI מתמקד פחות במבחן טיורינג ויותר בפתרון בעיות מעשיות ברמת מומחה.
⚠️ מלכודת מבחן נפוצה: רציונליות איננה "ידיעת-כל" (Omniscience)!
סוכן רציונלי אינו יודע את העתיד ואינו מחזיק בכוחות קסם. אם אדם חוצה כביש באופן חוקי ופתאום מטאור נופל מהשמיים ופוגע בו – המעשה שלו עדיין היה רציונלי לחלוטין! רציונליות נמדדת לפי תוחלת ההצלחה בהינתן המידע והתפיסות שנקלטו עד לאותו רגע, ולא לפי חוכמה בדיעבד.
התנסות מעשית: חקר מטריצת ארבע הגישות ל-AI
בסימולציה זו תוכלו לחקור כיצד מערכות AI שונות מסווגות לאורך צירי החשיבה, הפעולה, האנושיות והרציונליות, וכיצד מגבלות זמן ואי-ודאות מעבירות סוכנים רציונליים מחשיבה לפעולה.
סוכנים חכמים, מודל PEAS וסיווג סביבות
🤖 מהו "סוכן" (Agent) ומדוע הוא עומד במרכז ה-AI המודרני?
בניגוד לתוכנית מחשב סטנדרטית שממתינה לפקודה ומחשבת פלט בודד, סוכן (Agent) הוא ישות אוטונומית שמקיימת לולאת אינטראקציה מתמשכת עם העולם. הסוכן קולט את הסביבה באמצעות חיישנים (Sensors), מפעיל תהליך עיבוד בקוד שלו, ופועל על הסביבה כדי לשנות אותה באמצעות מפעילים (Actuators).
🔄 לולאת התפיסה-פעולה של הסוכן (Perception-Action Loop)
Core AI Architectureחיישנים (Sensors)
קולטים תפיסות (Percepts) מהסביבה: מצלמות, רדאר, קלט טקסטואלי, חיישני טמפרטורה
תוכנית הסוכן (Agent Program)
f: P* → A
ממפה את רצף התפיסות המלא (Percept Sequence) לפעולה ספציפית
מפעילים (Actuators)
מוציאים פעולות (Actions) לפועל: גלגלים, מנועים, הצגת הודעה, שליחת פקודת מסחר
📐 ההבדל הפורמלי: פונקציית הסוכן מול תוכנית הסוכן
פונקציית הסוכן (Agent Function): הפשטה מתמטית תיאורטית $f: P^* \to A$. הפונקציה מקבלת את כל היסטוריית התפיסות שנקלטו אי פעם ($P^*$ מייצג את אוסף כל המחרוזות האפשריות מעל שפת התפיסות) ומחזירה פעולה $A$.
תוכנית הסוכן (Agent Program): המימוש האלגוריתמי הקונקרטי בקוד מחשב שרץ על גבי חומרה (Architecture). בגלל שרצף התפיסות יכול לגדול לאינסוף, בלתי אפשרי לשמור טבלת מיפוי מלאה בזיכרון. לכן תוכנית הסוכן מיישמת אלגוריתמים, מודלים פנימיים וקירובים.
🏗️ חמש המשפחות של ארכיטקטורת סוכנים
בספרות ובחומרי הקורס סוכנים מחולקים ל-5 רמות מורכבות, מהפשוט ביותר ועד לסוכן אוטונומי לומד:
סוכן עם תגובה פשוטה (Simple Reflex Agent - 2.4.2)
פועל אך ורק על בסיס התפיסה הנוכחית ברגע זה. מפעיל כללי "אם-אז" (If Condition Then Action) ישירים לחלוטין ללא כל זיכרון היסטורי.
סוכן עם זיכרון / מצב פנימי (Model-Based Reflex Agent - 2.4.3)
מחזיק מצב פנימי (Internal State) המשקף את ההיסטוריה של העולם ואת מה שחיישניו אינם יכולים לראות כרגע. כולל ידע על אופן התפתחות העולם וכיצד פעולות הסוכן משפיעות על הסביבה.
סוכן מבוסס מטרה (Goal-Based Agent - 2.4.4)
מעבר מידיעת "מצב העולם" אל שאלת "לאן אני רוצה להגיע?". הסוכן מחזיק הגדרת יעד (Goal) ומחפש סדרת פעולות שתביא אותו מהמצב הנוכחי אל מצב היעד. זהו הבסיס לכל אלגוריתמי החיפוש והתכנון שנלמד בפרק זה.
סוכן מבוסס תועלת (Utility-Based Agent - 2.4.5)
מטרה בינארית ("הצלחה" או "כישלון") אינה מספיקה כאשר ישנם מספר נתיבים שונים להשגת היעד. פונקציית תועלת ממפה מצב למספר ממשי המייצג את מידת ה"אושר" או שביעות הרצון של הסוכן. מאפשר שקלול בין מהירות, בטיחות ועלות, וניהול סיכונים תחת אי-ודאות.
סוכן לומד (Learning Agent - 2.4.6)
מסוגל לשפר את ביצועיו לאורך זמן ולהתאים את עצמו לסביבות לא מוכרות. מורכב מארבעה רכיבים קריטיים:
🧹 המחשה קלאסית: עולם הרובוט שואב האבק הדו-משבצתי
דוגמת יסוד בקורסהסביבה מורכבת משתי משבצות בלבד: משבצת A ומשבצת B. הרובוט יכול לקלוט את מיקומו הנוכחי והאם המשבצת שבה הוא נמצא מלוכלכת או נקייה.
אם מלוכלך ← שאב, אחרת ← עבור למשבצת השנייה מתפקד מצוין בסביבה נצפית במלואה. אך אם חיישן הלכלוך מתקלקל או שהסביבה מורכבת יותר, הוא עלול לנוע לנצח הלוך ושוב במשבצות נקיות ולבזבז אנרגיה!
📋 מודל PEAS לאפיון סביבת המשימה (Task Environment)
כדי לתכנן סוכן רציונלי, הצעד הראשון של מהנדס ה-AI הוא לאפיין את סביבת המשימה באמצעות ארבעת מרכיבי PEAS:
Performance Measure
מדד הביצועים
הקריטריון הכמותי הקובע עד כמה הסוכן הצליח בהשגת מטרתו (למשל: בטיחות, מהירות, חיסכון בדלק, רווח כספי).
Environment
הסביבה
המרחב שבו הסוכן פועל. יכול להיות פיזי (כביש, מחסן) או וירטואלי (בורסה, רשת אינטרנט, לוח שחמט).
Actuators
מפעילים
המנגנונים שבאמצעותם הסוכן מוציא לפועל פעולות ומשנה את העולם (הגה, בלמים, שליחת פקודה ברשת, הצגת טקסט).
Sensors
חיישנים
ההתקנים שדרכם הסוכן קולט את מצב העולם (מצלמות וידאו, LiDAR, חיישן סונאר, מקלדת, קבצי יומן).
| סוג המערכת | P - Performance | E - Environment | A - Actuators | S - Sensors |
|---|---|---|---|---|
| נהג מונית אוטונומי (Autonomous Taxi) | הגעה מהירה ובטוחה ליעד, ציות לחוק, נוחות נסיעה, מקסום רווח | כבישים, הולכי רגל, נהגים אחרים, תנאי מזג אוויר וראות | מנוע היגוי, דוושת גז, בלמים, איתות, צופר, מסך תצוגה לנוסע | מצלמות, LiDAR, GPS, מד מהירות, מד תאוצה, חיישני מנוע |
| אלגוריתם מסחר אוטומטי בבורסה | מקסום תשואה פיננסית, מינימום סיכון והפסדים | בורסות ניירות ערך מקוונות, זרמי חדשות, פעילות שחקנים אחרים | שליחת פקודות קנייה/מכירה (API), עדכון תיק השקעות | פיד מחירי מניות בזמן אמת, דוחות כספיים, רשתות חדשות פיננסיות |
🌐 ששת ממדי הסיווג של סביבות תפקוד
סיווג הסביבה קובע ישירות את מידת המורכבות החישובית של הסוכן. ככל שהסביבה קרובה יותר לקצה השני של הסקאלה, נדרשים אלגוריתמים מתקדמים יותר:
👁️ נצפית במלואה מול נצפית חלקית (Fully vs. Partially Observable)
נצפית במלואה: חיישני הסוכן קולטים את המצב השלם של העולם בכל רגע (כמו שחמט).
נצפית חלקית: חלק מהסביבה מוסתר או רועש (כמו פוקר עם קלפים מוסתרים, או נהיגה עם ערפל). דורש מצב פנימי.
🎲 דטרמיניסטית מול סטוכסטית (Deterministic vs. Stochastic)
דטרמיניסטית: המצב הבא נקבע ב-100% ודאות על ידי המצב הנוכחי ופעולת הסוכן.
סטוכסטית: ישנה אקראיות או אי-ודאות בתוצאת הפעולה (כמו הטלת קובייה, פנצ'ר בגלגל).
🎞️ אפיזודית מול המשכית (Episodic vs. Sequential)
אפיזודית: החוויה מחולקת למקטעים עצמאיים. הפעולה הנוכחית לא משפיעה על העתיד (כמו סיווג תמונות בודדות).
המשכית: הפעולה בהווה מכריעה את המצבים הבאים (כמו שחמט או נהיגה). דורש תכנון לטווח ארוך.
⏱️ סטטית מול דינמית (Static vs. Dynamic)
סטטית: העולם אינו משתנה בזמן שהסוכן "חושב" (כמו תשבץ או שחמט ללא שעון).
דינמית: העולם משתנה ברקע בזמן החישוב (כמו נהיגה או משחקי וידאו בזמן אמת).
📏 בדידה מול רציפה (Discrete vs. Continuous)
בדידה: מספר סופי ומוגדר של מצבים וצעדי זמן (כמו לוח שחמט 64 משבצות).
רציפה: מצבים, מהירויות וזוויות המשתנים ברצף מתמטי ממשי (כמו זווית היגוי רכב, זרוע רובוטית).
👥 סוכן יחיד מול מרובה סוכנים (Single vs. Multi-Agent)
סוכן יחיד: הסוכן פועל לבד בעולם (סוליטר).
מרובה סוכנים: קיימים שחקנים נוספים שיכולים להיות תחרותיים (שחמט) או שיתופיים (רכבים אוטונומיים שמשתפים מידע בצומת).
התנסות מעשית: מעבדת עולם שואב האבק והשוואת 5 ארכיטקטורות הסוכנים
בסימולציה זו תוכלו להריץ את עולם שואב האבק במבנה 4 חדרים (A, B, C, D) ולראות במו עיניכם כיצד סוכן רפלקס פשוט נכשל ונכנס ללולאה אינסופית בסביבה נצפית חלקית, בעוד שסוכן עם מודל ומצב פנימי שומר על הסוללה.
פתרון בעיות באמצעות חיפוש ומרחבי מצבים
💡 מדוע סוכנים רפלקסיביים נכשלים ומתי חייבים חיפוש ותכנון?
כאשר העולם מורכב, רב-שלבי ודינמי, סוכן המסתמך רק על כללי תגובה מיידיים נוטה להיתקע במבוי סתום. כדי להצליח, הסוכן חייב לתכנן מראש (Look-Ahead): לבחון בזיכרונו את ההשלכות של סדרת פעולות עתידיות בטרם יוציא אותן לפועל בעולם האמיתי. התהליך מורכב משלושה שלבים: ניסוח הבעיה (Formulation) $\to$ חיפוש מסלול אופטימלי (Search) $\to$ ביצוע הפעולות בסביבה (Execution / Rollout).
⚙️ חמשת המרכיבים הפורמליים של בעיית חיפוש
כל בעיית חיפוש בבינה מלאכותית מוגדרת באופן אקסיומטי ומדויק על ידי חמישה רכיבים מתמטיים:
מצב התחלתי (Initial State)
$s_0 \in S$
המצב שבו הסוכן מתחיל את פעולתו (למשל: מיקום התחלתי ב-GPS, לוח שחמט במצב פתיחה, או סדר קלפים נתון).
מרחב הפעולות (Actions)
$Actions(s)$
קבוצת כל הפעולות החוקיות והזמינות לסוכן מתוך מצב נתון $s$ (למשל: {פנה שמאלה, סע ישר, שאב, עצור}).
מודל מעברים (Transition Model)
$Result(s, a)$
פונקציית העוקב (Successor Function) המגדירה מהו המצב החדש שייווצר בעולם כתוצאה מביצוע פעולה $a$ במצב $s$.
בדיקת יעד (Goal Test)
$GoalTest(s) \to \{True, False\}$
פונקציה בוליאנית הקובעת האם מצב $s$ מהווה יעד סופי. יכולה להיות השוואה מפורשת למצב בודד או בדיקת תנאי מופשט (למשל: "כל הכלים מחוץ ללוח").
פונקציית עלות מסלול (Path Cost)
$g(n) = \sum c(s_i, a_i, s_{i+1})$
מקצה ערך מספרי לכל מסלול. מחושבת לרוב כסכום עלויות הצעדים הבדידים ($c(s, a, s')$). פתרון אופטימלי (Least-Cost Solution) הוא המסלול בעל העלות המצטברת הנמוכה ביותר.
🧠 ההבדל היסודי והמהותי: מצב (State) מול צומת (Node)
שאלת מבחן קלאסית!מצב (State)
קונפיגורציה פיזית של העולם
- • מייצג את המצב האמיתי של הסביבה ברגע נתון (למשל: "הרובוט נמצא בעיר חיפה").
- • אין לו "אבא", אין לו עומק בעץ, ואין לו היסטוריית פעולות.
- • מספר המצבים במרחב הבעיה הוא לרוב סופי.
צומת (Node) בעץ החיפוש
מבנה נתונים תכנותי המנהל את החיפוש
- • מכיל:
State(המצב המשויך),Parent(מצביע לאב),Action(הפעולה שיוצרה),Path-Cost (g)(עלות מצטברת), ו-Depth(עומק בעץ). - • אותו מצב פיזי יכול להופיע בעשרות או באינסוף צמתים שונים המייצגים מסלולים שונים שהגיעו אליו!
מרחב האופרטורים, קשתות הגרף ושחזור מסלול הפתרון (path / op-path)
תהי $S$ קבוצת המצבים, ו-$O$ קבוצת האופרטורים. לכל אופרטור $o \in O$ מוגדר תחום הגדרה $\text{Domain}(o) \subseteq S$. קשתות הגרף $E$ מוגדרות פורמלית:
לחלופין, פונקציית היורשים (Successor Function) מקצה לכל מצב את תת-קבוצת המצבים הבאים: $Succ(s): S \to 2^S$.
פונקציית העלות מקצה מחיר מעבר לכל קשת: $Cost: \{(s_1, s_2) \mid s_1 \in S, s_2 \in Succ(s_1)\} \to \mathbb{R}^+$.
בסיום החיפוש, הצומת המנצח מחזיק שרשרת מצביעי אב (parent). שחזור הפתרון מתבצע ברקורסיה מקישורי האב עד לשורש:
🔄 כיצד גרף סופי בעל מעגלים מייצר עץ חיפוש אינסופי?
נניח גרף של 3 ערים: $A \leftrightarrow B \leftrightarrow C$. מספר המצבים הוא 3 בלבד.
אך בחיפוש עץ (Tree Search) שאינו שומר זיכרון של צמתים שביקרנו בהם, מפותח ענף אינסופי:
A → B → A → B → A → ...
עץ החיפוש גדל לעומק אינסופי ($m = \infty$) למרות שמרחב המצבים הפיזי זעיר!
📊 פרמטרי המרחב וארבעת ממדי ההערכה לאלגוריתמי חיפוש
Branching Factor
גורם ההסתעפות המרבי (מספר הבנים המקסימלי של צומת בודד)
Depth of Least-Cost
עומק צומת היעד הזול ביותר מהשורש
Maximum Depth
העומק המרבי של מרחב המצבים (יכול להיות אינסוף $\infty$)
ארבעת ממדי ההערכה האקסיומטיים:
התנסות מעשית: פריסת מרחב מצבים לעץ חיפוש ומניעת התפוצצות אינסופית
בסימולציה זו תוכלו לחקור הלכה למעשה את ההבדל הקונספטואלי בין "מצב" (State) ל"צומת" (Node), ולראות כיצד מעגל פשוט בגרף בן 5 מצבים מייצר עץ חיפוש אינסופי (Tree Search), וכיצד רשימת סגורים (Closed Set) בחיפוש גרף מונעת זאת.
אסטרטגיות חיפוש לא מיודע (Uninformed / Blind Search)
🔍 מה הופך חיפוש ל"עיוור" ומה קובע את זהות האלגוריתם?
חיפוש לא מיודע נקרא "עיוור" משום שאין לו שום מושג אם צומת מסוים נמצא במרחק של צעד אחד מהיעד או במרחק מיליון צעדים. המידע היחיד העומד לרשותו הוא חוקי הבעיה הבסיסיים (פונקציית המעברים ובדיקת היעד). כל האלגוריתמים במשפחה זו חולקים את אותו שלד בדיוק; ההבדל היחיד ביניהם הוא סדר שליפת הצמתים מתוך תור הקצוות (ה-Fringe / Frontier).
חיפוש לרוחב (Breadth-First Search - BFS)
עקרון פעולה: הרחבה שיטתית של כל הצמתים ברמה הנוכחית של העץ לפני מעבר כלשהו לצמתים ברמה הבאה. מיושם באמצעות תור רגיל (FIFO - First In, First Out).
ב-BFS, הזיכרון ולא הזמן הוא צוואר הבקבוק שיפיל את המערכת. האלגוריתם חייב לשמור את כל חזית החיפוש בזיכרון ה-RAM בו-זמנית.
חיפוש בעלות אחידה (Uniform-Cost Search - UCS)
עקרון פעולה: מרחיב בכל שלב את הצומת הלא-מורחב בעל עלות המסלול המצטברת הנמוכה ביותר מההתחלה $g(n)$. מנוהל באמצעות תור קדימויות (Priority Queue) הממוין לפי $g(n)$ בסדר עולה. אם כל עלויות הצעדים זהות, האלגוריתם מתנהג באופן זהה לחלוטין ל-BFS.
ללא תנאי נוסף – האלגוריתם אינו שלם! אם מחירי הקשתות אינם חסומים מלמטה על ידי קבוע חיובי $\delta > 0$, קיים תרחיש בו סוכן מבצע אינסוף צעדים בעלויות דועכות (למשל צעדים בעלות $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots$).
סכום המסלול האינסופי שואף ל-$1$. אם מצב היעד נמצא במסלול בעלות $1.5$, האלגוריתם ימשיך להרחיב לנצח צמתים מהמסלול האינסופי (שעלותם נמוכה מ-$1$) ולעולם לא יגיע ליעד! רק קיומו של חסם תחתון $\delta > 0$ מבטיח שכל צעד מגדיל את $g(n)$ בכמות מינימלית, ולכן מספר הצמתים בעלי עלות קטנה או שווה ל-$C^*$ הוא סופי בהכרח: $\le \frac{b^{\lceil C^*/\delta \rceil} - 1}{b - 1}$, מה שמבטיח עצירה ושלמות.
חיפוש לעומק (Depth-First Search - DFS)
עקרון פעולה: צלילה ישירה לצומת העמוק ביותר בעץ החיפוש. כאשר מגיעים לעלה שאינו יעד, מבצעים נסיגה לאחור (Backtracking). מיושם באמצעות מחסנית (LIFO Stack).
חיפוש בעומק מוגבל (Depth-Limited Search - DLS)
פותר את בעיית העומק האינסופי של DFS על ידי הגדרת חסם עומק מלאכותי $l$. ברגע שהחיפוש מגיע לעומק $l$, הוא מבצע Backtracking ואינו ממשיך מטה.
תכונות: מקום לינארי $O(bl)$, זמן $O(b^l)$. שלם רק אם $l \ge d$ (אם החסם נבחר קטן מעומק הפתרון, הוא ייכשל ולא ימצא דבר).
חיפוש נסיגה עיוור (Backtracking Search)
עקרון פעולה של חיפוש נסיגה (Backtracking Search): דומה לחיפוש לעומק, אך במקום לפתח ולהחזיק בזיכרון את כל הבנים של כל צומת בו-זמנית ($b$ בנים בכל רמה), האלגוריתם מייצר בן אחד בלבד, חוקר אותו לעומק, ורק כאשר ענף זה מסתיים בכישלון – הוא מייצר ומפתח את הבן הבא בתור.
היתרון המרכזי הוא חיסכון חסר תקדים בזיכרון: לא כל הצמתים מפותחים בזמן המעבר. נשתמש בחיפוש זה במיוחד כאשר מקדם הסיעוף $b$ גדול מאוד (למשל אלפי או מיליוני אופרטורים חוקיים בכל מצב). ב-DFS רגיל הזיכרון הוא $O(b \cdot m)$, בעוד שב-Backtracking נשמר רק הצומת הפעיל הבודד בכל רמה לאורך ענף החקירה – $O(m)$ בלבד!
חיפוש בעומק מעמיק איטרטיבית (Iterative Deepening Search - IDS)
השילוב המושלם: מאחד את יתרון הזיכרון הלינארי של DFS עם השלמות והאופטימליות של BFS! האלגוריתם מריץ סדרת קריאות ל-DLS עם חסם גדל בהדרגה: $l = 0, 1, 2, 3, \dots, d$.
🧮 נוסחת זמן הריצה המדויקת של IDS:
בכל איטרציה מפותח עץ עד עומק $l$. זמן הריצה המצטבר עד למציאת פתרון בעומק $L$ (או $d$) נתון בנוסחה המדויקת:
$50 + 400 + 3,000 + 20,000 + 100,000$
$10 + 100 + 1,000 + 10,000 + 100,000 + 999,990$
הסבר הפרדוקס: רוב הצמתים בעץ נמצאים ברמה התחתונה ביותר ($b^d$). החזרה על השורש זניחה לחלוטין ($d$ פעמים), בעוד ש-BFS מייצר את כל הצמתים המיותרים ברמה $d+1$ לפני עצירה!
🌳 מול 🕸️ חיפוש עץ (Tree Search) לעומת חיפוש גרף (Graph Search)
כל אלגוריתמי החיפוש קיימים בשתי תצורות אלו:
📊 טבלת השוואה מסכמת – אלגוריתמי חיפוש עיוור
| אלגוריתם חיפוש | שלמות (Complete) | סיבוכיות זמן | סיבוכיות מקום | אופטימליות (Optimal) |
|---|---|---|---|---|
| חיפוש לרוחב (BFS) | כן* (אם $b$ סופי) | $O(b^L)$ | $O(b^L)$ | כן* (רק כשעלות קשתות זהה) |
| חיפוש בעלות אחידה (UCS) | כן* (רק אם עלות חסומה: $\delta > 0$) | $O(b^{\lceil C^*/\delta \rceil})$ | $O(b^{\lceil C^*/\delta \rceil})$ | כן (מחיר מינימלי מובטח) |
| חיפוש לעומק (DFS) | לא (ענפים אינסופיים/מעגלים) | $O(b^m)$ | $O(bm)$ (לינארי) | לא |
| חיפוש נסיגה (Backtracking) | לא | $O(b^m)$ | $O(m)$ (מינימלי מוחלט) | לא |
| חיפוש בעומק מוגבל (DLS) | כן (רק כאשר $L \le D$) | $O(b^D)$ | $O(b \cdot D)$ | לא |
| העמקה הדרגתית (IDS) | כן (מוחלט) | $O(b^L)$ | $O(b \cdot L)$ (לינארי) | כן (מוצא מסלול קצר ביותר) |
התנסות מעשית: זירת הקרב של אלגוריתמי החיפוש העיוור (BFS, UCS, DFS, DLS, IDS)
בסימולציה זו תוכלו להריץ ולהשוות ראש-בראש את חמשת אלגוריתמי החיפוש הלא-מיודע. עקבו אחר קצב יצירת הצמתים, מבנה נתוני החזית (Fringe), ומד צריכת הזיכרון (RAM) הממחיש את קטסטרופת הזיכרון של BFS מול היעילות של IDS.
אסטרטגיות חיפוש מושכל (Informed Search) ואלגוריתם A*
🧭 המעבר לחיפוש מושכל: פתרון בעיית ההתפוצצות הקומבינטורית
בעיות מהעולם האמיתי (כמו ניווט GPS בין מיליוני כבישים) אינן ניתנות לפתרון בחיפוש עיוור, משום שגורם ההסתעפות מייצר מספר אפשרויות שגדול ממספר האטומים ביקום. הפתרון הוא חיפוש מושכל (Informed Search): שילוב ידע ספציפי מתחום הבעיה (Domain Knowledge) באמצעות פונקציה היוריסטית $h(n)$ המשמשת כ"מצפן פנימי" המכוון את הסוכן ישירות לעבר היעד.
📐 פונקציית ההיוריסטיקה $h(n)$ ופונקציית ההערכה $f(n)$
פונקציית ההיוריסטיקה $h(n)$ (Heuristic Function): מעריכה את עלות המסלול הזול ביותר מהצומת $n$ ועד למטרה הקרובה ביותר. מתקיים תמיד: $h(n) \ge 0$, ועבור כל צומת יעד $G$ מתקיים $h(G) = 0$.
פונקציית ההערכה הכללית $f(n)$ (Evaluation Function): קובעת את סדר העדיפות לפיתוח צמתים בתור הקדימויות. הצומת בעל ערך $f(n)$ המינימלי הוא זה שייפתח ראשון.
⚡ חיפוש חמדן (Greedy Best-First Search)
האלגוריתם מפתח תמיד את הצומת שנראה קרוב ביותר ליעד לפי ההיוריסטיקה בלבד, תוך התעלמות מוחלטת מעלות המסלול ששולמה עד כה ($g(n)$).
- שלמות (Completeness): לא שלם בעץ (עלול להיתקע בלולאות אינסופיות); שלם בגרף במרחבים סופיים.
- אופטימליות (Optimality): לא אופטימלי (צעד ראשון זול היוריסטית עשוי להוביל למסלול יקר ביותר).
- סיבוכיות זמן ומרחב: $O(b^m)$ במקרה הגרוע (כמו DFS).
⭐ אלגוריתם $A^*$ (השילוב המושלם)
משלב את העלות המדויקת ששולמה עד כה $g(n)$ (כמו ב-UCS) יחד עם ההערכה של העלות שנותרה $h(n)$. $f(n)$ מבטאת את העלות הכוללת המוערכת של המסלול הזול ביותר דרך הצומת $n$.
- שלמות (Completeness): שלם (אם עלויות הצעדים $\ge \epsilon > 0$).
- אופטימליות (Optimality): אופטימלי מובטח תחת תנאי קבילות (בעץ) ועקביות (בגרף).
- יעילות אופטימלית: אף אלגוריתם אופטימלי אחר עם אותה היוריסטיקה אינו מרחיב פחות צמתים מ-$A^*$.
⚖️ תנאי האופטימליות של $A^*$: קבילות ועקביות
1. היוריסטיקה קבילה (Admissible Heuristic) – תנאי לאופטימליות בחיפוש עץ
היוריסטיקה היא קבילה אם היא לעולם אינה מעריכה הערכת-יתר (Never overestimates) את עלות ההגעה ליעד. כלומר, לכל צומת $n$ מתקיים:
כאשר $h^*(n)$ היא עלות המסלול האופטימלי האמיתי מ-$n$ ליעד. דוגמה קלאסית: מרחק קו-אווירי ($h_{SLD}$ - Straight-Line Distance) – מאחר שקו ישר הוא המרחק הקצר ביותר בין שתי נקודות, הוא לעולם לא יעריך הערכת-יתר מרחק נסיעה בכבישים.
2. היוריסטיקה עקבית / מונוטונית (Consistent / Monotonic) – תנאי לאופטימליות בחיפוש גרף
היוריסטיקה היא עקבית אם לכל צומת $n$, פעולה $a$ וצומת יורש $n'$, העלות המשוערת מקיימת את אי-שוויון המשולש:
משמעות עמוקה: עקביות מבטיחה שערכי $f(n)$ אינם יורדים לאורך שום מסלול ($f(n') \ge f(n)$).
✓ תוצאה קריטית: בחיפוש גרף עם היוריסטיקה עקבית, הפעם הראשונה שבה צומת כלשהו נשלף מה-Fringe ומועבר ל-Closed List, המסלול אליו הוא בוודאות המסלול האופטימלי ביותר. לכן אין צורך לעדכן לעולם צומת שכבר נסגר!
כאשר מציבים $h(n) = 0$ לכל $n$, פונקציית ההערכה הופכת ל-$f(n) = g(n) + 0 = g(n)$. במצב זה אלגוריתם $A^*$ משכפל בדיוק את התנהגותו של חיפוש בעלות אחידה (Uniform-Cost Search)!
אם $h_2(n) \ge h_1(n)$ לכל צומת $n$ (ושניהם קבילים), נאמר ש-$h_2$ שולטת ב-$h_1$. $A^*$ עם $h_2$ מובטח שיפתח תת-קבוצה של הצמתים שיפתח $h_1$ (פחות או שווה צמתים). לכן נעדיף תמיד היוריסטיקה גבוהה יותר שקרובה ל-$h^*(n)$.
בדיוק כמו BFS, צוואר הבקבוק המרכזי של $A^*$ במציאות אינו זמן הריצה אלא צריכת הזיכרון האקספוננציאלית לשמירת כל הצמתים בחזית. הפתרון: אלגוריתם $IDA^*$ – מיישם את רעיון ההעמקה האיטרטיבית, כאשר במקום לחסום עומק $d$, הוא חוסם את ערך ה-$f(n)$. בכל איטרציה מבוצע חיפוש עומק עד לחסם הנוכחי, ובסיומה החסם גדל לערך ה-$f$ המינימלי של צומת שנחרג. התוצאה: שמירה על אופטימליות עם זיכרון לינארי $O(bd)$ בלבד!
התנסות מעשית: מעבדת אלגוריתם A* – היוריסטיקה, קווי קונטור ושליטה במרחב רשת
בסימולציה זו תוכלו לחקור לעומק את פעולת אלגוריתם $A^*$ על גבי רשת דו-ממדית. בחנו כיצד שינוי פונקציית ההיוריסטיקה (מנהטן קבילה, מרחק אוירי, היוריסטיקה מנוונת $h=0$ שהופכת ל-UCS, או היוריסטיקה לא קבילה שמפרה אופטימליות) משפיע על כמות הצמתים שנפתחים ועל קווי הקונטור $f(n) \le C^*$.
מילון מושגים, סיכום מהיר של פרק 1 והכנה לפרק 2
📖 ריכוז מושגי המפתח של פרק 1 – כלי עבודה מהיר לחזרה ובחינה
יחידה זו מרכזת את כל המונחים, ההגדרות הפורמליות וההבדלים המהותיים שנלמדו בפרק, יחד עם "מלכודות מבחן" קלאסיות שמופיעות בממ"נים ובבחינות הגמר, וסיכום תמציתי של עקרונות היסוד לקראת המעבר לחיפוש יריבותי בפרק 2.
📚 מילון מושגים אקדמי מורחב
⚠️ חמשת מוקשי הבחינה הקלאסיים בפרק 1 (מלכודות סטודנטים ב-20551)
תמיד בזמן שליפת הצומת (Expansion) ולא ביצירתו! בדיקה בזמן יצירה מפרה את תכונת האופטימליות, שכן ייתכן שקיים מסלול עקיף וזול יותר שטרם הגיע לאותו צומת.
משום שקצב הגידול של העץ הוא אקספוננציאלי לפי גורם ההסתעפות $b$. הרוב המכריע של הצמתים (כ-$(b-1)/b$ מכלל הצמתים) שוכנים ברמה התחתונה $b^d$, ולכן העבודה החוזרת על רמות השורש היא זניחה אסימפטוטית.
לא! רציונליות נמדדת לפי ההחלטה הטובה ביותר בהינתן המידע שהיה בידי הסוכן, ולא לפי מזל או חוכמה בדיעבד. סוכן יכול לפעול ברציונליות מושלמת ועדיין להיכשל בגלל סביבה סטוכסטית.
האלגוריתם הופך בדיוק ל-חיפוש בעלות אחידה (UCS), שכן $f(n) = g(n) + 0 = g(n)$.
הזיכרון (Space Complexity), ולא זמן הריצה! המחשב יקרוס מחוסר RAM לאחסון חזית החיפוש שבועות רבים לפני שיסתיים זמן החישוב התיאורטי.
סיכום מהיר: מה למדנו בפרק 1 ומבט קדימה לפרק 2
פרק 1 הניח את התשתית המתמטית והאלגוריתמית לכל הקורס: המעבר מהגדרה פילוסופית של בינה לפתרון בעיות הנדסי באמצעות חיפוש במרחב מצבים.
הגדרת בינה כפעולה רציונלית, אפיון משימות במודל PEAS, 6 תכונות סביבה והתפתחות מודל הסוכן מרפלקסיבי פשוט ועד לסוכן מבוסס תועלת ולומד.
הפרדה ברורה בין מצב פיזי (State) לצומת חיפוש (Node), 5 רכיבי הבעיה הפורמלית, וההבדל הקריטי בין חיפוש עץ (סכנת לולאות) לחיפוש גרף (Closed Set).
היררכיית החיפוש ללא ידע: BFS (שלם ואופטימלי אך זולל זיכרון), DFS (זיכרון לינארי אך לא שלם ולא אופטימלי), ו-IDS המשלב את המיטב משניהם עם זיכרון $O(bd)$.
פונקציית ההיוריסטיקה $h(n)$, אלגוריתם $A^*$ ($f=g+h$), תנאי קבילות ועקביות להבטחת אופטימליות, קווי קונטור $f \le C^*$, ופתרונות מוגבלי זיכרון ($IDA^*$).
עד כה הנחנו שהסוכן פועל בעולם שבו שום גורם אינו מתנכל לו. בפרק 2 נעבור אל חיפוש יריבותי (Adversarial Search): מה קורה כשיש בסביבה סוכן יריב שמנסה באופן אקטיבי למזער את התועלת שלנו? נלמד את אלגוריתם Minimax, שיטת הגיזום המהפכנית אלפא-בטא ($\alpha$-$\beta$ Pruning), קבלת החלטות בזמן אמת במשחקים (שחמט, דמקה), ומשחקים הכוללים מזל והסתברות (Expectiminimax)!