Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 01.06.2010, 19:42   #1
Zengor
Новичок
Джуниор
 
Регистрация: 01.06.2010
Сообщений: 1
По умолчанию Эвристический алгоритм нахождения максимально(по размеру) независимого множества

Дан граф 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.
Zengor вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм нахождения, максимального потока в Графе densi2009 Общие вопросы Delphi 0 27.05.2010 23:12
Реализовать алгоритм нахождения базисных циклов Fasolka Помощь студентам 0 03.05.2010 14:44
Алгоритм нахождения простых чисел ardor Помощь студентам 1 20.11.2009 00:00
Алгоритм нахождения обратной мтарицы AlinAA Помощь студентам 1 22.03.2009 12:20
алгоритм нахождения интеграла методом трапеций pirozho4ek Паскаль, Turbo Pascal, PascalABC.NET 2 11.06.2007 02:44