גישוש נסוג

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

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

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

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

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

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

להלן פסאודו קוד של פתרון רקורסיבי בעיית סיפוק אילוצים:

פונקציה ראשית:
  1. אתחל את כל המשתנים לריקים.
  2. בחר את אחד המשתנים והפעל את הפונקציה הרקורסיבית.
פונקציה רקורסיבית (מקבלת משתנה):
  1. נסה להציב למשתנה את כל הערכים, בזה אחר זה. לכל אחד מהם:
    1. אם הוא לא אפשרי, המשך לפתרון הבא. אם הוא אפשרי, בחר משתנה אחר והפעל את הפונקציה הרקורסיבית.
    2. אם חזר פתרון, החזר אותו. אם חזר false, המשך לפתרון הבא.
  2. החזר false.

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

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

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

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

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

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