אתגר תכנותי: האם תצליח לקחת את כל הקורסים?

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

זה בדיוק האתגר בבעיה Leetcode 207: נותנים לך רשימה של קורסים, ורשימת דרישות קדם. והשאלה היא: "האם אתה יכול להשלים את כל הקורסים ברשימה?"

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

הבעיה: תזמון קורסים Course Schedule (Leetcode 207)

נותנים לך לתכנן את תוכנית הלימודים שלך היכן שאתה לומד. לכל קורס יכולות להיות דרישות קדם. לדוגמה:

numCourses = 2
prerequisites = [(1, 0)]

• כלומר עליך לקחת 2 קורסים. כדי לקחת את קורס 1, עליך לקחת תחילה את קורס 0.

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

can_finish(numCourses: int, prerequisites: List[List[int]]) -> bool

הפונקציה תחזיר True אם ניתן לסיים את כל הקורסים, או False אם לא ניתן.

נראה דוגמאות נוספת:

num_courses = 4
prerequisites = [(1, 0), (2, 1), (3, 2), (3, 1)]

• 1תלוי ב-0
• 2 תלוי ב-1
• 3 תלוי ב-2
• גם 3 תלוי ב-1

ועל כן ניתן לקחת את כל 4 הקורסים.

בוא נראה דוגמה שלא עובדת:

num_courses = 4
prerequisites = [(1, 0), (2, 1), (3, 4)]

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

נראה דוגמה נוספת:

num_courses = 4
prerequisites = [(1, 0), (0,1)]

• תלוי ב-0, ו-0 תלוי ב-1. יש לנו תלות מעגלית ועל כן לא ניתן.

מקרי מבחן

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

# test cases
print(can_finish(4, [(1, 0), (2, 1), (3, 2), (3, 1)])) # True
print(can_finish(4, [(1, 0), (2, 1), (3, 4)]))         # False: course 4 is out of bounds
print(can_finish(4, [(1, 0), (2, 1), (3, 2)]))         # True
print(can_finish(2, [[1, 0], [0, 1]]))                 # False (cycle)
print(can_finish(2, [[1, 0]]))                         # True
print(can_finish(2, []))                               # True (no dependencies)

אולי תנסה בעצמך

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

שני המדריכים הבאים בהחלט יכולים לעזור בלמידת האלגוריתמים:

• הבנת אלגוריתם חיפוש לרוחב - BFS - סריקה של גרפים ומציאת הנתיב הקצר ביותר
• מיון טופולוגי באמצעות אלגוריתם Kahn

מהם אפשר לגזור את הפתרון לאתגר.

פתרון באמצעות אלגוריתם Kahn

הפתרון הבא לבעיה משתמש באלגוריתם Kahn לפתרון הבעיה:

from collections import deque

def can_finish(total_num_courses, prerequisites):
    if not prerequisites: 
        return True

    if total_num_courses < 1:
        return False

    num_courses_taken = 0

    adj_list   = {course: [] for course in range(total_num_courses)}
    in_degrees = {course: 0 for course in range(total_num_courses)}
    
    for course, pre in prerequisites:
        # Basic validation: Ensure course numbers are within the valid range
        if not 0 <= course < total_num_courses or not 0 <= pre < total_num_courses:
            return False
        # If valid fill the above data structures
        adj_list[pre].append(course)
        in_degrees[course] += 1
    
    # Initialize a queue
    q = deque() 
    # Queue all nodes with in-degree 0
    for course in range(total_num_courses):
         if in_degrees[course] == 0:
             q.append(course)


   # Perform BFS
    while q:
        current_course = q.popleft()
        num_courses_taken += 1
        for neighbor in adj_list[current_course]:
            in_degrees[neighbor] -= 1
            if in_degrees[neighbor] == 0:
                q.append(neighbor)

    return num_courses_taken == total_num_courses

נסביר:

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

• בנוסף, יש לנו מונה in-degree העוקב אחר מספר הקורסים בהם כל קורס תלוי.

• מוודאים שאף אחד מהקורסים או מהתלויות אינו חורג מרשימת הקורסים שיש לקחת.

• מאתחלים את מבנה הנתונים (queue) על ידי כך שממלאים אותו בקורסים שאין להם תלויות `in degree = 0`.

• אלגוריתם הסריקה לרוחב BFS:

  1. מסיר קורס שאפשר לקחת (כי אין לו תלויות) מהתור (queue).
  2. מוריד 1 ממספר התלויות של הקורסים התלויים בו.
  3. אם אחד הקורסים מגיע ל in_degree= 0 סימן שאין לו תלויות אז מוסיפים אותו לתור כי אפשר לקחת אותו.

• לבסוף, בודקים האם מספר הקורסים שניתן לקחת שווה למספר הקורסים שיש לקחת. אם כן, אז אפשר ללמוד את כל הקורסים.

הערכת יעילות

• יעילות זמן:O(V + E)

  V - מספר הקורסים (צמתים בגרף), E - מספר דרישות הקדם (קשתות המקשרות בין צמתים)

• יעילות מקום:O(V)

  מקום בזיכרון המוקצה לרשימת הסמיכויות ול-in degrees המאכלסים את הקורסים.

דוגמאות מהחיים

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

• ניהול תלויות בתוכנה כאשר מודולים ותוכנות תלויים לפעולתם במודולים ותוכנות אחרים (לדוגמה, pip של פייתון המוגדר dependency manager)
• קביעת סדר הפעולות בתהליך ייצור.
• הקצאת פעילויות במסגרת ניהול פרויקטים - מה יש לעשות לפני מה? איזה משימה יש לעשות לפני הנוכחית?

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

מיון טופולוגי באמצעות אלגוריתם Kahn

הבנת אלגוריתם חיפוש לרוחב - BFS - סריקה של גרפים ומציאת הנתיב הקצר ביותר

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

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

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

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