תחי ישראל - אין לנו ארץ אחרת

תחי ישראל -אין לנו ארץ אחרת

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

מחבר:
בתאריך:

coding challenge solved by dynamic programming algorithm - longest increasing path in a matrix

נתונה מטריצה דו-ממדית, 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 כוכבים

 

 

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

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

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

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

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

הוסף תגובה חדשה

 

 

ענה על השאלה הפשוטה הבאה כתנאי להוספת תגובה:

איך אומרים בעברית אינטרנט?