האלגוריתם ההונגרי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

האלגוריתם ההונגרי היא אלגוריתם אופטימיזציה שפותר את בעיית ההשמה בזמן פולינומי. הוא פותח ופורסם ב-1955 על ידי הרולד קון(אנ'), שנתן לאלגוריתם את השם "השיטה ההונגרית" משום שהוא התבסס במידה רבה על עבודה קודמת של שני מתמטיקאים הונגריים: דנס קוניג (אנ') ויאנו איגרווארי(אנ').[1][2]

המתמטיקאי ג'יימס מאנקרס (אנ') שבחן את האלגוריתם בשנת 1957, מצא שרמת הסיבוכיות שלו היא פולינומית.[3] האלגוריתם ידוע מאז גם בשם אלגוריתם קון-מאנקרס או אלגוריתם ההשמה של מאנקרס. בשנת 2006 התגלה כי קרל גוסטב יעקבי פתר את בעיית ההשמה כבר במאה ה-19, והפתרון פורסם לאחר מותו ב-1890 בלטינית.[4]

הבעיה הבסיסית[עריכת קוד מקור | עריכה]

דוגמה[עריכת קוד מקור | עריכה]

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

לנקות חדר לטאטא חצר לשטוף חלונות
אפרים 2 3 3
מאיר 3 2 3
ישראל 3 3 2

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

ישנן שתי דרכים לנסח את הבעיה: כמטריצה וכגרף דו-צדדי (bipartite graph).

ניסוח כמטריצה[עריכת קוד מקור | עריכה]

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

ניסוח כגרף דו-צדדי[עריכת קוד מקור | עריכה]

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

האלגוריתם לפתרון הניסוח כמטריצה[עריכת קוד מקור | עריכה]

נתונה מטריצה של עובדים ומשימות המכילה את העלויות לשיבוץ עובד למשימה. שלבי האלגוריתם הם:

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

אלגוריתם למציאת מספר קווים מינימלי לכיסוי האפסים[עריכת קוד מקור | עריכה]

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

דוגמה[עריכת קוד מקור | עריכה]

נתונה מטריצת עלויות שיבוץ של 4 עובדים (j1, j2, j3, j4) ל-4 משימות (m1, m2, m3, m4).

m1 m2 m3 m4
j1 82 83 69 92
j2 77 37 49 92
j3 11 69 5 86
j4 8 9 98 23

מצאו את השיבוץ שיביא את סך העלויות למינימום.

שלב 1: הפחתת האלמנט המינימלי מכל שורה[עריכת קוד מקור | עריכה]

m1 m2 m3 m4
j1 13 14 0 23
j2 40 0 12 55
j3 6 64 0 81
j4 0 1 90 15

אין שיבוץ חד-חד ערכי (למשימה 3 משובצים שני עובדים ואין שיבוץ למשימה 4)

שלב 2: הפחתת האלמנט המינימלי מכל עמודה[עריכת קוד מקור | עריכה]

m1 m2 m3 m4
j1 13 14 0 8
j2 40 0 12 40
j3 6 64 0 66
j4 0 1 90 0

אין שיבוץ חד-חד ערכי (עובדים 1 ו-3 משובצים לאותה משימה ללא אפשרות אחרת)

שלב 3: העברת מספר קווים מינימלי לכיסוי האפסים[עריכת קוד מקור | עריכה]

שלב 3.1: סימון השורות שללא שיבוץ[עריכת קוד מקור | עריכה]

m1 m2 m3 m4
j1 13 14 0 8
j2 40 0 12 40
*j3 6 64 0 66
j4 0 1 90 0
שלב 3.2: סימון עמודות שלהן אפסים בשורות מסומנות[עריכת קוד מקור | עריכה]

m1 m2 *m3 m4
j1 13 14 0 8
j2 40 0 12 40
*j3 6 64 0 66
j4 0 1 90 0
שלב 3.3: סימון שורות עם שיבוץ בעמודות מסומנות[עריכת קוד מקור | עריכה]

m1 m2 *m3 m4
*j1 13 14 0 8
j2 40 0 12 40
*j3 6 64 0 66
j4 0 1 90 0
שלב 3.4: חזרה על שלבים 2–3 עד שאין שינוי[עריכת קוד מקור | עריכה]

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

שלב 3.5: העברת קווים על העמודות המסומנות והשורות הלא מסומנות[עריכת קוד מקור | עריכה]

נסמן את המחיקות בצהוב

m1 m2 *m3 m4
*j1 13 14 0 8
j2 40 0 12 40
*j3 6 64 0 66
j4 0 1 90 0

את האלמנט המינימלי שלא מכוסה (6), מוסיפים לצמתים ומחסירים מהלא מכוסים:

m1 m2 m3 m4
j1 7 8 0 2
j2 40 0 18 40
j3 0 58 0 60
j4 0 1 96 0

כעת ישנו שיבוץ חד-חד ערכי ולכן אין צורך לחזור על שלב 3. השיבוץ והעלויות (מהמטריצה ההתחלתית):

  • את j1 נשבץ ל-m3 בעלות של 69
  • את j2 נשבץ ל-m2 בעלות של 37
  • את j3 נשבץ ל-m1 בעלות של 11
  • את j4 נשבץ ל-m4 בעלות של 23

סך העלות: 130

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ H. W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics 52, 2005-2, עמ' 7–21 doi: 10.1002/nav.20053
  2. ^ H. W. Kuhn, Variants of the hungarian method for assignment problems, Naval Research Logistics Quarterly 3, 1956-12, עמ' 253–258 doi: 10.1002/nav.3800030404
  3. ^ James Munkres, Algorithms for the Assignment and Transportation Problems, Journal of the Society for Industrial and Applied Mathematics 5, 1957-3, עמ' 32–38 doi: 10.1137/0105003
  4. ^ Jacobi's bound, www.lix.polytechnique.fr