Доброго времени суток!!
Очень нужна помощь.Необходимо разобраться в небольшой программе, а именно дописать коментарии. Задача принадлежит к классу комбинаторики.
Вот задание "Задача о трех станках. Даны N деталей, каждая из которых должна быть обработана на станке A, затем на станке B, затем на станке C. Каждый станок может в данный момент времени обрабатывать только одну деталь. Если нужный станок занят, то другие детали могут ожидать его освобождения. Для каждой детали известны длительности ее обработки на каждом станке: TAi, TBi, TCi. Требуется найти такой порядок запуска деталей на обработку (т.е. найти такую перестановку номеров деталей), при котором длительность обработки всего комплекта деталей минимальна."
В ниже приведенной программе задача рашается двумя алгоритмами
1)метод перебора-соответсвенно в программе она называется процедурой "perebor"
2) методом последовательного выбора(эвристический алгоритм) в программе называется процедурой "evristika"
Очень прошу вашей помощи. Особенно нужны коментарии в начале где основные переменные описаны и в процедурах "calc" и "evristika"
по этой ссылке http://slil.ru/27474819 я залил текстовый файл in.txt нужный для программы - в нем записана сама матрица. В этой матрице 1000 строк -соответсвенно 1000 деталей, и 3 столбца соответсвенно для 1-го для 2-го и для 3-го станка. На пересечение строки и столбца стоит время обработки детали на данном станке.
| Код |
program p;
uses
crt,dos;
var
fin,fout:text;
Mt:array [1..1001,1..3] of integer;
X:array [1..1000] of integer;
N,min1,i:integer;
time:real;
min2:word;
function GetSeconds: Real;
{Возвращает системное время как вещественное число секунд}
var
h, m, s, hund : Word;
begin
GetTime(h,m,s,hund);
GetSeconds := h*3600.0 + m*60 + s + hund/100;
end; {GetSeconds}
function max2(a,b:integer):integer;
{ Возвращает максимум из двух целых чисел }
begin
if a>b then max2:=a
else max2:=b
end;
function max3(a,b,c:integer):integer;
{ Возвращает максимум из трех целых чисел }
begin
max3:=max2(a,max2(b,c));
end;
procedure calc(var time:integer);
{процедура подсчета длительности обработки всего комплекта деталей}
var
i:integer;
begin
time:=0;
time:=Mt[X[1],1];
time:=time+max2(Mt[X[1],2],Mt[X[2],1]);
i:=1;
while i<(N-1) do begin
time:=time+max3(Mt[X[i],3],Mt[X[i+1],2],Mt[X[i+2],1]);
inc(i);
end;
time:=time+max2(Mt[X[N-1],3],Mt[X[N],2]);
time:=time+Mt[X[N],3];
end;
procedure perebor(k :Integer); {k – количество уже найденных номеров деталей в последовательности}
var
ip:integer;
ok:boolean;
begin
if k = N then begin
calc(ip);
if ip<min1 then min1:=ip;
end
else begin {k < n}
inc(k);
X[k]:=1;
while X[k]<= N do begin
ok:=true;
ip:=1;
while ip < k do begin
if (X[k]=X[ip]) then ok:=false;
inc(ip);
end;
if (ok) then perebor(k);
inc(X[k]);
end;
end;
end; {procedure perebor}
function fact(n:integer):longint;
{ Функция возвращает факториал от n }
var i:integer;
s:longint;
begin
s:=1;
i:=1;
while i<=n do begin
s:=s*i;
inc(i);
end;
fact:=s;
end;
{EBPucTu4eckuu AJIrOPuTM}
Procedure evristika(N1:integer; var time1: word);
var
i,j,k:integer;
min:integer;
ok:boolean;
begin
{поиск первой лучшей детали }
min:=32000;
for i:=1 to N1 do begin
if Mt[i,1]<min then begin
min:=Mt[i,1];
X[1]:=i;
end;
end;
time1:=min;
{поиск второй лучшей детали}
min:=32000;
for i:=1 to N1 do begin
if i<>X[1] then begin
if max2(Mt[X[1],2],Mt[i,1])<min then begin
min:=max2(Mt[X[1],2],Mt[i,1]);
X[2]:=i;
end;
end;
end;
time1:=time1+min;
{поиск остальных деталей }
i:=1;
while i<=(N1-2) do begin
min:=32000;
for j:=1 to N1 do begin
ok:=true;
for k:=1 to (i+1) do begin
if j=X[k] then ok:=false;
end;
if ok then begin
if max3(Mt[X[i],3],Mt[X[i+1],2],Mt[X[j],1])<min then begin
X[i+2]:=j;
min:=max3(Mt[X[i],3],Mt[X[i+1],2],Mt[X[j],1]);
end;
end;
end;
time1:=time1+min;
inc(i);
end;
time1:=time1+max2(Mt[X[N-1],3],Mt[X[N],2]);
time1:=time1+Mt[X[N],3];
end;
begin
{ Открытие и считывание данных с входного файла }
assign(fin,'c:\temp\in.txt');
assign(fout,'c:\temp\out.txt');
rewrite(fout);
for i:=1 to 5 do begin
N:=0;
min1:=32000;
min2:=32000;
reset(fin);
while (not(eof(fin))and(N<i+4))do begin
inc(N);
readln(fin,Mt[N,1],Mt[N,2],Mt[N,3]);
end;
Time:=GetSeconds;
perebor(0);
{вывод таблицы результатов}
write('N: ',N:2,'.Time: ',(GetSeconds-Time):5:2,'cek. MIN1: ',min1:3,' KoJI-BO ',fact(N):7);
Time:=Getseconds;
evristika(N,min2);
writeln(' Time2: ',(GetSeconds-Time):5:2,'cek. Min2: ',min2:3);
write(fout,'N: ',N:2,'.Time: ',(GetSeconds-Time):5:2,'cek. MINIMUM: ',min1:3,' KoJI-BO ',fact(N):7);
writeln(fout,' Time2: ',(GetSeconds-Time):5:2,'cek. Min2: ',min2:3);
end;
for i:=1 to 5 do begin
N:=0;
min2:=32000;
reset(fin);
while (not(eof(fin))and(N<i*200))do begin
inc(N);
readln(fin,Mt[N,1],Mt[N,2],Mt[N,3]);
end;
Time:=Getseconds;
evristika(N,min2);
writeln('N: ',N:3,' Time2: ',(GetSeconds-Time):5:2,'cek. Min2: ',min2:3);
writeln(fout,' Time2: ',(GetSeconds-Time):5:2,'cek. Min2: ',min2:3);
end;
readln;
{закрытие файлов}
close(fin);
close(fout);
end. |
|