מי פיתח את A*, ולמה
אלגוריתם חיפוש A* (נהגה "איי-סטאר") פותח ב-1968 בידי שלושה חוקרים ממכון-המחקר Stanford Research Institute (SRI) — פיטר הארט, נילס נילסון וברטרם רפאל — במאמר "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", שפורסם בכתב-העת IEEE Transactions on Systems Science and Cybernetics. השלושה עבדו אז בקבוצת-הבינה-המלאכותית של SRI על שייקי (Shakey) — הרובוט הנייד הראשון שתכנן בעצמו את פעולותיו — וזקוקים היו לשיטה יעילה שתאפשר לרובוט לתכנן מסלול-תנועה בין מכשולים בחדר, ולא רק לזהות שמסלול כזה קיים בכלל.
המנגנון: שילוב עלות-בפועל עם ניחוש היוריסטי
האלגוריתם מרחיב שיטה קודמת ומוכרת יותר, אלגוריתם דייקסטרה (Dijkstra), שמוצא את המסלול הזול-ביותר בגרף אך בודק את כל הכיוונים בלי שום העדפה. A* מוסיף לכל צומת שני מרכיבי-עלות: g(n), העלות בפועל מנקודת-ההתחלה עד לאותו צומת, ו-h(n), הערכה היוריסטית — ניחוש מושכל, לא בהכרח מדויק — של המרחק הנותר משם ליעד. סכום שני המרכיבים, f(n), קובע איזה צומת ייבדק הבא: האלגוריתם תמיד מרחיב תחילה את הצומת עם ה-f(n) הנמוך-ביותר מבין אלה שעדיין לא נבדקו.
התנאי להבטחת-האופטימליות: היוריסטיקה קבילה
כל עוד ההיוריסטיקה h(n) אינה מגזימה לעולם בהערכתה את המרחק האמיתי הנותר (תכונה שנקראת "קבילות", admissibility), מוכיח המאמר המקורי מ-1968 שהאלגוריתם מבטיח למצוא את המסלול הזול-ביותר האפשרי — לא רק מסלול טוב-מספיק. יתרון נוסף שהוכח באותו מאמר: ככל שההיוריסטיקה מדויקת-יותר (בלי להגזים), כך האלגוריתם בודק פחות צמתים בדרך לפתרון, בהשוואה לחיפוש-עיוור כמו דייקסטרה שאין לו שום כיוון מועדף.
השם: מדוע "A*" ולא סתם "A"
הכוכבית בשם מציינת שמדובר במקרה הפרטי-והמובטח-אופטימלי מתוך משפחה רחבה-יותר של אלגוריתמי-חיפוש מבוססי-היוריסטיקה, שתוארה בהמשך בספרות המחקר: אלגוריתם כללי מהמשפחה עשוי להשתמש בכל היוריסטיקה, גם כזו שמגזימה ועלולה לפספס את הפתרון האופטימלי; הגרסה המסומנת בכוכבית היא זו שמבטיחה, בתנאי הקבילות שהוזכר לעיל, למצוא תמיד את הפתרון הטוב-ביותר.
מ-Shakey ועד ניווט ומשחקים: השימושים היום
בזכות השילוב בין ודאות מתמטית (הבטחת-האופטימליות) ליעילות מעשית, הפך A* לאחד האלגוריתמים הנפוצים והמצוטטים ביותר במדעי-המחשב. הוא נמצא כיום מאחורי יישומים יומיומיים כמו חישוב מסלול-נסיעה באפליקציות-ניווט וב-GPS, תכנון-תנועה של דמויות (NPC) במשחקי-מחשב, ותכנון-מסלולים לרובוטים אוטונומיים ולזרועות-רובוטיות בתעשייה — כל מקרה שבו צריך למצוא את הדרך הזולה-ביותר בין שתי נקודות בתוך מרחב עם מכשולים.
המשמעות: אבן-יסוד של ה-AI הסמלי-הקלאסי
A* נחשב לאחת מדוגמאות-הדגל של "AI קלאסי" (Classical/Symbolic AI) — הגישה הסמלית-מבוססת-חוקים וחיפוש-במרחב-מצבים, שקדמה ללמידת-המכונה הסטטיסטית והלמידה-העמוקה של היום. הוא עודנו נלמד כאבן-יסוד בכל קורס-מבוא לבינה מלאכותית, ומדגים עיקרון שנשאר רלוונטי גם מחוץ לחיפוש-מסלולים: שילוב בין ידע-תחום (ההיוריסטיקה) לבין חיפוש שיטתי יכול להיות יעיל משמעותית מחיפוש עיוור.