Метод ветвей и границ применим в том случае

Пусть — конечное множество и  — вещественнозначная функция на нем; требуется найти минимум  этой функции и элемент множества, на котором этот минимум  достигается.

Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора элементов всего множества M. Но чаще  всего полный перебор производить приходится. В этом случае  обязательно возникает задача, как лучше перебор организовать.

Метод ветвей и границ применим в том случае, когда  выполняются специфические дополнительные условия на множество Mи минимизируемой на нем функции. А именно, —  предположим, что имеется вещественно — значная функция j на множестве подмножеств множества M со следующими двумя свойствами:

·        для  ,

 где {mi} — множество, состоящее  из единственного элемента  mi;

·        если  и , то .

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:  разобьем множество M на части (любым способом) и выберем ту из его частей W1, на которой функция j минимальна; затем разобьем на несколько частей множество W1 и выберем ту из его частей W2, на которой функция j  минимальна; затем разобьем W2 на несколько частей и выберем ту из них, где минимальна j, и так далее, пока не придем к какому-либо одноэлементному множеству {mi}.

Ссылка на основную публикацию
Adblock detector