Дан граф G = (V, E), где V = {v1, v2, ... vN} – вершины графа, E = {e1, e2, ... eM} – его ребра. ребуется найти максимальное (по мощности) множество вершин U такое, что никакие две его вершины не смежны.
Вообще нужно сравнить перебор с эвристикой. Перебор я реализовал, а вот эвристику не знаю как. Может ли кто нибудь подсказать эвристический алгоритм(желательно код) или хотя бы в какой литературе его поискать?
На всякий случай код перебора
Код:
program Laba5;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
NMin = 5;
NMax = 60;
Repeats = 10;
var
f:text;
n,i,j:integer;
mas :Array[1..NMax, 1..NMax] of Integer; {Матрица смежности}
rez,temp,fl:array [1..50] of integer;
sumTime :Array[NMin..NMax] of Real;
rezsize,tempsize :integer;
calls :Longint; {Количество рекурсивных вызовов функции перебора}
minCalls, sumCalls, maxCalls :Array[NMin..NMax] of Longint;
time1 :Real;
procedure GenerateMatrix(N :Integer);
var
i, j :Integer;
begin
for i := 1 to N do begin
for j := 1 to i-1 do begin
mas[i,j] := Random(2);
mas[j,i] := mas[i,j];
end;
end;
for i := 1 to N do
mas[i,i] := 0;
end; {GenerateMatrix}
function GetSeconds: Real;
{Возвращает системное время как вещественное число секунд}
begin
GetSeconds := TimeStampToMSecs(DateTimeToTimeStamp(Time));
end; {GetSeconds}
procedure InitializeSearch;
{Инициализирует величины перед началом решения новой задачи}
begin
time1 := GetSeconds; {Время начала}
calls := 0; {Вызовов процедуры еще не было}
end; {InitializeSearch}
procedure InitializeSeries;
{Инициализирует статистики перед каждой серией из Repeats задач
для данного N}
begin
minCalls[N] := MaxLongInt;
sumTime[N] := 0;
sumCalls[N] := 0;
maxCalls[N] := 0;
end; {InitializeSeries}
function check:boolean;
var
il,jl,t:integer;
begin
t:=tempsize;
for il:=1 to t do
for jl:=1 to t do
if (mas[temp[il]][temp[jl]]<>0) then
begin
check:=false;
exit;
end;
check:=true;
end;
procedure rez_temp;
var
il:integer;
begin
rezsize:=tempsize;
for il:=1 to rezsize do
rez[il]:=temp[il];
end;
procedure temp_push_back(ii:integer);
begin
temp[tempsize+1]:=ii;
tempsize:=tempsize+1;
end;
procedure temp_pop_back;
begin
tempsize:=tempsize-1;
end;
procedure rec(k:integer);
var
q:integer;
begin
Inc(calls); {Сосчитаем данный вызов}
if (check) then
begin
if (tempsize>rezsize) then
rez_temp;
for q:=k+1 to n do
begin
if fl[q]=0 then
begin
fl[q]:=1;
temp_push_back(q);
rec(q);
temp_pop_back;
fl[q]:=0;
end;
end;
end;
end;
procedure StoreResults;
{Фиксирует результаты решения одной случайной задачи}
begin
sumTime[N] := sumTime[N] + (GetSeconds - time1);
if calls < minCalls[N] then minCalls[N] := calls;
if calls > maxCalls[N] then maxCalls[N] := calls;
Inc(sumCalls[N], calls)
end; {StoreResults}
procedure ShowResults;
{Выдает таблицу результатов эксперимента}
begin
Writeln(' N Srednee Chislo visovov ');
Writeln(' vremja minim. srednee. max.');
Writeln('------------------------------------------');
for N:=NMin to NMax do
Writeln(N:2, sumTime[N]/Repeats:9:2,
minCalls[N]:10, round(sumCalls[N]/Repeats):9, maxCalls[N]:9);
end; {ShowResults}
Begin
randomize();
{ assign(f,'input.txt');
reset(f);
readln(f,n);
for i:=1 to n do
for j:=1 to n do
read(f,mas[i][j]);
close(f);
tempsize:=0;
rezsize:=0;
rec(0);
for i:=1 to rezsize do
write(rez[i],' ');
readln; }
for N := NMin to NMax do begin
InitializeSeries;
Write('N =', N:3);
for i := 1 to Repeats do begin
GenerateMatrix(N);
InitializeSearch;
tempsize:=0;
rezsize:=0;
rec(0);
StoreResults; {Учесть результат в статистике}
end;
Writeln;
end;
ShowResults;
readln;
end.