Вопросы к Поиску с Алисой
В чем заключается метод ветвей и границ в дискретном программировании?
Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. ru.wikipedia.org
Суть метода заключается в упорядоченном переборе вариантов, рассмотрении лишь тех из них, которые оказываются по определённым признакам перспективными, и отбрасывании бесперспективных вариантов. studizba.com
В основе метода лежит идея последовательного разбиения множества допустимых решений на подмножества. studizba.com old.math.nsc.ru На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. studizba.com old.math.nsc.ru
Для метода ветвей и границ необходимы две процедуры: ru.wikipedia.org
- Ветвление. ru.wikipedia.org Множество допустимых значений переменной разбивается на подобласти (подмножества) меньших размеров. ru.wikipedia.org Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. ru.wikipedia.org
- Нахождение оценок (границ). ru.wikipedia.org Заключается в поиске верхних и нижних границ для решения задачи на подобласти допустимых значений переменной. ru.wikipedia.org
В основе метода лежит следующая идея: если нижняя граница значений функции на подобласти дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти, то первая может быть исключена из дальнейшего рассмотрения. ru.wikipedia.org
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти. ru.wikipedia.org
Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. ru.wikipedia.org
