---
title: "Метод на клоните и границите"
source: "https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5"
wiki: "systems-analysis.info/int"
article: "Метод_на_клоните_и_границите"
language: "bg"
categories:
  - "Category:Bulgarian"
  - "Category:Operations research"
revision_id: 8699
wiki_created_at: 2026-09-07T01:21:20Z
wiki_modified_at: 2026-09-07T01:21:20Z
downloaded_at: 2026-09-07T23:26:53Z
---

# Метод на клоните и границите

**Методът на клоните и границите** (англ. *Branch and Bound*, съкр. **B&B** или **BnB**) е обща парадигма за изграждане на точни алгоритми за решаване на задачи от дискретна и комбинаторна оптимизация, по-специално NP-трудни задачи<sup>[\[1\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-en-wiki-bnb-1)</sup>. Методът представлява стратегия за насочено изчерпване, при която цялото множество от допустими решения последователно се разделя на подмножества (**разклоняване**), а за всяко от тях се изчисляват оценки (**граници**) на стойността на целевата функция. Тези оценки позволяват да се отхвърлят (отрязват) онези подмножества, които очевидно не съдържат оптимални решения, което съществено намалява пространството за търсене<sup>[\[2\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-ru-wiki-bnb-2)</sup>.

Методът е предложен за първи път от А. Ленд и А. Дойг през 1960 година за решаване на задачи от целочислено програмиране<sup>[\[3\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-land-doig-1960-3)</sup>. Оттогава той се превърна в един от най-фундаменталните подходи в изследването на операциите и компютърните науки. Ключова особеност на метода е неговата гъвкавост: той не е конкретен алгоритъм, а стратегическа схема от високо ниво (framework), адаптивна към структурата на решаваната задача.

## Ключови компоненти на метода

В основата на метода лежат три фундаментални операции, приложими към подмножества от пространството на решенията, организирани като дърво за търсене.

- **Разклоняване** (англ. *Branching*) — това е процес на рекурсивно разделяне на текущото множество от допустими решения $S_{i}$ на няколко по-малки, като правило непресичащи се подмножества $S_{i1},S_{i2},\ldots,S_{ik}$. Всяко такова подмножество съответства на нова подзадача и се представя като дъщерен възел в дървото за търсене. Например, в задачите на целочислено програмиране разклоняването често се извършва по променлива, която има дробна стойност в решението на LP-релаксацията.

<!-- -->

- **Оценка на границите** (англ. *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$, е глобално оптимално.

## Ключови свойства и теореми

- **Коректност и сходимост:** Алгоритъмът гарантирано намира глобално оптимално решение за краен брой стъпки, ако множеството от допустими решения е крайно, а процедурата за разклоняване е сходяща (т.е. при рекурсивно разбиване подмножествата се „свиват" към точки)<sup>[\[4\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-conitzer-duke-4)</sup>.
- **Стратегия за търсене:** Ефективността на алгоритъма силно зависи от стратегията за избор на следващия възел за разклоняване (например търсене в дълбочина, търсене в ширина, търсене по най-добра оценка) и от избора на променлива за разклоняване. Съвременните решатели (solvers) често използват хибридни стратегии<sup>[\[5\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-maudet-danoy-2024-5)</sup>.

## Примери

- **Задача за целочислено програмиране**: Класическо приложение на метода. Като релаксация се използва линейно програмиране. Разклоняването се извършва по дробна променлива $x_{j}$, създавайки две подзадачи с допълнителни ограничения $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ и $x_{j} \geq \lceil x_{j}^{\ast}\rceil$.
- **Задача на търговския пътник**: Пространството на решенията са всички възможни хамилтонови цикли в графа. Разклоняването може да се извършва по ребра (включване/изключване на ребро от маршрута). Като долни граници могат да се използват решения на по-прости задачи, като задачата за назначаване или изграждане на минимално покриващо дърво<sup>[\[6\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-little-1963-6)</sup>.

## Свързани понятия и приложения

- **Метод на клоните и отрязванията** (*Branch-and-Cut*): Хибриден метод, обединяващ B&B с метода на отсичащите равнини. На всеки възел от дървото за търсене, освен решаване на релаксацията, се генерират допълнителни неравенства (отрязвания), които усилват долната граница, което води до по-ефективно отрязване на клони.
- **Търсене с връщане** (*Backtracking*): Методът на клоните и границите може да се разглежда като обобщение на този алгоритъм за задачи за оптимизация.
- **Алфа-бета отрязване**: Концептуална аналогия, използвана в игрови дървета за отрязване на заведомо губещи клони.

## Вижте също

- Целочислено програмиране
- Комбинаторна оптимизация
- Задача на търговския пътник
- NP-трудна задача
- Симплекс метод

## Бележки

<sup>[\[1\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-en-wiki-bnb-1)</sup> <sup>[\[2\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-ru-wiki-bnb-2)</sup> <sup>[\[3\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-land-doig-1960-3)</sup> <sup>[\[4\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-conitzer-duke-4)</sup> <sup>[\[5\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-maudet-danoy-2024-5)</sup> <sup>[\[6\]](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_note-little-1963-6)</sup> \</references\>

1.  <span id="cite_note-en-wiki-bnb-1">↑ <sup>[1.0](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-en-wiki-bnb_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-en-wiki-bnb_1-1)</sup> Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from <a href="https://en.wikipedia.org/wiki/Branch_and_bound" class="external free" rel="nofollow">https://en.wikipedia.org/wiki/Branch_and_bound</a></span>
2.  <span id="cite_note-ru-wiki-bnb-2">↑ <sup>[2.0](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-ru-wiki-bnb_2-0)</sup> <sup>[2.1](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-ru-wiki-bnb_2-1)</sup> Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from <a href="https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ" class="external free" rel="nofollow">https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ</a></span>
3.  <span id="cite_note-land-doig-1960-3">↑ <sup>[3.0](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-land-doig-1960_3-0)</sup> <sup>[3.1](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-land-doig-1960_3-1)</sup> 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: <a href="https://www.jstor.org/stable/1910129" class="external free" rel="nofollow">https://www.jstor.org/stable/1910129</a></span>
4.  <span id="cite_note-conitzer-duke-4">↑ <sup>[4.0](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-conitzer-duke_4-0)</sup> <sup>[4.1](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-conitzer-duke_4-1)</sup> Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: <a href="https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf" class="external free" rel="nofollow">https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf</a></span>
5.  <span id="cite_note-maudet-danoy-2024-5">↑ <sup>[5.0](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-maudet-danoy-2024_5-0)</sup> <sup>[5.1](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-maudet-danoy-2024_5-1)</sup> 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: <a href="https://arxiv.org/abs/2412.09444" class="external free" rel="nofollow">https://arxiv.org/abs/2412.09444</a></span>
6.  <span id="cite_note-little-1963-6">↑ <sup>[6.0](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-little-1963_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0_%D0%BA%D0%BB%D0%BE%D0%BD%D0%B8%D1%82%D0%B5_%D0%B8_%D0%B3%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D0%B8%D1%82%D0%B5#cite_ref-little-1963_6-1)</sup> 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: <a href="https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf" class="external free" rel="nofollow">https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf</a></span>