מהו מעקב אחורי? - הגדרה מטכנולוגיה

הגדרה - מה המשמעות של Backtracking?

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

חברת Techopedia מסבירה את Backtracking

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

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