Решение задачи о наименьшем покрытии

К задачам на построение МДМ можно отнести следующие практические (конечно упрощенные) задачи:

a) Размещение телевизионных станций на некоторой территории.

б) Размещение военных баз, контролирующих данную территорию.

в) Размещения центров торговли, обслуживающих некоторый район.

г) Размещение окружных центров избирательной кампании.

Если предположить, что "территория обслуживания" представляет собой квадрат как на рис.2.5а с 16 районами. "Центр обслуживания", помещенный в любой район, контролирует не только этот район, но и соседние, граничащие (имеющие общую сторону) с ним районы. Тогда наименьшее число "центров обслуживания" равно 4. Возможное расположение указано на рис.2.5а. Если предположить, что район - вершина графа и соседние вершины соединить ребрами, то полученное решение на графе (рис.2.5б) представляет одно из МДМ, для которого все остальные вершины достижимы за один шаг.

К более сложным относится задача г), которую можно описать следующим образом. Пусть заданы населенные пункты с числом избирателей n_i, и известна карта дорог между ними с расстояниями С_ij. Известны удельные транспортные затраты р и затраты на организацию одного избирательного центра округа – q. Выдвинуты требования, чтобы в избирательном округе число избирателей удовлетворяло условию где номер избирательного округа.

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

Следует отметить, что если для МНМ важно получить все списки, то для задач с поиском МДМ обычно требуется найти просто наименьшее доминирующее множество (НДМ).

Пусть - транспонированная матрица смежности графа с единичными диагональными элементами. Задача определения НДМ графа эквивалентна задаче нахождения такого множества столбцов в , что каждая строка матрицы содержит 1 хотя бы в одном из выбранных столбцов. Эта задача о поиске наименьшего множества столбцов, "покрывающих" все строки, называется задачей о наименьшем покрытии (ЗНП).

В общей ЗНП матрица не обязательно квадратная. Кроме того каждому столбцу (в нашем случае каждой вершине x_j) сопоставляется некоторый вес с_j (штраф, дополнительная стоимость и т.п.) и требуется выбрать покрытие (для графов это ДМ) с наименьшей (наибольшей) стоимостью. Таким образом задача об отыскании МДМ является частной задачей о покрытии ().

ЗНП можно сформулировать в теоретико-множественной интерпретации таким образом. Даны множество и семейство множеств . Любое подсемейство семейства Y, такое что

(2.15)

называется покрытием множества , a называется покрывающими множествами. Если в дополнение к (2.15) удовлетворяет условию

(2.16)

то называется разбиением множества R.

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

В матричной форме, когда строки матрицы состоящей из 0 и 1, покрываются столбцами, ЗНП может быть сформулирована как задача линейного программирования (ЗЛП):

при условии

, (2.17)

где ,

Для ЗНР неравенства (2.17) превращаются в равенства

.

Вследствие особой природы ЗНП часто удается упростить эту задачу.

a) Если то r_j покрыть нельзя, и, следовательно, задача не имеет решения.

б) Если то должно присутствовать вo всех решениях, т.е. размерность задачи снижается введением

в) Если тогда, если такие, что , то , можно удалить из R, т.к. любое множество, покрывающее покрывает и (т.е. доминирует над ).

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

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

Суть его состоит в построении в самом начале "блоков" столбцов, по одному на . -й блок состоит из таких множеств семейства Y, в которых содержится , но отсутствуют (cм. табл.2.1).

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

Таблица 2.1

Исходная таблица

	Блок 1	Блок 2	Блок 3
	1...1
	0 или 1	1...1
	0 или 1	1...1
---	0 или 1

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

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