פתרון בעיות אופטימיזיציה באמצעות אלגוריתם חמדן

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

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

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

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

GreedyAlgo(Sequence): 
    Initialize solution

    For each item in Sequence: 
          Add item to solution if locally optimal and feasible

    Return solution

• כאשר solution הוא התוצאה האופטימלית של הרצת האלגוריתם במלואו.

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

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

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

אתגר הקיטבג החלקי Fractional Knapsack

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

למשימה שני חוקים נוספים:

1. קיבולת הקיטבג היא לכל היותר 47 ק"ג.
2. ניתן לבחור לא להכניס לקיטבג שק אורז מסויים, או להכניס חלק של שק או שק שלם אבל לא ניתן להכניס יותר משק 1 מכל סוג.

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

אילו השקים באתגר:

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

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

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

1. חשב את היחס בין הרווח מן השק למשקלו:

   Item	Value-to-Weight Ratio
   A	60 / 10 = 6
   B	100 / 20 = 5
   C	120 / 30 = 4
   D	40 / 5 = 8
   E	70 / 15 = 4.67

2. מיין את הפריטים בהתאם ליחס המחושב בסדר יורד:

   Item	Value-to-Weight Ratio
   D	8
   A	6
   B	5
   E	4.67
   C	4

3. מילוי הקיטבג: תתחיל ממילוי השק בפריט שיש לו את היחס הגבוה ביותר (D, יחס 8). כיוון שמשקלו 5 ולקיטבג קיבולת של 47 אין לך בעיה להכניס את כל פריט D. עדכן את קיבולת הקיטבג (47 - 5 = 42) ואת הרווח עד כה (40).

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

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

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

בוא נראה את קוד הפונקציה לפתרון האתגר התכנותי:

# Import the heapq module for creating a binary heap (a special kind of list)
import heapq

def fractional_knapsack(items: [], bag_capacity: int):
    # Objective: Maximize profit by selecting items while not exceeding the bag capacity
    # Initialize the maximum profit to zero
    max_profit = 0
    # Prepare a list to keep track of selected items
    selected_items = []
    
    # Calculate value-to-weight ratios for each item
    value_for_weight_pq = [(item[2] / item[1], item) for item in items]
    
    # Build a max heap (binary heap) of items based on ratios
    heapq._heapify_max(value_for_weight_pq)

    # While we have items to consider and bag space left
    while value_for_weight_pq and bag_capacity > 0:
        # Get the item with the highest ratio from the max heap
        _, item = heapq._heappop_max(value_for_weight_pq)
        
        # Calculate the fraction of the item that fits into the bag
        if bag_capacity - item[1] >= 0:
            # If the whole item fits, take it completely
            ratio = 1
        else:
            # If only a fraction fits, take that fraction
            ratio = bag_capacity / item[1]
        
        # Adjust the bag's space and increase the total profit
        bag_capacity -= ratio * item[1]
        max_profit += ratio * item[2]
        selected_items.append([item[0], ratio])

    # Return the highest profit we can get and the list of items we took
    return max_profit, selected_items

נבחן את הפתרון:

# Items: [name, weight, value]
items = [
    ['A', 10, 60],
    ['B', 20, 100],
    ['C', 30, 120],
    ['D', 5, 40],
    ['E', 15, 70],
]

bag_capacity = 47
max_profit, selected_items = fractional_knapsack(items, bag_capacity)

print('Max profit =', max_profit)
print('Selected items =', selected_items)

נסביר את הקוד:

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

שלבי הביצוע:

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

אתגר: תזמון עבודות תוך עמידה בלוחות זמנים Job Scheduling with Deadlines

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

רשימת העבודות מופיעה בטבלה הבאה:

כשאתה מתזמן את העבודות אתה צריך להביא בחשבון את המגבלות הבאות:

• כל עבודה דורשת שעה 1 להשלמתה.
• עומד לרשותך זמן עבודה כולל של 4 שעות בלבד (כי אם תעבוד יותר מדי ישרף לך המוח).
• אם אינך יכול להשלים עבודה בזמן עקב חריגה מה-deadline אתה לא תיקח אותה כי המוטו של העסק שלך הוא "עמידה בזמנים היא קודש קודשים".

המטרה שלך היא לתזמן את העבודות כך שתרוויח הכי הרבה במסגרת 4 שעות העבודה העומדות לרשותך.

הסבר הפתרון:

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

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

1. קודם כל, ננסה לשבץ את עבודה G שהיא הכי רווחית (רווח 500). אמנם ניתן להגישה חזרה ללקוח עד השעה החמישית אבל שעה זו אינה זמינה כי אנחנו מוגבלים ל-4 שעות אז נשבץ לשעה הרביעית שבה טרם שיבצנו עבודה.
2. בשלב השני, ננסה לשבץ את העבודה השנייה הרווחית ביותר A (רווח 100) אותה נשבץ לשעה השלישית כי זה מה שהעבודה דורשת ושעה זו פנויה לנו.
3. בשלב שלישי, ננסה לשבץ את העבודה השלישית הכי רווחית, F, (רווח 90) בשעה השלישית אך כיוון שזו שעה השמורה לפריט A נעבור לשבץ בשעה השנייה בגלל שהיא עדיין פנויה.
4. בשלב הרביעי, ננסה לשבץ את פריט E בעל הרווח הרביעי בגובהו (רווח 80) בשעה השנייה אבל כיוון ששעה זו תפוסה, נשבץ בשעה הראשונה.
5. בשלב הרביעי, ננסה לשבץ את פריט D בעל הרווח הרביעי בגובהו (60) בשעה הראשונה כיוון שהתנאי הוא שצריך לסיים את העבודה תוך שעה אולם כיוון שהשעה הראשונה כבר תפוסה נאלץ לוותר על השיבוץ.
6. בשלב החמישי, ננסה לשבץ את פריט B החמישי ברווחיותו בשעה הראשונה שכבר תפוסה ועל כן נוותר עליו.
7. בשלב השישי, ננסה לשלב את C בשעה הרביעית שאינה פנויה לנו ועל כן נוותר עליו.
8. אחרי שסיימנו לשבץ את כל הפריטים נסכום את הרווחים מהעבודות:

