4.3. Алгоритм решения ЗНР, использующий дерево поиска

Как отмечалось ранее, ЗНР тесно связана с ЗНП, являясь по существу ЗНП с дополнительным (неперекрываемость) ограничением. Это ограничение выгодно, если мы пытаемся решить задачу с помощью некоторого метода, использующего дерево поиска: при таком ограничении может рано выясниться, что некоторые возможные ветвления дерева рассматривать не надо. Учитывая вышесказанное, мы сначала займемся алгоритмом решения ЗНР (использующим дерево поиска), а затем покажем, как его можно приспособить к решению ЗНП.

Простые методы решения ЗНР, использующие дерево поиска, были предложены Пирсом [48] и Гарфинкелем и Немхаузером (271.

Сущность этих методов такова. Вначале строятся «блоки» столбцов, по одному на каждый элемент из т. е. всего блоков. блок состоит из таких множеств семейства (представленных столбцами), в которых содержится элемент но отсутствуют элементы с меньшими индексами — Следовательно, каждое множество (столбец) появляется точно в одном определенном блоке и совокупность блоков может быть представлена в виде таблицы, как показано на рис. 3.1. В конкретных задачах некоторые из блоков могут отсутствовать.

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

отброшено (на этом этапе) в соответствии с требованием неперекрываемости.

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

Таблица 3.1 (см. скан) Исходная таблица

Текущее «наилучшее» решение В со стоимостью известно на любом этапе поиска (В обозначает семейство соответствующих покрывающих множеств). Если соответствующие семейство и стоимость на данной стадии поиска, множество, представляющее те элементы (т. е. строки) которые покрываются множествами из В, то один из простых алгоритмов, использующих дерево поиска, можно описать следующим образом.

Присвоение начальных значений

Шаг 1. Построить исходную таблицу и начать с частного решения:

Расширение

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

Шаг 3. Начиная с отмеченной позиции в блоке перебирать его множества скажем, в порядке возрастания индекса .

(i) Если найдено множество такое, что стоимость множества то перейти к шагу 5.

(ii) В противном случае, т. е. если блок исчерпан или выбрано множество такое, что перейти к шагу 4.

Шаг возвращения

Шаг 4. В не может привести к лучшему решению. Если (т. е. блок 1 исчерпан), то алгоритм заканчивает работу и оптимальным решением является В. В противном случае удалить последнее множество, скажем, добавить его в В, положить поставить метку над множеством удалить предшествующую метку в блоке I и перейти к шагу 3.

Проверка нового решения

Шаг 5. Обновить данные: Если найдено лучшее решение то положить и перейти к шагу 4. Иначе перейти к шагу 2.

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

Прежде чем показать, как алгоритм для ЗНР распространяется на ЗНП, кратко упомянем о некоторых других методах, применяемых при решении ЗНР. В [49] Пиро и Ласки дали ряд модификаций приведенного выше основного алгоритма, используя в качестве вспомогательного средства линейное программирование; в [45] Мишо описал другой алгоритм неявного перебора, который основан на задаче линейного программирования, соответствующей ЗНР с «блочной» структурой (рассмотренной выше и игравшей вспомогательную роль).

Предлагались также алгоритмы, включающие итерации симплексного типа, как прямые [4, 5], так и двойственные [58, 37]. В [37] Йенсен успешно применил метод динамического программирования к определенному типу ЗНР.