Метод ветвей и границ

Метод ветвей и границметод решения переборных задач.

В основе этого метода лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия «разделяй и властвуй»). Метод ветвей и границ - общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод был сначала предложен A. H. Land и A. G. Doig в 1960 г. для решения задач целочисленного линейного программирования.

Общее описание

Общая идея метода может быть описана на примере нахождения решения задачи минимизации функции f(x) по множеству допустимых решений x. Как f, так и x могут быть произвольными. Метод ветвей и границ использует две процедуры: ветвление и нахождение оценок (границ). Ветвление покрывает область допустимых решений областями допустимых решений меньших размеров. Процедура называется ветвлением, так как она повторяется рекурсивным образом далее к каждой из полученных подобластей, образуя дерево, называемое деревом поиска или деревом ветвей и границ. Вершины этого дерева соответствуют построенным подобластям. Другая процедура — нахождение оценок, которая является быстрым методом нахождения верхних и нижних границ оптимального решения в подобласти допустимых решений.

В основе метода ветвей и границ лежит простое наблюдение, что если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения. Это обычно выполняется с помощью глобальной переменной m, в которой запоминается минимальная верхняя граница, полученная для всех просмотренных до настоящего времени вариантах; любая вершина дерева поиска, нижняя граница которой больше m, может быть исключена из дальнейшего рассмотрения.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home