מהו אלגוריתם חמדני?
אולי שמעתם על הרבה טכניקות עיצוב אלגוריתמיות בזמן שסיננתם בחלק מהמאמרים כאן. חלקם הם:
- בכוח הזרוע
- הפרד ומשול
- תכנות חמדן
- תכנות דינמי עד כמה שם. במאמר זה תלמדו מהו אלגוריתם חמדני וכיצד תוכלו להשתמש בטכניקה זו כדי לפתור הרבה בעיות תכנות שאחרת אינן נראות טריוויאליות.
דמיין שאתה יוצא לטיולים והמטרה שלך היא להגיע לשיא הגבוה ביותר האפשרי. יש לך כבר את המפה לפני שתתחיל, אך ישנם אלפי נתיבים אפשריים המוצגים במפה. אתה עצלן מדי ופשוט אין לך זמן להעריך כל אחד מהם. הברג את המפה! התחלתם לטייל באסטרטגיה פשוטה - היו חמדנים וקצרי רואי. פשוט קח שבילים המשתפלים ביותר. זה נראה כמו אסטרטגיה טובה לטיולים. אבל האם זה תמיד הכי טוב?
לאחר סיום הטיול וכל גופך כואב ועייף, אתה מסתכל לראשונה על מפת הטיולים. אלוהים אדירים! יש נהר בוצי שהייתי צריך לחצות אותו במקום להמשיך ללכת למעלה. המשמעות היא שאלגוריתם חמדני בוחר את הבחירה המיידית הטובה ביותר ולעולם לא שוקל מחדש את בחירותיו. מבחינת אופטימיזציה של פתרון, זה פשוט אומר שהפתרון החמדן ינסה למצוא פתרונות אופטימליים מקומיים - שיכולים להיות רבים - ועלול להחמיץ פתרון אופטימלי עולמי.
הגדרה רשמית
נניח שיש לך פונקציה אובייקטיבית שצריך למטב (או למקסם או למזער) בנקודה מסוימת. אלגוריתם חמדן מבצע בחירות חמדניות בכל שלב כדי להבטיח את הפונקציה האובייקטיבית. לאלגוריתם החמדן יש ירייה אחת בלבד כדי לחשב את הפתרון האופטימלי כך שהוא לעולם לא יחזור לאחור ויהפוך את ההחלטה.
לאלגוריתמים חמדניים יש כמה יתרונות וחסרונות:
- די קל להמציא אלגוריתם חמדני (או אפילו אלגוריתמים חמדניים מרובים) לבעיה. ניתוח זמן הריצה לאלגוריתמים חמדניים יהיה בדרך כלל קל בהרבה מאשר לטכניקות אחרות (כמו חלוק וכיבוש). לטכניקת הפרד והכיבוש, לא ברור אם הטכניקה מהירה או איטית. הסיבה לכך היא שבכל רמה של רקורסיה הגודל של קטן יותר ומספר בעיות המשנה גדל.
- החלק הקשה הוא שעבור אלגוריתמים חמדניים אתה צריך לעבוד הרבה יותר קשה על מנת להבין בעיות נכונות. גם עם האלגוריתם הנכון, קשה להוכיח מדוע הוא נכון. ההוכחה שאלגוריתם חמדני הוא נכון היא יותר אמנות מאשר מדע. זה כרוך ביצירתיות רבה. בדרך כלל, לבוא עם אלגוריתם אולי נראה טריוויאלי, אבל להוכיח שהוא אכן נכון, זו בעיה אחרת לגמרי.
בעיית תזמון מרווחים
בואו נצלול לבעיה מעניינת שתוכלו להיתקל בה כמעט בכל תעשייה או בכל תחומי חיים. מקרים מסוימים של הבעיה הם כדלקמן:
- אתה מקבל קבוצה של לוחות זמנים של הרצאות ליום אחד באוניברסיטה. לוח הזמנים להרצאה ספציפית הוא של הטופס ( זמן, זמן f ) שבו הזמן מייצג את זמן ההתחלה של אותה הרצאה ובאופן דומה זמן f מייצג את זמן הסיום. בהינתן רשימת לוחות הזמנים של הרצאות N, עלינו לבחור מערך הרצאות מקסימלי שיתקיים במהלך היום כך שאף אחת מההרצאות אינה חופפת זו לזו, כלומר אם ההרצאה Li ו- Lj כלולה בבחירה שלנו, אז שעת ההתחלה של j > = זמן הסיום של i או להפך .
- חברך עובד כיועץ למחנה והוא אחראי על ארגון פעילויות עבור קבוצת חניכים. אחת מתוכניותיו היא תרגיל המיני-טריאתלון הבא: על כל מתמודד לשחות 20 הקפות בריכה, ואז לרכוב על אופניים 10 מייל ואז לרוץ 3 מיילים.
- התוכנית היא לשלוח את המתמודדים בצורה מזועזעת, דרך הכלל הבא: על המתמודדים להשתמש בבריכה אחד בכל פעם. במילים אחרות, המתמודד הראשון שוחה את 20 ההקפות, יוצא ומתחיל לרכוב על אופניים.
- ברגע שהאדם הראשון הזה יצא מהבריכה, מתמודד שני מתחיל לשחות את 20 ההקפות; ברגע שהוא או היא בחוץ ומתחילים לרכוב על אופניים, מתמודד שלישי מתחיל לשחות, וכן הלאה.
- לכל מתמודד זמן שחייה צפוי, זמן רכיבה צפוי וזמן ריצה צפוי. חברך רוצה להחליט על לוח הזמנים לטריאתלון: סדר בו רצף ההתחלות של המתמודדים.
- בואו נגיד שזמן השלמת לוח הזמנים הוא הזמן המוקדם ביותר בו כל המתמודדים יסיימו עם כל שלוש הרגליים של הטריאתלון, בהנחה שתחזיות הזמן מדויקות. מהו הסדר הטוב ביותר לשליחת אנשים, אם רוצים שכל התחרות תסתיים בהקדם האפשרי? ליתר דיוק, תן אלגוריתם יעיל שמייצר לוח זמנים שזמן השלמתו קטן ככל האפשר
בעיית תזמון ההרצאות
בואו נסתכל על הגישות השונות לפתרון בעיה זו.
שעת ההתחלה המוקדמת ראשונה כלומר בחר את המרווח שיש לו זמן ההתחלה המוקדם. התבונן בדוגמה הבאה השוברת פיתרון זה. פיתרון זה נכשל מכיוון שיכול להיות מרווח שמתחיל מוקדם מאוד אבל זה ארוך מאוד. פירוש הדבר שהאסטרטגיה הבאה שנוכל לנסות תהיה היכן שנראה קודם במרווחים קטנים יותר.
המרווח הקטן ביותר ראשית כלומר בסופו של דבר אתה בוחר את ההרצאות לפי מרווח הזמן הכולל שלהן שאינו אלא שלהן finish time - start time. שוב, פתרון זה אינו נכון. תסתכל על המקרה הבא.
אתה יכול לראות בבירור שהרצאת המרווחים הקצרה ביותר היא זו שבאמצע, אבל זה לא הפיתרון האופטימלי כאן. בואו נסתכל על פיתרון נוסף לבעיה זו המפיק תובנות מהפתרון הזה.
מרווח מתנגש לפחות, ראשית כלומר עליכם להסתכל על מרווחים הגורמים למספר הקונפליקטים הנמוך ביותר. שוב יש לנו דוגמה שבה גישה זו לא מצליחה למצוא פיתרון אופטימלי.
התרשים מראה לנו שהמרווח הפחות מתנגש הוא זה שבאמצע עם שני קונפליקטים בלבד. לאחר מכן נוכל לבחור רק את שני המרווחים בסוף עם קונפליקטים 3 כל אחד. אך הפיתרון האופטימלי הוא לבחור את 4 המרווחים ברמה העליונה ביותר.
שעת הגימור המוקדמת ראשונה . זו הגישה שתמיד נותנת לנו את הפיתרון האופטימלי ביותר לבעיה זו. השגנו הרבה תובנות מגישות קודמות ולבסוף הגענו לגישה זו. אנו ממיינים את המרווחים על פי סדר הגדלה של זמני הגימור שלהם ואז מתחילים לבחור מרווחים מההתחלה. עיין בקוד הפסאודו הבא לבהירות רבה יותר.
function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end מתי אנו משתמשים באלגוריתמים חמדניים
אלגוריתמים חמדניים יכולים לעזור לך למצוא פתרונות להרבה בעיות קשות לכאורה. הבעיה היחידה איתם היא שאולי תמצא את הפיתרון הנכון, אך ייתכן שלא תוכל לאמת אם הוא הנכון. כל הבעיות החמדניות חולקות רכוש משותף שאופטימה מקומית יכולה בסופו של דבר להוביל למינימום גלובלי מבלי לשקול מחדש את מערך הבחירות שכבר נשקלו.
אלגוריתמים חמדניים עוזרים לנו לפתור הרבה סוגים שונים של בעיות, כמו: