Дискретная оптимизация - 4 стр.

                                     4
3) Правило обхода дерева вариантов в процессе работы алгоритма называют
   стратегией обхода дерева. Существует множество различных стратегий.
   Наиболее распространенными являются три из них.
   a) “По минимуму оценки”. В этом случае для последующего разбиения вы-
      бирается подмножество, имеющее к даному шагу алгоритма минималь-
      ную оценку.
   b) Односторонний обход дерева вариантов. Для последующего разбиения
      выбирается одно из подмножеств, полученных на предыдущем шаге (на-
      пример, подмножество, в котором xl =1 , 1 ≤l ≤n ). Если соответствующая
      ветвь дерева оказывается пройденной до конца (или отброшена как не-
      перспективная), то происходит возвращение к ближайшему из предыду-
      щих шагов, где сохранилась альтернатива.
   c) Смешанная стратегия. В этом случае для продвижения “вниз по дереву”
      используется односторонний обход дерева вариантов, а при “подъеме
      вверх” ищется множество с минимальной оценкой.
4) Будем называть множество неперспективным, если относительно него при-
   нимается решение о выбрасывании его из дальнейшего рассмотрения. От-
   брасывание множеств в ходе решения обеспечивает сокращение перебора.
   Исключение множеств вариантов из дальнейшего рассмотрения производит-
   ся с помощью оценок этих множеств и рекорда. Рекордом (или рекордным
   значением) называют значение целевой функции в “лучшей” (доставляющей
   наименьшее значение) из полученных допустимых точек. Для определения
   начального рекорда рекомендуется воспользоваться каким-либо приближен-
   ным алгоритмом или другой априорной информацией, если она имеется. По
   ходу решения задачи рекорд обновляется. Справедливо следующее утвер-
   ждение. Если оценка некоторого подмножества больше имеющегося ре-
   корда, то среди точек данного подмножества нет решения задачи. Это
   утверждение позволяет сформулировать основное правило сокращения пе-
   ребора: если оценка множества больше рекордного значения, то такое мно-
   жество вариантов выбрасывается из дальнейшего рассмотрения. Отметим,
   что множество может не подвергаться последующему ветвлению и по дру-
   гим причинам: если при решении оценочной задачи на данном множестве
   была получена точка, являющаяся допустимой в исходной задаче, или если
   допустимое множество оценочной задачи пусто.
5) Работа метода останавливается в соответствии с критерием оптимальности.
   Признаком останова является следующая ситуация: не осталось ни одного
   множества, которое может быть подвергнуто последующему ветвлению.
   Решением при этом является точка, в которой получено последнее рекорд-
   ное значение.

В представленных выше пяти пунктах описаны основные модули, с помощью
которых может быть составлена схема работы любого варианта метода ветвей и
границ.