Контрольная работа: Алгоритмы на графах. Независимые и доминирующие множества

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;