מעקב אחר אלגוריתמים: רקורסיבי וחיפוש מוסבר בדוגמאות

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

1. חידות כמו חידת מלכות שמונה, תשבצים, חשבון מילולי, סודוקו [nb 1] ופית סוליטייר.
2. בעיות אופטימיזציה קומבינטוריות כמו ניתוח ובעיית הכנאפה.
3. שפות תכנות לוגיות כגון אייקון, מתכנן ופרולוג, המשתמשות במעקב חוזר באופן פנימי ליצירת תשובות.

בעיה לדוגמא (בעיית הסיור של האביר)

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

נתיב ואחריו נייט לכיסוי כל התאים

להלן לוח שחמט עם 8 x 8 תאים. המספרים בתאים מצביעים על מספר הזזה של האביר.

אלגוריתם נאיבי לסיבוב ההופעות של נייט

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

while there are untried tours { generate the next tour if this tour covers all squares { print this path; } } 

חזרה אלגוריתם לסיבוב ההופעות של נייט

להלן אלגוריתם Backtracking לבעיית הסיור של נייט.

If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" ) 

והנה הסבר לסרטון עבורך