Описание процедур и функций

procedure TForm1.btn1Click – предназначена для ввода количества вершин, при нажатии позволяет увеличить количество на единицу.

procedure TForm1.btn2Click – предназначена для поиска пути. В качестве результата работы …

procedure TForm1.mniN2Click – предназначена для закрытия программы

procedure TForm1.btn3Click – предназначена для открытия контекстного меню.

OpenDialog1.InitialDir – загружает данные из исходного файла.

SaveDialog1.InitialDir – сохраняет данные в исходный файл.

Заключение

Изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.

Предложен собственный эффективный метод решения ЗК на основе построения выпуклого многоугольника и включения в него центральных вершин (городов).

Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).

Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.

Приведены тексты программ, позволяющие решить ЗК различными методами.

Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Menus, Grids, Buttons, StdCtrls, ExtCtrls, Math;

type

TForm1 = class(TForm)

mm1: TMainMenu;

mniN1: TMenuItem;

lbledt1: TLabeledEdit;

btn1: TSpeedButton;

chk1: TCheckBox;

mniN2: TMenuItem;

bvl1: TBevel;

lbledt2: TLabeledEdit;

lbledt3: TLabeledEdit;

btn2: TButton;

grp1: TGroupBox;

strngrd1: TStringGrid;

grp2: TGroupBox;

strngrd2: TStringGrid;

strngrd3: TStringGrid;

lbl1: TLabel;

strngrd4: TStringGrid;

lbl2: TLabel;

N1: TMenuItem;

N2: TMenuItem;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

procedure btn1Click(Sender: TObject);

procedure mniN2Click(Sender: TObject);

procedure btn2Click(Sender: TObject);

procedure btn3Click(Sender: TObject);

procedure N1Click(Sender: TObject);

procedure N2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

ver: integer;

implementation

{$R *.dfm}

procedure TForm1.btn1Click(Sender: TObject);

var

i,j,f,b: integer;

begin Randomize;

strngrd1.ColCount:= StrToInt(lbledt1.text) + 1;

strngrd1.RowCount:= StrToInt(lbledt1.Text) + 1;

strngrd4.ColCount:= StrToInt(lbledt1.text) + 1;

strngrd4.RowCount:= StrToInt(lbledt1.Text) + 1;

ver:= StrToInt(lbledt1.Text) + 1;

strngrd2.RowCount:= ver;

//strngrd2.ColWidths[2]:= 40;

for i:= ver to ver-1 do begin

strngrd2.Cells[0,i]:= 'l' + IntToStr(i);

end;

for i:= 1 to ver-1 do begin

strngrd1.Cells[0,i]:= IntToStr(i);

strngrd1.Cells[i,0]:= IntToStr(i);

strngrd4.Cells[0,i]:= IntToStr(i);

strngrd4.Cells[i,0]:= IntToStr(i);

end;

if chk1.Checked = True then begin

for i:=1 to ver-1 do begin

for j:=1 to ver-1 do begin

if i=j then begin

strngrd1.Cells[i,j]:= '0';

strngrd4.Cells[i,j]:= '0';

end

else begin

b:= Random(5);

if b = 0 then begin

strngrd1.Cells[i,j]:= '100';

strngrd1.Cells[j,i]:= '100';

strngrd4.Cells[i,j]:= '100';

strngrd4.Cells[j,i]:= '100';

end;

if b <> 0 then begin

f:= RandomRange(1, 10);

strngrd1.Cells[i,j]:= IntToStr(f);

strngrd1.Cells[j,i]:= IntToStr(f);

strngrd4.Cells[i,j]:= IntToStr(f);

strngrd4.Cells[j,i]:= IntToStr(f);

end;

end;

end;

end;

end;

end;

procedure TForm1.mniN2Click(Sender: TObject);

begin

close;

end;

procedure label_change;

begin

end;

procedure TForm1.btn2Click(Sender: TObject);

var

end_way, begin_way, begin_way2, i, j, n, met, min, step: integer;

labels,labels_2: array of integer;

end_c, end_c2: Boolean;

begin

SetLength(labels, ver-1);

SetLength(labels_2, ver-1);

begin_way:= StrToInt(lbledt2.text);

begin_way2:= 0;

for i:= 0 to ver-2 do begin

labels[i]:= 5000;

end;

////

repeat

end_c:= false;

strngrd1.Cells[begin_way, begin_way]:= '500';

if begin_way = StrToInt(lbledt3.Text) then begin

break;

end;

n:= 0;

for i:= 1 to ver-1 do begin //ìåòêè

strngrd2.Cells[1,i]:= IntToStr(labels[n]);

inc(n);

end;

n:= 1;

for i:= 0 to ver-2 do begin

