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

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

המתמטיקאי ג'יימס מאנקרס  שבחן את האלגוריתם בשנת 1957, מצא שרמת הסיבוכיות שלו היא פולינומית. האלגוריתם ידוע מאז גם בשם אלגוריתם קון-מאנקרס או אלגוריתם ההשמה של מאנקרס. בשנת 2006 התגלה כי קרל גוסטב יעקובי פתר את בעיית ההשמה כבר במאה ה-19, והפתרון פורסם לאחר מותו ב-1890 בלטינית.
 הבעיה הבסיסית 
 דוגמה 
בדוגמה פשוטה זו ישנם שלושה אחים: אפרים, מאיר וישראל. אחד מהם צריך לנקות את חדר השינה, שני לטאטא את החצר ושלישי לשטוף את החלונות. כל אחד מהם דורש תשלום שונה עבור כל משימה. המטרה היא למצוא את השיבוץ שייתן את העלות הנמוכה ביותר לביצוע שלוש המשימות. את הבעיה ניתן לייצג במטריצה של עלויות העובדים לביצוע המשימות:
 לנקות חדר לטאטא חצר לשטוף חלונות אפרים 2 3 3 מאיר 3 2 3 ישראל 3 3 2
יישום האלגוריתם ההונגרי על המטריצה ייתן את העלות המינימלית שהיא 6, עלות זו מושגת על ידי שיבוצו של אפרים לניקוי החדר, של מאיר לטאטוא החצר ושל ישראל לשטיפת החלונות.

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

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

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

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

 אלגוריתם למציאת מספר קווים מינימלי לכיסוי האפסים 

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

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

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

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

 שלב 3: העברת מספר קווים מינימלי לכיסוי האפסים 
 שלב 3.1: סימון השורות שללא שיבוץ 

m1m2m3m4j1131408j24001240*j3664066j401900

 שלב 3.2: סימון עמודות שלהן אפסים בשורות מסומנות 
m1m2*m3m4j1131408j24001240*j3664066j401900

 שלב 3.3: סימון שורות עם שיבוץ בעמודות מסומנות 
m1m2*m3m4*j1131408j24001240*j3664066j401900

 שלב 3.4: חזרה על שלבים 2–3 עד שאין שינוי 
אין יותר עמודות שלהן אפסים בשורות מסומנות.

 שלב 3.5: העברת קווים על העמודות המסומנות והשורות הלא מסומנות 
נסמן את המחיקות בצהוב.
m1m2*m3m4*j1131408j24001240*j3664066j401900
את האלמנט המינימלי שלא מכוסה (6), מוסיפים לצמתים ומחסירים מהלא מכוסים:
m1m2m3m4j17802j24001840j3058060j401960
כעת ישנו שיבוץ חד-חד ערכי ולכן אין צורך לחזור על שלב 3. השיבוץ והעלויות (מהמטריצה ההתחלתית):
 את j1 נשבץ ל-m3 בעלות של 69
 את j2 נשבץ ל-m2 בעלות של 37
 את j3 נשבץ ל-m1 בעלות של 11
 את j4 נשבץ ל-m4 בעלות של 23

סך העלות: 140

הערות שוליים

קטגוריה:אלגוריתמים