יחידה 10: אלגוריתמים חמדניים

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

הגישה החמדנית: עקרונות יסוד

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

מתי אלגוריתם חמדן עובד?

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

• תכונת הבחירה החמדנית (Greedy Choice Property): בחירה מקומית אופטימלית מובילה בהכרח לחלק מפתרון גלובלי אופטימלי. במילים אחרות, ברגע שביצענו בחירה חמדנית, תמיד קיים פתרון אופטימלי לבעיה המקורית הכולל את הבחירה הזו.
• תכונת תת-מבנה אופטימלי (Optimal Substructure Property): פתרון אופטימלי לבעיה מכיל בתוכו פתרונות אופטימליים לתת-בעיות שלה. תכונה זו משותפת גם לתכנון דינמי, אך היישום שלה באלגוריתמים חמדניים שונה: לאחר הבחירה החמדנית, נשארת תת-בעיה שיש לפתור באופן אופטימלי.

הוכחת נכונות של אלגוריתם חמדן

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

שלבי ההוכחה:

1. הוכחת תכונת הבחירה החמדנית (Greedy Choice Property):

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

   • נניח שקיים פתרון אופטימלי כלשהו (שאינו בהכרח חמדן).
   • אם הפתרון האופטימלי הזה כולל את הבחירה החמדנית הראשונה, מצוין.
   • אם לא, אנו מראים כיצד ניתן "להחליף" את הבחירה הראשונה של הפתרון האופטימלי בבחירה החמדנית, וליצור פתרון אופטימלי חדש שכולל את הבחירה החמדנית, ואינו גרוע יותר מהפתרון המקורי. זה מוכיח שתמיד קיים פתרון אופטימלי הכולל את הבחירה החמדנית.
2. הוכחת תכונת תת-מבנה אופטימלי (Optimal Substructure Property):

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

דוגמאות קלאסיות לאלגוריתמים חמדניים

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

• בעיית בחירת פעילויות (Activity Selection Problem): נתונות קבוצת פעילויות, לכל אחת זמן התחלה וסיום. המטרה היא לבחור את המספר המקסימלי של פעילויות שאינן חופפות. האלגוריתם החמדן בוחר תמיד את הפעילות שמסתיימת מוקדם ביותר.
• בעיית תרמיל הגב השברי (Fractional Knapsack Problem): נתונים פריטים, לכל אחד משקל וערך. יש לבחור פריטים (או חלקים מהם) כך שמשקלם הכולל לא יעלה על קיבולת התרמיל, וערכם הכולל יהיה מקסימלי. האלגוריתם החמדן בוחר תמיד את הפריט בעל היחס הגבוה ביותר של ערך למשקל. (שימו לב: עבור בעיית תרמיל הגב 0/1, בה לא ניתן לקחת חלקי פריטים, הגישה החמדנית נכשלת ויש להשתמש בתכנון דינמי).
• קוד הופמן (Huffman Coding): אלגוריתם לדחיסת נתונים ללא איבוד מידע, המבוסס על בניית עץ קידוד אופטימלי. בכל שלב, האלגוריתם בוחר את שני התווים (או צמתי העץ) בעלי השכיחות הנמוכה ביותר ויוצר מהם צומת חדש.
• אלגוריתמים למציאת עץ פורש מינימלי (MST) – קרוסקל ופרים: שני אלגוריתמים אלו, למרות שונים במימושם, מבוססים על עקרונות חמדניים. קרוסקל בוחר בכל שלב את הקשת הקלה ביותר שאינה יוצרת מעגל, ופרים מרחיב עץ קיים על ידי הוספת הקשת הקלה ביותר המחברת צומת בעץ לצומת מחוצה לו.

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

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

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

שאלות לדיון

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

נקודות לתשובת מודל

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