אלגוריתם החיפוש A* הוא שיטה פופולרית של תוואי וגרף מסלול בשימוש ביישומים שונים כגון רובוטים, פיתוח משחק ומערכות ניווט.זה משלב את התכונות של חיפוש אחיד עלות חיפוש וחיפוש מיטבי חמדני ראשון, מה שהופך אותו יעיל למציאת הנתיב הקצר ביותר בגרפים במשקל.מדריך זה מספק גישה צעד-על-ידי-שלב ליישום A * עם דוגמאות מעשיות.

להבין את A * Algorithm

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

שלב A* שלב-by-Step

בצע שלבים אלה כדי ליישם A * בשפת תכנות כמו Python:

  • עדכן את הרשימה הפתוחה עם הצומת הראשון ואת הרשימה סגורה כריקה.
  • ללופ עד שהרשימה הפתוחה ריקה:
  • להסיר את הצומת עם העלות הנמוכה ביותר של הרשימה הפתוחה.
  • אם הצומת הזה הוא המטרה, לשחזר את הדרך ולסיים.
  • אחרת, ליצור את שכנותיה ולהעריך כל אחד:
  • חישוב העלות להגיע לכל שכנה והעריך את המרחק שנותר למטרה באמצעות תפקוד תיירותי.
  • אם שכנה אינה ברשימה פתוחה או סגורה, הוסף אותה לרשימה הפתוחה עם העלות הכוללת שלה.
  • העבר את הצומת הנוכחי לרשימה סגורה.

דוגמא מעשית

שקול רשת שבה כל תא מייצג צומת, ועלות התנועה היא אחידה.התיוייר המשמש הוא מרחק מנהטן.יישום A* כרוך בהקמת מבני נתונים עבור הרשת, עלויות, ואת נקודות ההורות. במהלך ביצוע, האלגוריתם חוקר את הרשת, עדיפות נקודות קרוב יותר למטרה המבוססת על היוריסט, בסופו של דבר למצוא את הדרך הקצרה ביותר.

סיכום

יישום A * דורש הבנה של רכיבי הליבה שלה: הרשימה הפתוחה, הרשימה סגורה, חישובים עלות ותפקוד הירריסטי.על ידי ביצוע תהליך שלב-שלב ויישום לדוגמאות מעשיות, מפתחים יכולים למעשה לשלב A * לתוך היישומים שלהם עבור פתרונות אופטימליים של מציאת נתיב.