אתגר תכנותי: מציאת הנתיב העולה הארוך ביותר במטריצה

נתונה מטריצה דו-ממדית, matrix, עליך למצוא את אורך המסלול העולה הארוך ביותר.

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

לצורך הפתרון יש לכתוב פונקציה:

longest_increasing_path(matrix: List[List[int]]) -> int

שתחזיר את אורך המסלול העולה הארוך ביותר במטריצה.

דוגמה 1:

matrix = [
  [3, 2],
  [4, 1]
]


result = longest_increasing_path(matrix)
print(result)  # Output: 4

• הסבר: הנתיב הארוך ביותר אורכו 4 והוא עובר דרך: 1 > 2 > 3 > 4

דוגמה 2:

matrix = [
  [9, 12, 13],
  [6, 6, 14],
  [2, 13, 8]
]


result = longest_increasing_path(matrix)
print(result)  # Output: 6

• הסבר: הנתיב הארוך ביותר אורכו 6 והוא עובר דרך: 2 > 6 > 9 > 12 > 13 > 14

שים לב

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

מגבלות

• המטריצה הנתונה הינה מערך דו ממדי m x n אשר כל התאים בה מכילים ערכים מספריים.
• הערכים המספריים בכל תא בטבלה גדולים מ-0.

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

# Use numpy to print the matrix in a convenient-to-read form
import numpy as np

def longest_increasing_path(matrix):
    # Goal: compute the length of the longest increasing path
    max_len = 0
    
    # Get the number of rows and columns in the matrix
    row_len = len(matrix)
    col_len = len(matrix[0])
    
    # Initialize a 2D array to store the length of the longest increasing path at each cell
    dp = [[0 for _ in range(0, col_len)] for _ in range(0, row_len)]
    
    # Check if a given position is valid and the value at the position is greater than the parent cell's value
    def is_valid(row_idx, col_idx, parent_val):
        return 0 <= row_idx < row_len and 0 <= col_idx < col_len and parent_val < matrix[row_idx][col_idx]
        
    # Perform a recursive Depth-First Search (DFS) to find the longest increasing path
    def dfs(row_idx, col_idx):
        # Import the `max_len` variable from the outer scope
        nonlocal max_len
        
        # Base case: If the result for the current cell is already computed, return it
        if dp[row_idx][col_idx] > 0:
            return dp[row_idx][col_idx]
        
        # Define the possible movements (up, down, left, right)
        positions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        
        # Initialize the minimum path length for the current cell
        max_len_path = 1
        
        # Explore each possible movement
        for dy, dx in positions:
            if is_valid(row_idx+dy, col_idx+dx, matrix[row_idx][col_idx]):
                # Update the path length for the current cell based on valid moves
                max_len_path = max(max_len_path, 1 + dfs(row_idx+dy, col_idx+dx))

        # Update `max_len` if the path length for the current cell is greater
        if max_len_path > max_len:
            max_len = max_len_path
            
        # Store the result in the dp array 
        dp[row_idx][col_idx] = max_len_path
            
        # Return the max path length for the current cell
        return max_len_path
            
    # Iterate through each cell in the matrix
    for row_idx in range(0, row_len):
        for col_idx in range(0, col_len):
            # If the result for the current cell is not yet computed, compute it
            if dp[row_idx][col_idx] == 0:
                dfs(row_idx, col_idx)
       
    # Return the dp array and the maximum path length in the matrix         
    return dp, max_len

נבחן את התוצאות:

# Test cases
m = [[8, 6], [5, 3], [1, 1]]
res_dp, res_path_len = longest_increasing_path(m)  # Expected path: [1, 2, 3, 4]
print(np.matrix(res_dp)) 
print(res_path_len)  # Expected output: 4

m = [[9, 12, 13], [6, 6, 14], [2, 13, 8]]
res_dp, res_path_len = longest_increasing_path(m)  # Expected path: [2, 6, 9, 12, 13]
print(np.matrix(res_dp)) 
print(res_path_len)  # Expected output: 6

m = [[3, 3, 3], [3, 3, 3], [3, 3, 3]]
res_dp, res_path_len = longest_increasing_path(m)  
print(np.matrix(res_dp)) 
print(res_path_len)  # Expected output: 1

m = [[3, 3, 3], [3, 3, 3], [3, 4, 3]]
res_dp, res_path_len = longest_increasing_path(m)  # Expected path: [3, 4]
print(np.matrix(res_dp)) 
print(res_path_len)  # Expected output: 2

m = [[3, 3, 3], [3, 4, 3], [3, 3, 3]]
res_dp, res_path_len = longest_increasing_path(m)  # Expected path: [3, 4]
print(np.matrix(res_dp)) 
print(res_path_len)  # Expected output: 2

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

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

   # Initialize a 2D array to store the length of the longest increasing path at each cell
   dp = [[0 for _ in range(0, col_len)] for _ in range(0, row_len)]

   • הערכים בכל תא בטבלה מאותחלים בערך 0 כי לציין שאלגוריתם הסריקה DFS לא עבר דרכם.

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

   # Perform a recursive Depth-First Search (DFS) to find the longest increasing path
   def dfs(row_idx, col_idx):
           # Import the `max_len` variable from the outer scope
           nonlocal max_len
           
           # Base case: If the result for the current cell is already computed, return it
           if dp[row_idx][col_idx] > 0:
               return dp[row_idx][col_idx]
           
           # Define the possible movements (up, down, left, right)
           positions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
           
           # Initialize the minimum path length for the current cell
           max_len_path = 1
           
           # Explore each possible movement
           for dy, dx in positions:
               if is_valid(row_idx+dy, col_idx+dx, matrix[row_idx][col_idx]):
                   # Update the path length for the current cell based on valid moves
                   max_len_path = max(max_len_path, 1 + dfs(row_idx+dy, col_idx+dx))
   
           # Update `max_len` if the path length for the current cell is greater
           if max_len_path > max_len:
               max_len = max_len_path
               
           # Store the result in the dp array 
           dp[row_idx][col_idx] = max_len_path
               
           # Return the max path length for the current cell
           return max_len_path

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

   # Iterate through each cell in the matrix
   for row_idx in range(0, row_len):
       for col_idx in range(0, col_len):
           # If the result for the current cell is not yet computed, compute it
           if dp[row_idx][col_idx] == 0:
               dfs(row_idx, col_idx)

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

4. בסוף התהליך, הפונקציה מחזירה את הנתיב העולה הארוך ביותר ואת המערך dp:

   # Return the dp array and the maximum path length in the matrix         
       return dp, max_len

הערכת יעילות הפתרון

סיבוכיות זמן: O(m * n)

סיבוכיות הזמן נקבעת על ידי הלולאות המקוננות שעוברות בכל תא במטריצה. הלולאה החיצונית עוברת על השורות (m), והפנימית עוברת על העמודות (n). עבור כל תא, פונקציית dfs מבצעת חיפוש לעומק רקורסיבי, ובודקת תאים סמוכים. במקרה הגרוע ביותר, מבקרים בכל תא בדיוק פעם אחת, כי בפעמים הבאות שפונים לתא התשובה מוחזרת מטבלת התכנות הדינמי dp.

סיבוכיות מקום: O(m * n)

סיבוכיות המקום נשלטת בעיקר על ידי מטריצת העזר dp, המשמשת לאחסון אורך המסלול העולה הארוך ביותר עבור כל תא. למטריצה ממדים m x n, כאשר m הוא מספר השורות ו-n הוא מספר העמודות. לכן, סיבוכיות המקום היא O(m * n).

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

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

אלגוריתם חיפוש לעומק DFS - מהבנה ליישום

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

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

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

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