כיצד להשתמש באלגוריתם ההונגרי?
מהו האלגוריתם לכסות את האלמנטים האפסיים עם מספר השורות המינימלי?
האלגוריתם ההונגרי מאפשר למצוא "התאמה מינימלית". ניתן להשתמש בכך במקרים שבהם יש הצעות מחיר מרובות לקבוצת פעילויות וכל פעילות חייבת להיעשות על ידי אדם אחר, כדי למצוא את העלות המינימלית להשלמת כל הפעילויות.
- 1סדרו את המידע שלכם במטריצה עם ה"אנשים "משמאל ו"הפעילות" לאורך החלק העליון, עם ה"עלות "לכל זוג באמצע.
- 2ודא שהמטריצה מרובעת על ידי הוספת שורות / עמודות דמה במידת הצורך. באופן מקובל, כל אלמנט בשורה / העמודה הדמה זהה למספר הגדול ביותר במטריצה.
- 3צמצמו את השורות על ידי הפחתת הערך המינימלי של כל שורה מאותה שורה.
- 4אם יש עמודות ללא אפס, הפחת את העמודות על ידי הפחתת הערך המינימלי של כל עמודה מאותה עמודה.
- 5מכסים את האלמנטים האפסיים במספר השורות המינימלי שאפשר לכסות עליהם. (אם מספר השורות שווה למספר השורות, עבור לשלב 9)
אתה יכול להשתמש באלגוריתם של פלויד-ורשל כדי לחשב את הנתיב הקצר ביותר מכל צומת לכל צומת. - 6הוסף את האלמנט המינימלי שלא נחשף לכל אלמנט מכוסה. אם אלמנט מכוסה פעמיים, הוסף אליו את האלמנט המינימלי פעמיים.
- 7מחסרים את האלמנט המינימלי מכל אלמנט במטריצה.
- 8מכסים את אפס האלמנטים שוב. אם מספר השורות המכסות את רכיבי האפס אינו שווה למספר השורות, חזור לשלב 6.
- 9בחר התאמה על ידי בחירה בקבוצת אפסים כך שכל שורה או עמודה יבחרו רק אחת.
- 10החל את ההתאמה על המטריצה המקורית, תוך התעלמות משורות הדמה. זה מראה מי צריך לעשות איזו פעילות, והוספת העלויות תתן את העלות המינימלית הכוללת.
- אם ברצונך למצוא התאמה מקסימאלית ולא מינימלית, הכפל כל מספר ב -1 בשלב 1, ולאחר מכן בצע את השלבים ככתוב.
- תובנה מרכזית כאן היא שהוספת אותו מספר לכל הערכים בשורה אחת או בעמודה של המטריצה מייצרת מטריצה חדשה עם אותו פתרון אופטימלי. זה מה שמאפשר לנו לברוח מהפחתת המטריצה בשלב 6.
- עיתון
- עט עפרון
קרא גם: כיצד למצוא ממוצע, חציון ומצב
שאלות ותשובות
- האם ניתן לבצע את צמצום העמודות ראשונה ואת צמצום השורה שניה?לא, מכיוון שהערכים משתנים באופן דרמטי ובכך משנים את המשוואה ואת הפתרון.
- כיצד מיישמים את השיטה ההונגרית לקבלת פתרון אם המטריצה היא מלבן?תחילה הוסף שורות "דמה" או עמודות כדי להפוך אותה לריבועית, כאשר הערך "דמה" הוא הערך הגבוה ביותר מאותה עמודה או שורה, בהתאמה.
- במה נבדלים האלגוריתמים של דייקסטרה ופלויד?באפשרותך להשתמש באלגוריתם Dijkstra כדי לחשב את הנתיב הקצר ביותר מצומת המקור לכל צומת אחר. אתה יכול להשתמש באלגוריתם של פלויד-ורשל כדי לחשב את הנתיב הקצר ביותר מכל צומת לכל צומת. אל תשתמש ב- Dijkstra אם יש קשתות עם משקל שלילי. אם יש מחזור שלילי בגרף שלך, אינך יכול להשתמש באלגוריתם פולינום.
שאלות ללא מענה
- מה עלי לעשות אם למקורות מסוימים אין ערך עבור יעד מסוים בעת שימוש באלגוריתם ההונגרי?
- מהו האלגוריתם לכסות את האלמנטים האפסיים עם מספר השורות המינימלי?
