--- title: "Branch and bound — שיטת הענפים והגבולות" source: "https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA" wiki: "systems-analysis.info/int" article: "Branch_and_bound_—_שיטת_הענפים_והגבולות" language: "he" categories: - "Category:Hebrew" - "Category:Operations research" revision_id: 812 wiki_created_at: 2026-09-06T22:39:11Z wiki_modified_at: 2026-09-06T22:39:11Z downloaded_at: 2026-09-07T22:42:30Z --- # Branch and bound — שיטת הענפים והגבולות **שיטת הענפים והגבולות** (באנגלית: *Branch and Bound*, בקיצור **B&B** או **BnB**) היא פרדיגמה כללית לבניית אלגוריתמים מדויקים לפתרון בעיות אופטימיזציה דיסקרטית וקומבינטורית, ובפרט בעיות NP-קשות[\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-en-wiki-bnb-1). השיטה מהווה אסטרטגיית סריקה מכוונת, שבה כל קבוצת הפתרונות האפשריים מחולקת ברצף לתת-קבוצות (**ענפים**), ועבור כל אחת מהן מחושבות הערכות (**גבולות**) לערך פונקציית המטרה. הערכות אלו מאפשרות להשמיט (לגזום) אותן תת-קבוצות שבוודאות אינן מכילות פתרונות אופטימליים, מה שמצמצם משמעותית את מרחב החיפוש[\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-ru-wiki-bnb-2). השיטה הוצעה לראשונה על ידי א. לנד וא. דויג בשנת 1960 לפתרון בעיות תכנות שלמות[\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-land-doig-1960-3). מאז הפכה לאחד הגישות הבסיסיות ביותר בחקר פעולות ובמדעי המחשב. המאפיין המרכזי של השיטה הוא גמישותה: היא אינה אלגוריתם ספציפי, אלא מסגרת (framework) אסטרטגית ברמה גבוהה, המותאמת למבנה הבעיה הנפתרת. ## מרכיבים מרכזיים של השיטה בבסיס השיטה עומדות שלוש פעולות יסודיות, המיושמות על תת-קבוצות של מרחב הפתרונות, המאורגנות כעץ חיפוש. - **ענפים** (באנגלית: *Branching*) — תהליך החלוקה הרקורסיבית של קבוצת הפתרונות האפשריים הנוכחית $S_{i}$ למספר תת-קבוצות קטנות יותר, בדרך כלל זרות $S_{i1},S_{i2},\ldots,S_{ik}$. כל תת-קבוצה כזו מתאימה לתת-בעיה חדשה ומיוצגת כצומת בן בעץ החיפוש. לדוגמה, בבעיות תכנות שלמות, הענפים נוצרים לרוב לפי משתנה בעל ערך שבור בפתרון הרלקסציה הליניארית. - **חישוב גבולות** (באנגלית: *Bounding*) — עבור כל צומת בעץ החיפוש (כלומר, עבור כל תת-בעיה) מחושבת הערכה לערך פונקציית המטרה. עבור בעיית מינימום, זוהי **גבול תחתון** (*lower bound*), המהווה הערכה מובטחת מלמטה לכל פתרון בתת-קבוצה הנתונה. לרוב הערכה זו מתקבלת על ידי פתרון ה*רלקסציה* של תת-הבעיה המקורית — גרסה מפושטת שבה חלק מהאילוצים הקשים (כגון אילוץ שלמות) מוסרים זמנית. הנפוצה ביותר היא רלקסציה ליניארית (LP). - **גיזום** (באנגלית: *Pruning*) — תהליך הסרת צמתים (ועצי המשנה התואמים להם) מהשיקול, שבוודאות אינם יכולים להכיל פתרון אופטימלי. צומת נגזם באחד מהמקרים הבאים: 1. **גיזום לפי גבול**: הגבול התחתון של הצומת הנתון אינו טוב יותר (כלומר, גדול או שווה לבעיית מינימום) מערכו של הפתרון האפשרי הטוב ביותר שנמצא עד כה, המכונה **רקורד** (*incumbent*). 2. **גיזום לפי אפשרות**: פתרון הרלקסציה של הצומת אפשרי לבעיה המקורית (לדוגמה, כל המשתנים שלמים). פתרון זה מושווה לרקורד הנוכחי, ואם הוא טוב יותר, הרקורד מתעדכן. אין צורך בהמשך ענפים מצומת זה. 3. **גיזום לפי חוסר פתרון**: תת-הבעיה התואמת לצומת אינה מכילה פתרונות אפשריים. ## אלגוריתם כללי האלגוריתם המוכלל של שיטת הענפים והגבולות לבעיית מינימום ניתן לתיאור בשלבים הבאים: 1. **אתחול:** מציאת פתרון אפשרי ראשוני (לדוגמה, בעזרת היוריסטיקה) וקביעת ערכו כגבול עליון ראשוני (רקורד) $U$. יצירת תור של צמתים פעילים $Q$ המכיל את הצומת השורש (הבעיה המקורית). 2. **לולאה ראשית:** כל עוד התור $Q$ אינו ריק: - בחירת צומת מתוך $Q$ בהתאם לאסטרטגיית החיפוש (לדוגמה, חיפוש לעומק או לפי הערכה הטובה ביותר). - פתרון הרלקסציה לצומת זה, תוך קבלת גבול תחתון $L$. - **גיזום** הצומת, אם $L \geq U$. - אם פתרון הרלקסציה אפשרי לבעיה המקורית, עדכון הרקורד: $U\leftarrow L$. - אם הצומת לא נגזם והפתרון אינו אפשרי, ביצוע **ענפים**, חלוקתו לצמתים בנים והוספתם לתור $Q$. 3. **סיום:** כאשר התור $Q$ מתרוקן, האלגוריתם מסתיים. הפתרון שנמצא, המתאים לרקורד $U$, הוא האופטימום הגלובלי. ## תכונות ומשפטים מרכזיים - **נכונות והתכנסות:** האלגוריתם מבטיח מציאת פתרון אופטימלי גלובלי במספר סופי של צעדים, בתנאי שקבוצת הפתרונות האפשריים סופית ושנוהל הענפים הוא מתכנס (כלומר, שבחלוקה רקורסיבית תת-הקבוצות "מתכווצות" לנקודות)[\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-conitzer-duke-4). - **אסטרטגיית חיפוש:** יעילות האלגוריתם תלויה מאוד באסטרטגיית בחירת הצומת הבא לענפים (לדוגמה, חיפוש לעומק, חיפוש לרוחב, חיפוש לפי ההערכה הטובה ביותר) ובבחירת המשתנה לענפים. פותרים מודרניים משתמשים לרוב באסטרטגיות היברידיות[\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-maudet-danoy-2024-5). ## דוגמאות - **בעיית תכנות שלמות**: יישום קלאסי של השיטה. כרלקסציה משמשת תכנות ליניארי. הענפים נוצרים לפי משתנה שבור $x_{j}$, תוך יצירת שתי תת-בעיות עם אילוצים נוספים $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ ו-$x_{j} \geq \lceil x_{j}^{\ast}\rceil$. - **בעיית הסוכן הנוסע**: מרחב הפתרונות הוא כל מחזורי ההמילטון האפשריים בגרף. הענפים יכולים להתבצע לפי קשתות (הכללת/הסרת קשת מהמסלול). כגבולות תחתונים ניתן להשתמש בפתרונות בעיות פשוטות יותר, כגון בעיית ההקצאה או בניית עץ פורש מינימלי[\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-little-1963-6). ## מושגים קשורים ויישומים - **שיטת הענפים והחתכים** (*Branch-and-Cut*): שיטה היברידית המשלבת B&B עם שיטת המישורים החותכים. בכל צומת של עץ החיפוש, בנוסף לפתרון הרלקסציה, נוצרים אי-שוויונות נוספים (חתכים) המחזקים את הגבול התחתון, מה שמוביל לגיזום יעיל יותר של ענפים. - **חיפוש עם נסיגה** (*Backtracking*): שיטת הענפים והגבולות ניתן לראות כהכללה של אלגוריתם זה לבעיות אופטימיזציה. - **קיצוץ אלפא-בטא**: אנלוגיה מושגית המשמשת בעצי משחק לגיזום ענפים שהפסדם ודאי. ## ראו גם - תכנות שלמות - אופטימיזציה קומבינטורית - בעיית הסוכן הנוסע - בעיה NP-קשה - שיטת הסימפלקס ## הערות [\[1\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-en-wiki-bnb-1) [\[2\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-ru-wiki-bnb-2) [\[3\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-land-doig-1960-3) [\[4\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-conitzer-duke-4) [\[5\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-maudet-danoy-2024-5) [\[6\]](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_note-little-1963-6) \ 1. ↑ [1.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-en-wiki-bnb_1-0) [1.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-en-wiki-bnb_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](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-ru-wiki-bnb_2-0) [2.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-ru-wiki-bnb_2-1) Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ 3. ↑ [3.0](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-land-doig-1960_3-0) [3.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-land-doig-1960_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](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-conitzer-duke_4-0) [4.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-conitzer-duke_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](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-maudet-danoy-2024_5-0) [5.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-maudet-danoy-2024_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](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-little-1963_6-0) [6.1](https://systems-analysis.info/int/Branch_and_bound_%E2%80%94_%D7%A9%D7%99%D7%98%D7%AA_%D7%94%D7%A2%D7%A0%D7%A4%D7%99%D7%9D_%D7%95%D7%94%D7%92%D7%91%D7%95%D7%9C%D7%95%D7%AA#cite_ref-little-1963_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