В чём заключается суть метода ветвей и границ?

Суть метода ветвей и границ (англ. branch and bound) — нахождение оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. ru.ruwiki.ru ru.wikipedia.org

Метод основан на систематическом перечислении кандидатов решения с отсечением подмножеств, не содержащих оптимального решения. ai.mitup.ru

Метод включает две ключевые операции: ai.mitup.ru

1. Ветвление. ru.ruwiki.ru ai.mitup.ru Множество решений разбивается на подмножества меньших размеров. ru.ruwiki.ru ai.mitup.ru Полученные подобласти образуют дерево поиска или дерево ветвей и границ. ru.ruwiki.ru
2. Оценка границ. ai.mitup.ru Вычисляются верхние и нижние оценки целевой функции для каждого подмножества. ai.mitup.ru

В основе метода лежит правило отсева: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти, то первая подобласть исключается из дальнейшего рассмотрения. ru.ruwiki.ru ru.wikipedia.org

Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. ru.ruwiki.ru

Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. ru.ruwiki.ru ru.wikipedia.org