labels_2[i]:= begin_way2 + StrToInt(strngrd1.cells[n, begin_way]);

inc(n);

end;

for i:= 0 to ver-2 do begin

if labels[i] > labels_2[i] then

begin

labels[i]:= labels_2[i];

end;

end;

for i:= 1 to ver-1 do begin // çàïîëíÿåì òàáëèöó

strngrd1.Cells[i, begin_way]:= '500';

strngrd1.cells[begin_way, i]:= '500';

end;

n:= 0;

for i:= 1 to ver-1 do begin

strngrd2.Cells[2,i]:= IntToStr(labels[n]);

Inc(n);

end;

strngrd2.Cells[2,begin_way]:= ''; //î÷èùàåì ìåíüøåå

for i:= 1 to ver-1 do begin

if strngrd2.Cells[2,i] = '' then strngrd2.Cells[2,i]:= '500';

end;

min:= 1000;

for i:= 1 to ver-1 do begin

if StrToInt(strngrd2.cells[2, i]) < min then

begin

min:= StrToInt(strngrd2.cells[2, i]);

begin_way:= i;

begin_way2:= min;

end;

end;

strngrd2.cells[2, begin_way]:= '500';

n:= 0;

for i:= 1 to ver-1 do begin

labels[n]:= StrToInt(strngrd2.cells[2,i]);

inc(n);

end;

//showmessage(IntToStr(min));

//ShowMessage('Âåðøèíà: ' + IntToStr(begin_way));

if begin_way = StrToInt(lbledt3.Text) then end_c:= True;

until end_c;

lbl1.Caption:= IntToStr(min);

end;

procedure TForm1.btn3Click(Sender: TObject);

var

i,j: integer;

begin

strngrd3.RowCount:= ver;

strngrd3.Cells[1,0]:= 'M';

strngrd3.Cells[2,0]:= 'T';

for i:= 1 to ver-1 do begin

strngrd3.Cells[0,i]:= IntToStr(i);

end;

for i:= 1 to 2 do begin

for j:= 1 to ver-1 do begin

strngrd3.cells[i,j]:= '0';

end;

end;

for i:= 1 to ver-1 do begin

for j:= 1 to ver-1 do begin

if (strngrd1.Cells[j,i] <> '0') and (strngrd1.Cells[j,i] <> 'á') then begin

strngrd3.Cells[1,i]:= IntToStr(StrToInt(strngrd3.Cells[1,i]) + StrToInt(strngrd1.Cells[j,i]));

strngrd3.Cells[2,i]:= IntToStr(i);

end;

end;

end;

end;

procedure TForm1.N1Click(Sender: TObject);

var

f: file of integer;

n, i, j, t: integer;

begin

OpenDialog1.InitialDir:= GetCurrentDir;

if OpenDialog1.Execute then

begin

AssignFile(f, OpenDialog1.FileName);

reset(f);

read(f, n);

lbledt1.Text:= inttostr(n);

strngrd1.ColCount:= StrToInt(lbledt1.text) + 1;

strngrd1.RowCount:= StrToInt(lbledt1.Text) + 1;

strngrd4.ColCount:= StrToInt(lbledt1.text) + 1;

strngrd4.RowCount:= StrToInt(lbledt1.Text) + 1;

ver:= StrToInt(lbledt1.Text) + 1;

strngrd2.RowCount:= ver;

//strngrd2.ColWidths[2]:= 40;

for i:= ver to ver-1 do begin

strngrd2.Cells[0,i]:= 'l' + IntToStr(i);

end;

for i:= 1 to ver-1 do begin

strngrd1.Cells[0,i]:= IntToStr(i);

strngrd1.Cells[i,0]:= IntToStr(i);

strngrd4.Cells[0,i]:= IntToStr(i);

strngrd4.Cells[i,0]:= IntToStr(i);

end;

for i:= 1 to n-1 do

for j:= 1 to n-1 do

begin

read(f, t);

strngrd4.Cells[j,i]:= inttostr(t);

end;

closefile(f);

end;

end;

procedure TForm1.N2Click(Sender: TObject);

var

f: file of integer;

i, j, t: integer;

begin

SaveDialog1.InitialDir:= GetCurrentDir;

if SaveDialog1.Execute then

begin

AssignFile(f,SaveDialog1.FileName);

Rewrite(f);

t:= strngrd4.RowCount - 1;

write(f, t);

for i:=1 to strngrd4.RowCount-1 do

for j:=1 to strngrd4.RowCount-1 do

begin

t:= strtoint(strngrd4.Cells[j,i]);

write(f, t);

end;

closefile(f);

end;

end;

end.

Дата добавления: 2015-08-31