גישוש נסוג

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

מימוש האלגוריתם[עריכת קוד מקור | עריכה]

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

דוגמאות[עריכת קוד מקור | עריכה]

אנימציה המתארת פתירת חידת שמונה המלכות באמצעות גישוש נסוג

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

דוגמה נוספת לשימוש בשיטה זו היא של אדסחר דייקסטרה שבשנת 1972 הסביר כיצד למצוא מילה ארוכה באלפבית של שלושה סימנים שאין לה שתי תת-סדרות רצופות עוקבות זהות (בעיית תאו-מורס מתחילת המאה העשרים).

קישורים חיצוניים[עריכת קוד מקור | עריכה]

P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.