Если оценка некоторого подмножества больше имеющегося рекорда, то среди точек данного подмножества нет оптимальных точек (решения задачи)

Это утверждение позволяет сформулировать основное правило сокращения перебора: если оценка множества больше рекордного значения, то такое множество вариантов выбрасывается из дальнейшего рассмотрения. Отметим, что множество может не подвергаться последующему ветвлению и по другим причинам:

- если при решении оценочной задачи на данном множестве была получена точка, являющаяся допустимой в исходной задаче;

- если допустимое множество оценочной задачи пусто.

5. Работа метода останавливается в соответствии с критерием оптимальности: оценки всех подмножеств не меньше имеющегося рекорда.

Таким образом,признаком останова является следующая ситуация: не осталось ни одного перспективного множества, которое может быть подвергнуто последующему ветвлению. Решением при этом является точка, в которой получено последнее рекордное значение.

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

Каждый конкретный алгоритмический вариант требует индивидуального «наполнения» всех модулей применительно к решаемой задаче.

Алгоритмическая схема метода

Решается задача вида: .

Шаг 1. Инициализация.

Задать начальное рекордное значение R. Если отыскание начального рекорда затруднительно, положить Положить – множество номеров подмножеств, подлежащих ветвлению, — множество номеров подмножеств, для которых будут решаться оценочные задачи.

Шаг 2.Вычисление оценок.

Решить оценочные задачи для множеств где . Вычислить

Шаг 3.Обновление рекорда.

Если на шаге 2 получены допустимые точки , то положить R= .

Шаг 4. Сокращение перебора.

Осуществить закрытие неперспективных множеств (включая те номера , для которых ). Удалить их номера из множеств I и J. Положить , . Если , то перейти к шагу 7.

Шаг 5.Реализация стратегии.

Выбрать из множества I номер k – индекс подмножества , подлежащего ветвлению на данном этапе в соответствии с зафиксированным правилом.

Шаг 6.Ветвление.

Осуществить разбиение множества на подмножества . Положить . Перейти к шагу 2.

Шаг 7.Останов, .

Заметим, что такая последовательность шагов может быть не рациональной в случае, если при вычислении оценок заведомо не могут появиться допустимые точки (например, при решении задачи коммивояжера).

УПРАЖНЕНИЯ

1. Докажите свойство монотонности оценок в условиях, при которых ветвление и составление оценочных задач осуществляется по правилам, указанным в п.п. 1 и 2 описания основных модулей.

2. Предложите другие стратегии обхода дерева вариантов.

3. Докажите, что при использовании основного правила отбрасывания неперспективных множеств (п.4) не происходит потери решения.

4. В предложенной алгоритмической схеме отыскивается одно решение, даже если оно в задаче не единственно. Где происходит потеря других решений? Исправьте алгоритм таким образом, чтобы появилась возможность отыскания всех решений задачи.