school stuff

In studiile mele intense facute la faculta am aflat ca trebuie sa studiem ceva legat de agloritmi de calcul al sistemelor de ecuatii.
Am fost foarte curios sa aflu cum functioneaza acest Cuthill McKee am implementat in Delphi acest algoritm,
si am facut o mica aplicatie folosind si o harta de biti pentru vizualizarea matricilor si solutiilor acestora.
Intersant se vede foarte bine aceasta micsorare a latimii benzi in cazul matricilor rare.
Va pun la dispozitie pentru cei „pasionati” ca si mine de matematica ,algoritmul implementat,cat si functia ce genereaza harta de biti.

//Cuthill-Mckee

begin
// initializari
SetLength(LevStr, Matrix.Size);
SetLength(Selected, Matrix.Size);
SetLength(Result.Elements, Matrix.Size);
Result.Size := Matrix.Size;

for i := 0 to Matrix.Size – 1 do
begin
LevStr[i].vecini.Size := 0;
Selected[i] := 0;
Result.Elements[i] := -1;
end;
//constructia grafului
for i := 0 to Matrix.Size – 1 do
begin
LevStr[i].InitialLabel := i;
LevStr[i].NewLabel := 0;
for j := i+1 to Matrix.Size – 1 do
if Matrix.Elements[i,j] <> 0 then
begin
Inc(LevStr[i].Vecini.Size);
Inc(LevStr[j].Vecini.Size);
SetLength(LevStr[i].Vecini.Elements, LevStr[i].Vecini.Size);
SetLength(LevStr[j].Vecini.Elements, LevStr[j].Vecini.Size);
LevStr[i].Vecini.Elements[LevStr[i].Vecini.Size-1] := j;
LevStr[j].Vecini.Elements[LevStr[j].Vecini.Size-1] := i;
end;
end;

//sortarea vecinilor si inserarea in ordinea gradelor
min := Matrix.Size;
MinIndex := -1;
for i := 0 to Matrix.Size – 1 do
begin
for j := 0 to LevStr[i].Vecini.Size – 2 do
for k := j+1 to LevStr[i].Vecini.Size – 1 do
if LevStr[LevStr[i].Vecini.Elements[j]].Vecini.Size > LevStr[LevStr[i].Vecini.Elements[k]].Vecini.Size then
begin
aux := LevStr[i].Vecini.Elements[j];
LevStr[i].Vecini.Elements[j] := LevStr[i].Vecini.Elements[k];
LevStr[i].Vecini.Elements[k] := aux;
end;

//se determina un nod de start
if LevStr[i].Vecini.Size < min then
begin
min := LevStr[i].Vecini.Size;
MinIndex := i;
end;
end;

Assignfile(f, ExtractFilePath(Application.ExeName)+’\RCMOUT1.txt’);
Rewrite(f);
for i := 0 to Matrix.Size – 1 do
begin
Write(f, LevStr[i].InitialLabel+1,’ ‘, LevStr[i].NewLabel+1, ‘ ‘, LevStr[i].VEcini.Size, ‘ ‘);
for j := 0 to LevStr[i].Vecini.Size – 1 do
Write(f, LevStr[i].Vecini.Elements[j]+1,’ ‘);
Writeln(f);
end;
CloseFile(f);

RStartIndex := 0;
REndIndex := 0;
Selected[MinIndex] := 1;
Result.Elements[RStartIndex] := MinIndex;
Inc(REndIndex);
LevStr[MinIndex].NewLabel := RStartIndex;

//se plica CutHill McKee pentru fiecare componenta conexa din graf
repeat
Neconex := false;
while (REndIndex < Matrix.Size) do
begin
for i := 0 to LevStr[Result.Elements[RStartIndex]].Vecini.Size – 1 do
if Selected[LevStr[Result.Elements[RStartIndex]].Vecini.Elements[i]] = 0 then
begin
Selected[LevStr[Result.Elements[RStartIndex]].Vecini.Elements[i]] := 1;
Inc(REndIndex);
LevStr[LevStr[Result.Elements[RStartIndex]].Vecini.Elements[i]].NewLabel := REndIndex – 1;
Result.Elements[REndIndex – 1] := LevStr[Result.Elements[RStartIndex]].Vecini.Elements[i];
end;
Inc(RStartIndex);
if RStartIndex>(REndIndex – 1) then
begin
Neconex := true;
Break;
end;
end;

if Neconex then
begin
MinIndex := -1;
min := Matrix.Size;
for i := 0 to Matrix.Size – 1 do
begin
if Selected[LevStr[i].InitialLabel] = 0 then
if LevStr[i].Vecini.Size < min then
begin
min := LevStr[i].Vecini.Size;
MinIndex := i;
end;
end;
Result.Elements[RStartIndex] := MinIndex;
Inc(REndIndex);
LevStr[MinIndex].NewLabel := RStartIndex;
Selected[MinIndex] := 1;
end;
until not(Neconex);

// generea solutiei
GenerateUnitMatrix(Solution, Matrix.Size);
for i := 0 to Matrix.Size – 1 do
for j := 0 to  LevStr[i].Neighbours.Size – 1 do
begin
LevStr[i].Neighbours.Elements[j] := LevStr[LevStr[i].Vecini.Elements[j]].NewLabel;
Solution.Elements[LevStr[i].NewLabel, LevStr[i].Vecini.Elements[j]] := 1;
end;

Pentru a putea urmarii rezultatele acestui algoritm,si anume modificarea latimii benzii trebuie sa cream o harta de biti pentru a vizualiza  punctele matricii initiale
si matrice finala dupa aplicarea algoritmului.
codul pentru harta arata cam asa:

function BuildMatrixBitmap(Matrix: TVariable);
var
i: integer;
j: integer;
Row:  pRGBTripleArray;
begin
ProgressBar.Max := AMatrix.Size;
ProgressBar.Min := 0;
ProgressBar.Step := 1;
ProgressBar.Position := 0;

FreeAndNil(MPreview);
MPreview := TBitmap.Create;
MPreview.PixelFormat := pf24bit;
MPreview.Width  := AMatrix.Size;
MPreview.Height := AMatrix.Size;
for j := 0 to MPreview.Height – 1 do
begin
Row := MPreview.ScanLine[j];
for i := 0 to MPreview.Width – 1 do
begin
With row[i] do
if AMatrix.Elements[i,j] = 0 then
begin
rgbtRed := 60;
rgbtGreen := 112;
rgbtBlue := 255;
end
else
begin
rgbtRed := 0;
rgbtGreen := 0;
rgbtBlue := 0;
end;
end;
ProgressBar.StepIt;
end;

{for i := 0 to MPreview.Width – 1 do
begin
for j := 0 to MPreview.Height – 1 do
if AMatrix.Elements[i,j] = 0 then
MPreview.Canvas.Pixels[i,j] := clHighlight
else
MPreview.Canvas.Pixels[i,j] := clBlack;
ProgressBar.StepIt;
end;}
end;

Sunt multi algoritmi ce merita studiati, am gasit lucrarea lui A. Lim, B. Rodrigues si F. Xiao pentru algoritmul hibrid o combinatie
intre algoritmul genetic si Hill Climbing o puteti gasi si voi aici

Anunțuri

One response to this post.

  1. Posted by Clara on Decembrie 3, 2009 at 5:39 pm

    After intense search of this algorithm, i found this variant of implementation to improve my game. I want to congratulate for this implementation.it is the most intelligible and understanding.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

%d blogeri au apreciat asta: