מבוא לbacktracking או מציאת כל השילובים באמצעות אלגוריתם גישוש נסוג

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

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

ככה זה עובד:

1. תתחיל בכניסה: בחר נתיב, וצעד צעד אחד.
2. האם אתה יכול להמשיך מבלי להיתקל בקיר או ללכת לאיבוד?
   
   • אם כן: נהדר! תמשיך בבניית המסלול, צעד צעד נוסף באותו כיוון.
   • אם לא: עצור! אתה בנתיב ללא מוצא.
3. אם הגעת לנתיב ללא מוצא אז חזור לאחור: חזור על עקבותיך ולך בחזרה ל"נקודת ההסתעפות" האחרונה (במסגרתה בחרת בנתיב).
4. בדוק אפשרויות אחרות: בחר נתיב חדש מאותה נקודת הסתעפות, ואז חזור על שלבים 2 ו-3.
5. המשך לחקור: המשך לבנות את המסלול ולחזור לאחור עד שתמצא את היציאה, או עד שתחקור את כל הנתיבים האפשריים ולא תמצא את היציאה.

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

להלן כמה דברים שכדאי לזכור לגבי אלגוריתם גישוש נסוג:

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

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

מה ההבדל בין גישה של כוח גס brute force לבין גישוש נסוג back track

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

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

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

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

דוגמה לבעיה שניתן לפתור באמצעות אלגוריתם גישוש נסוג backtracking

נראה דוגמה לבעיה שניתן לפתור באמצעות אלגוריתם גישוש נסוג.

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

לדוגמה:

בהינתן הקלטים:

coins = [1, 4, 5]
target = 5

אשר יוזנו לפונקציה:

coin_combinations(coins, target)

הפלט הצפוי הוא:

[[1, 1, 1, 1, 1], [1, 4], [4, 1], [5]]

זוהי דוגמה טובה לבעיה הניתנת לפתרון באמצעות אלגוריתם גישוש נסוג מהסיבות הבאות:

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

אתה יכול לנסות לפתור בעצמך או להציץ בפתרון שאני מצאתי.

def coin_combinations(coins, target):
   """
   Finds all possible combinations of coins to reach the target sum.


   Args:
       coins: A list of coin denominations.
       target: The target sum to reach.


   Returns:
       A list of lists, where each sublist represents a valid combination of coins.
   """
   combinations = []


   def backtrack(current_sum, current_coins):
       # Base case: If the current sum equals the target, add the current combination to the result
       if current_sum == target:
           combinations.append(list(current_coins))
           return


       # Explore all possible choices starting from the current index
       for coin in coins:

           # Check if adding the current coin exceeds the target; if not, explore this choice
           if current_sum + coin <= target:
               # Explore
               current_coins.append(coin)
              
               # Recursively explore further combinations, starting from the current index
               backtrack(current_sum + coin, current_coins)
              
               # Backtrack: Remove the last coin to try another combination
               current_coins.pop()


   # Start the backtracking process
   backtrack(0, [])


   return combinations

נבדוק את הפתרון:

# Test case
coins = [1, 4, 5]
target = 5
combinations = coin_combinations(coins, target)
print(combinations)




# Test case
coins = [1, 4, 5]
target = 5
combinations = coin_combinations(coins, target)
print(combinations, len(combinations))




coins = [1, 2, 3, 4, 5]
target = 5
combinations = coin_combinations(coins, target)
print(combinations, len(combinations))




coins = [2, 3, 4]
target = 1
combinations = coin_combinations(coins, target)
print(combinations, len(combinations))

מרשם לשימוש באלגוריתם גישוש נסוג

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

1. הגדרת הבעיה:
   
   • ניסוח ברור של הבעיה שאותה מנסים לפתור, כולל הקלט, הפלט ואילוצי הבעיה.
   • זיהוי מרכיבי המפתח שיכללו בפתרון, כגון המשתנים ומבני הנתונים הדרושים.
2. זיהוי מקרי בסיס base case:
   
   • קביעת התנאים המייצגים פתרון שלם או תקף. מקרים בסיסיים אלה יגרמו לאלגוריתם לסיים ולהחזיר את הפתרון.
3. כתיבת פונקציה רקורסיבית:
   
   • יצירת פונקציה רקורסיבית שתחקור פתרונות אפשריים באופן שיטתי.
   • פונקציה זו בדרך כלל מקבלת כקלט את מצב הפתרון הנוכחי ובונה עליו.
4. חקירת אפשרויות:
   
   • בתוך הפונקציה הרקורסיבית, מעבר על הבחירות הזמינות עבור השלב הנוכחי.
   • עבור כל בחירה, יש לבדוק אם היא תקפה על סמך האילוצים של הבעיה.
5. בניית פתרון הדרגתית:
   
   • אם בחירה תקפה, יש לשלב אותה בפתרון החלקי הנוכחי.
   • יש לקרוא באופן רקורסיבי לפונקציית הגישוש נסוג כדי לחקור בחירות נוספות על סמך המצב המעודכן.
6. חזרה לאחור:
   
   • אם בחירה מובילה למבוי סתום או למצב לא תקף, יש להחזיר את הפתרון החלקי למצבו הקודם.
   • מנגנון חזרה לאחור זה מאפשר לאלגוריתם לנסות נתיבים שונים עד למציאת פתרון תקף.
7. החזרת פתרונות:
   
   • כאשר מגיעים למקרה בסיסי, יש להחזיר את הפתרון התקף או לאחסן אותו ברשימת הפתרונות אם קיימים מספר פתרונות.

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

function backtrack(current_state):
   if is_valid_solution(current_state):
       # Base case: A valid solution is found
       store_or_process_solution(current_state)
   else:
       # Explore possible choices from the current state
       for choice in available_choices(current_state):
           # Make the choice and proceed
           make_choice(choice)

           # Recursively explore further choices
           backtrack(updated_state)

           # Backtrack: Undo the choice if it didn't lead to a solution
           undo_choice(choice)

נסביר:

• backtrack(current_state): פונקציה רקורסיבית זו מטפלת בתהליך גישוש נסוג.
• is_valid_solution(current_state): בודקת אם המצב הנוכחי מייצג פתרון תקף.
• store_or_process_solution(current_state): אם נמצא פתרון תקף, מאחסנת אותו ברשימה או מעבדת אותו לפי הצורך.
• available_choices(current_state): מייצרת רשימה של בחירות תקפות שניתן לבצע מהמצב הנוכחי.
• make_choice(choice): משנה את המצב הנוכחי כדי לשלב את הבחירה שנבחרה.
• backtrack(updated_state): קוראת לעצמה באופן רקורסיבי כדי לחקור בחירות נוספות מהמצב המעודכן.
• undo_choice(choice): מבטלת את השפעות הבחירה כדי לחזור למצב הקודם, ומאפשרת חקירה של נתיבים שונים.

איך ניתן להשיג תוצאות טובות יותר כשמשתמשים באלגוריתם גישוש נסוג?

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

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

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

שימוש באלגוריתם backtracking גישוש נסוג לפתרון האתגר של N מלכות

קוד לפתרון סודוקו בעזרת אלגוריתם backtracking גישוש נסוג

רקורסיה בפייתון - כל מה שרצית לדעת ועוד כמה דברים חשובים

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים