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

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

ממציא	הרולד קון

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

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

הבעיה הבסיסית

דוגמה

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

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

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

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

ניסוח כמטריצה

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

ניסוח כגרף דו-צדדי

קל לתאר את האלגוריתם גם באמצעות ניסוח הבעיה כגרף. נגדיר גרף דו-צדדי שלם בו כל קודקוד בקבוצה הראשונה מחובר לקודקוד בקבוצה השנייה $G=\left(S,T;E\right)$ עם $n$ קודקודי עובדים $(S)$ ו-$n$ קודקודי עבודות $(T)$. לכל קשת בקבוצת הקשתות $(E)$ ישנה עלות לא שלילית של $c(i,j)$. אנחנו רוצים למצוא שידוך עם עלות כוללת מינימלית.

האלגוריתם לפתרון הניסוח כמטריצה

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

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

סך העלות: 140

הערות שוליים

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