Branch and bound — שיטת הענפים והגבולות

From Systems analysis Wiki
Jump to navigation Jump to search

שיטת הענפים והגבולות (באנגלית: Branch and Bound, בקיצור B&B או BnB) היא פרדיגמה כללית לבניית אלגוריתמים מדויקים לפתרון בעיות אופטימיזציה דיסקרטית וקומבינטורית, ובפרט בעיות NP-קשות[1]. השיטה מהווה אסטרטגיית סריקה מכוונת, שבה כל קבוצת הפתרונות האפשריים מחולקת ברצף לתת-קבוצות (ענפים), ועבור כל אחת מהן מחושבות הערכות (גבולות) לערך פונקציית המטרה. הערכות אלו מאפשרות להשמיט (לגזום) אותן תת-קבוצות שבוודאות אינן מכילות פתרונות אופטימליים, מה שמצמצם משמעותית את מרחב החיפוש[2].

השיטה הוצעה לראשונה על ידי א. לנד וא. דויג בשנת 1960 לפתרון בעיות תכנות שלמות[3]. מאז הפכה לאחד הגישות הבסיסיות ביותר בחקר פעולות ובמדעי המחשב. המאפיין המרכזי של השיטה הוא גמישותה: היא אינה אלגוריתם ספציפי, אלא מסגרת (framework) אסטרטגית ברמה גבוהה, המותאמת למבנה הבעיה הנפתרת.

מרכיבים מרכזיים של השיטה

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

  • ענפים (באנגלית: Branching) — תהליך החלוקה הרקורסיבית של קבוצת הפתרונות האפשריים הנוכחית Si למספר תת-קבוצות קטנות יותר, בדרך כלל זרות Si1,Si2,…,Sik. כל תת-קבוצה כזו מתאימה לתת-בעיה חדשה ומיוצגת כצומת בן בעץ החיפוש. לדוגמה, בבעיות תכנות שלמות, הענפים נוצרים לרוב לפי משתנה בעל ערך שבור בפתרון הרלקסציה הליניארית.
  • חישוב גבולות (באנגלית: Bounding) — עבור כל צומת בעץ החיפוש (כלומר, עבור כל תת-בעיה) מחושבת הערכה לערך פונקציית המטרה. עבור בעיית מינימום, זוהי גבול תחתון (lower bound), המהווה הערכה מובטחת מלמטה לכל פתרון בתת-קבוצה הנתונה. לרוב הערכה זו מתקבלת על ידי פתרון הרלקסציה של תת-הבעיה המקורית — גרסה מפושטת שבה חלק מהאילוצים הקשים (כגון אילוץ שלמות) מוסרים זמנית. הנפוצה ביותר היא רלקסציה ליניארית (LP).
  • גיזום (באנגלית: Pruning) — תהליך הסרת צמתים (ועצי המשנה התואמים להם) מהשיקול, שבוודאות אינם יכולים להכיל פתרון אופטימלי. צומת נגזם באחד מהמקרים הבאים:
  1. גיזום לפי גבול: הגבול התחתון של הצומת הנתון אינו טוב יותר (כלומר, גדול או שווה לבעיית מינימום) מערכו של הפתרון האפשרי הטוב ביותר שנמצא עד כה, המכונה רקורד (incumbent).
  2. גיזום לפי אפשרות: פתרון הרלקסציה של הצומת אפשרי לבעיה המקורית (לדוגמה, כל המשתנים שלמים). פתרון זה מושווה לרקורד הנוכחי, ואם הוא טוב יותר, הרקורד מתעדכן. אין צורך בהמשך ענפים מצומת זה.
  3. גיזום לפי חוסר פתרון: תת-הבעיה התואמת לצומת אינה מכילה פתרונות אפשריים.

אלגוריתם כללי

