Попытаемся осознать метод решения задачи, рассматривая, как обычно, пример. У нас есть ориентированный граф, его матрица смежности и транспонированная матрица смежности с единичными диагональными элементами. Исследуем структуру матрицы А*. Нас интересует, какие столбцы содержат единицу в первой строке, какие столбцы содержат единицу во второй строке и не содержат в первой и так далее. С этой целью можно было бы переставлять столбцы в матрице А*, но оставим ее «в покое». Будем использовать дополнительную матрицу Bl, ее тип:
type Pr=array [1..MaxN, 1..MaxN+1] of integer;
var Bl: Pr;, где MaxN – максимальная размерность задачи. Почему плюс единица (технический прием – «барьер»), будет ясно из последующего изложения (процедура Press).
При инициализации матрица Bl должна иметь вид:
· в первой строке – [1 2 3. №0];
· все остальные элементы равны нулю.
То есть наше исходное предположение заключается в том, что все столбцы матрицы А* имеют единицы в первой строке. Проверим его. Будем просматривать элементы очередной строки (i) матрицы Bl. Если Bl [i, j]<>0, то со значением Bl [i, j], как номером столбца матрицы A*, проверим соответствующий элемент А*. При его неравенстве нулю элемент Bl остается на своем месте, иначе он переписывается в следующую строку матрицы Bl, а элементы текущей строки Bl сдвигаются вправо, сжимаются (Press). Итак, для N-1 строки матрицы Bl. Для нашего примера матрица Bl после этого преобразования будет иметь вид:
| … | |||||||
| …. | |||||||
| Bl= | … | ||||||
| …… | |||||||
4 3 6 1 0… 0
5 7 2 0… 0
Bl= 0 0
….
0 … 0
В нашей задаче определены стоимости вершин графа или стоимости столбцов матрицы А*, и необходимо найти разбиение наименьшей стоимости. Пусть стоимости описываются в массиве Price (Price: array [1..MaxN] of integer) и для примера на рисунке имеют значения [15 13 4 3 8 9 10]. Осталась чисто техническая деталь – отсортировать элементы каждой строки матрицы Bl по возрастанию стоимости соответствующих столбцов матрицы А. Логика формирования приведена ниже по тексту (Blocs).
procedure Blocs; {выделения блоков}
{Bl – глобальная переменная}
procedure Sort;
{Price и Bl – глобальные переменные}
begin
…
end;
procedure Press (i, j:integer); {Сдвигаем элементы строки с номером i, начиная с позиции (столбца) j, на одну позицию вправо}
{Bl – глобальная переменная}
var k:integer;
begin
k:=j;
while Bl [i, k]<>0 do begin {Поэтому размерность матрицы с плюс единицей. В последнем столбце строки всегда записан 0.}
Bl [i, k]:=Bl [i, k+1];
Inc(k);
end; {while}
end; {Press}
var i, j, cnt:integer;
begin
FillChar (Bl, SizeOf(Bl), 0);
for i:=1 to N do Bl [1, i]:=i; {предполагается, что в первом блоке все столбцы}
for i:=1 to N-1 do begin
j:=1; cnt:=0;
while Bl [i, j]<>0 do begin
if A*[i, Bl [i, j]]=0 then begin {столбец не в этом блоке}
Inc(cnt);
Bl [i+1, cnt]:=Bl [i, j]; {переписать в следующую строку}
Press (i, j);
Dec(j);
end; {if}
Inc(j);
end; {while}
end; {for}
Sort;
end; {Blocs}
После этой предварительной работы мы имеем вполне «приличную» организацию данных для решения задачи путем перебора вариантов. Матрица Bl разбита на блоки, и необходимо выбрать по одному элементу (если соответствующие строки ещё не покрыты) из каждого блока. Процесс выбора следует продолжать до тех пор, пока не будут включены в «покрытие» все строки или окажется, что некоторую строку нельзя включить.
Продолжим рассмотрение метода. Если при поиске независимых множеств мы шли «сверху вниз», последовательно уточняя логику, то сейчас попробуем идти «снизу вверх», складывая окончательное решение из сделанных «кирпичиков». Как обычно, следует начать со структур данных. Во-первых, мы ищем лучшее решение, то есть то множество столбцов, которое удовлетворяет условиям задачи (непересечение и «покрытие» всего множества строк), и суммарная стоимость этого множества минимальна. Значит, необходима структура данных для хранения этого множества и значения наилучшей стоимости и, соответственно, структуры данных для хранения текущего (очередного) решения и его стоимости. Во-вторых, в решении строка может быть или не быть. Следовательно, нам требуется как-то фиксировать эту информацию. Итак, данные.
type Model=array [1..MaxN] of boolean;
var Sbetter: Model; Pbetter:integer; {лучшее решение}
S: Model; P:integer; {текущее решение}
R: Model; {R[i]=true – признак того, что строка i «покрыта» текущим решением}
Логика включения (исключения) столбца с номером k в решение (из решения) имеет вид:
procedure Include (k:integer); {включить столбец в решение}
{A*, R, Price, S, P – глобальные переменные}
var j:integer;
begin
P:=P+Price[k]; {текущая цена решения}
S[k]:=true; {столбец с номером k в решение}
for j:=1 to N do
if A*[j, k]=1 then R[j]:=true; {строки, «покрытые» столбцом k}
end; {Include}
procedure Exclude (k:integer); {исключить столбец из решения}
var j:integer;
begin
p:=p-Price[k];
S[k]:=false;
for j:=1 to N do if (A*[j, k]=1) and R[j] then R[j]:=false;
end; {Exclude}
Проверка, сформировано ли решение, заключается в том, чтобы просмотреть массив R и определить, все ли его элементы равны истине.
function Result:boolean;
var j:integer;
begin
j:=1;
while (j<=N) and R[j] do Inc(j);
if j=N+1 then Result:=true else Result:=false;
end; {Result}
Кроме перечисленных «кирпичиков», нам необходимо уметь определять, можно ли столбец с номером k включать в решение. Для этого следует просмотреть столбец с номером k матрицы A* и проверить, нет ли совпадений единичных элементов со значением true соответствующих элементов массива R.
function Cross (k:integer):boolean; {пересечение столбца с частичным решением, сформированным ранее}
var j:integer;
begin
j:=1;
while (j<=N) and Not (R[j] and (A*[j, k]=1)) do Inc(j);
if j=N+1 then Cross:=true else Cross:=false;
end; {Cross}
Заключительная логика поиска (Find) имеет в качестве параметров номер блока (строки матрицы Bl) – переменная bloc и номер позиции в строке. Первый вызов – Find (1,1).
procedure Find (bloc, jnd:integer);
{переменные глобальные}
begin
if Result then begin if P<Pbetter then begin Pbetter:=P;
Sbetter:=S;
end;
end
else if Bl [bloc, jnd]=0 then exit
else if Cross (Bl[bloc, jnd]) then begin
Include (Bl[bloc, jnd]);
Find (bloc+1,1);
Exclude (Bl[bloc, jnd]);
end
else if R[bloc] then Find (bloc+1,1);
Find (bloc, jnd+1);
end; {Find}
Нам осталось дать общую логику, но после выполненной работы она не вызывает затруднений.
program R_min;
const MaxN=…;
type… var…
procedure Init; {ввод и инициализация данных}
begin
…
end;
procedure Print; {вывод результата}
begin
…
end;
{процедуры и функции, рассмотренные ранее}
{основная логика}
begin
Init;
Blocs;
Find (1,1);
Print;
end.
Заключение
Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф (клика). В максимальном независимом множестве нет смежных вершин, в клике все вершины попарно смежны. Максимальное независимое множество графа G соответствует клике графа G’, где G’ – дополнение графа G.
Литература
1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. - М.: Наука, 1975.
2. Берж К. Теория графов и ее применение. – М.: ИЛ, 1962.
3. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.
4. Зыков А.А. Теория конечных графов. - Новосибирск: Наука; Сиб. отд-ние, 1969.
5. Йенсен П., Барнес Д. Потоковое программирование.-М.:Радио и связь, 1984.
6. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. – М.: Наука, 1986.
7. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978.
8. Кофман А. Введение в прикладную комбинаторику. - М.: Наука, 1975.
9. Липский В. Комбинаторика для программистов. - М.: Мир, 1988.
10.Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир, 1981.
11.Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск: Наука; Сиб. отд-ние, 1990.
12.Окулов С.М. Конспекты занятий по информатике (алгоритмы на графах). Учебное пособие для студентов и учителей школ. – Киров, 1996.
13.Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.-М.:Мир, 1985.
14.Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984.
15.Филипс Д., Гарсиа-Диас А. Методы анализа сетей. – М.: Мир, 1984.
16.Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. - М.: Мир, 1963.
17.Фрэнк Г., Фриш И. Сети, связь и потоки. - М.: Связь, 1978.
18.Харари Ф. Теория графов. - М.: Мир, 1973.