P(E) + P(F) + P(A) + P(G) = 80 + 90 + 100 + 500 = 770

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

הפתרון להלן מבוסס על סידור העבודות בסדר יורד של רווח בעזרת פונקציית למדא ומתודה sort() למיון רשימות של פייתון:

def schedule_jobs_with_deadlines(jobs: [], allowed_working_hours: int):
    # Goal: maximize profits
    total_profit = 0
    
    # Initialize the schedule with the allowed time slots
    schedule = [''] * allowed_working_hours  
    
    # Order by profit-per-job
    jobs.sort(key=lambda x: x[2])
    
    # As long as there are jobs to consider
    while jobs:
        # Get the job with the maximum profit from the jobs
        job_name, deadline, profit = jobs.pop()
        
        # If the job's deadline exceeds allowed working hours, adjust the deadline
        if deadline > allowed_working_hours:
            deadline = allowed_working_hours
        
        # Try putting the job in a time slot if not already captured by another job
        # If a time slot is occupied try the one before it
        for slot in reversed(range(deadline)):
            if schedule[slot] == "":
                schedule[slot] = job_name
                total_profit += profit
                break
    
    return schedule, total_profit 

ננסה את הפתרון שכתבנו:

# List of jobs: [name, deadline, profit]
jobs = [
    ['A', 3, 100],
    ['B', 1, 50],
    ['C', 4, 25],
    ['D', 1, 60],
    ['E', 2, 80],
    ['F', 3, 90],
    ['G', 5, 500]
]

working_hours = 4
schedule, max_profit = schedule_jobs_with_deadlines(jobs, working_hours)
 
print('Schedule =', schedule)
print('Profit =', max_profit)

שלבי הפתרון:

1. מסדרים את העבודות בסדר יורד של רווחים על מנת להבטיח מתן קדימות לעבודות הרווחיות ביותר.
2. יוצרים מערך schedule שמספר הפריטים בו תואם את מספר שעות העבודה האפשריות.
3. עוברים על העבודות מהרווחית ביותר בסדר יורד של רווחיות. אם הדד ליין של העבודה חורג ממסגרת הזמן אז עושים את ההתאמה הנדרשת (לדוגמה, אם העבודה דורשת דד ליין של 5 שעות כאשר השעה החמישית אינה זמינה כי יום העבודה מוגבל ל- 4 שעות נגדיר את הדד ליין שלה לשעה הרביעית האפשרית מבחינת לוח הזמנים). אחרי שעושים התאמות, מנסים לשבץ במסגרת הזמן, אם פנויה, (לדוגמה, אם ה-deadline הוא 4 שעות אז מנסים לשבץ בשעה הרביעית) אבל אם לא פנויה מנסים לשבץ בשעות שלפני כי אפשר למסור את העבודה ללקוח עוד לפני ה-deadline. אם מוצאים מסגרת זמן פנויה אז משבצים בה את העבודה.
4. אחרי שמסיימים לעבור על כל רשימת העבודות מחזירים את רשימת העבודות שבוצעו ואת הרווח המקסימלי שנצבר בתהליך.

בעיית מספר המטבעות הנמוך ביותר Minimum number of Coins

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

נוסח הבעיה: נתונה קבוצה של מטבעות בערך נקוב (למשל, {1, 5, 10, 25}) וסכום כסף אליו צריך להגיע. יש למצוא את המספר המינימלי של מטבעות הדרושים להשלמת הסכום.

אם הסכום אותו יש למצוא הוא 30 אז:

1. בשלב הראשון האלגוריתם ייבחר את המטבע בעל הערך הגבוה ביותר האפשרי שהוא 25.
2. בשלב השני האלגוריתם ייבחר במטבע של 5 כי הוא המטבע בעל הערך הגבוה ביותר האפשרי.

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

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

נניח קבוצה של מטבעות עם ערכים {1, 3, 4} והמטרה היא להשלים לסכום של 6. הגישה החמדנית תעשה משהו כזה:

• בשלב הראשון, תבחר מטבע של 4 שהוא הגבוה ביותר האפשרי
• בשלב השני, לא תהיה לה ברירה אלא לבחור מטבע של 1
• בשלב השלישי, בחירה במטבע נוסף של 1 תשלים את הסכום ל-6

סך המטבעות המשמשים יהיה 3.

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

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

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

ערימה בינארית Binary Heap ותור עדיפויות Priority Queue

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

יישום רשימת סמיכויות adjacency list - חלק ב בסדרה על גרפים

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

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

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

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