האלגוריתם המוכלל של שיטת הענפים והגבולות לבעיית מינימום ניתן לתיאור בשלבים הבאים:

  1. אתחול: מציאת פתרון אפשרי ראשוני (לדוגמה, בעזרת היוריסטיקה) וקביעת ערכו כגבול עליון ראשוני (רקורד) U. יצירת תור של צמתים פעילים Q המכיל את הצומת השורש (הבעיה המקורית).
  2. לולאה ראשית: כל עוד התור Q אינו ריק:
    • בחירת צומת מתוך Q בהתאם לאסטרטגיית החיפוש (לדוגמה, חיפוש לעומק או לפי הערכה הטובה ביותר).
    • פתרון הרלקסציה לצומת זה, תוך קבלת גבול תחתון L.
    • גיזום הצומת, אם L≥U.
    • אם פתרון הרלקסציה אפשרי לבעיה המקורית, עדכון הרקורד: U←L.
    • אם הצומת לא נגזם והפתרון אינו אפשרי, ביצוע ענפים, חלוקתו לצמתים בנים והוספתם לתור Q.
  3. סיום: כאשר התור Q מתרוקן, האלגוריתם מסתיים. הפתרון שנמצא, המתאים לרקורד U, הוא האופטימום הגלובלי.

תכונות ומשפטים מרכזיים

  • נכונות והתכנסות: האלגוריתם מבטיח מציאת פתרון אופטימלי גלובלי במספר סופי של צעדים, בתנאי שקבוצת הפתרונות האפשריים סופית ושנוהל הענפים הוא מתכנס (כלומר, שבחלוקה רקורסיבית תת-הקבוצות "מתכווצות" לנקודות)[4].
  • אסטרטגיית חיפוש: יעילות האלגוריתם תלויה מאוד באסטרטגיית בחירת הצומת הבא לענפים (לדוגמה, חיפוש לעומק, חיפוש לרוחב, חיפוש לפי ההערכה הטובה ביותר) ובבחירת המשתנה לענפים. פותרים מודרניים משתמשים לרוב באסטרטגיות היברידיות[5].

דוגמאות

  • בעיית תכנות שלמות: יישום קלאסי של השיטה. כרלקסציה משמשת תכנות ליניארי. הענפים נוצרים לפי משתנה שבור xj, תוך יצירת שתי תת-בעיות עם אילוצים נוספים xj≤⌊xj∗⌋ ו-xj≥⌈xj∗⌉.
  • בעיית הסוכן הנוסע: מרחב הפתרונות הוא כל מחזורי ההמילטון האפשריים בגרף. הענפים יכולים להתבצע לפי קשתות (הכללת/הסרת קשת מהמסלול). כגבולות תחתונים ניתן להשתמש בפתרונות בעיות פשוטות יותר, כגון בעיית ההקצאה או בניית עץ פורש מינימלי[6].

מושגים קשורים ויישומים

  • שיטת הענפים והחתכים (Branch-and-Cut): שיטה היברידית המשלבת B&B עם שיטת המישורים החותכים. בכל צומת של עץ החיפוש, בנוסף לפתרון הרלקסציה, נוצרים אי-שוויונות נוספים (חתכים) המחזקים את הגבול התחתון, מה שמוביל לגיזום יעיל יותר של ענפים.
  • חיפוש עם נסיגה (Backtracking): שיטת הענפים והגבולות ניתן לראות כהכללה של אלגוריתם זה לבעיות אופטימיזציה.
  • קיצוץ אלפא-בטא: אנלוגיה מושגית המשמשת בעצי משחק לגיזום ענפים שהפסדם ודאי.

ראו גם

  • תכנות שלמות
  • אופטימיזציה קומבינטורית
  • בעיית הסוכן הנוסע
  • בעיה NP-קשה
  • שיטת הסימפלקס

הערות

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 3.0 3.1 Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ 4.0 4.1 Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ 5.0 5.1 Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ 6.0 6.1 Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.info/int/index.php?title=Branch_and_bound_—_שיטת_הענפים_והגבולות&oldid=812"