Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ
end;
end;
if min1<>0 then min2:=0;
if min2>32000 then min2:=0;
l2[q]:=min2;
end;
for q:=1 to n do
begin
min1:=maxint;min2:=maxint;
for w:=1 to n do
if t^[i(q,w)]< >-1 then
begin
if min2> t^[i(q,w)] then min2:=t^[i(q,w)];
if min1> min2 then
begin
e:=min1;
min1:=min2;
min2:=e;
end;
end;
if min1<>0 then min2:=0;
if min2>32000 then min2:=0;
l1[q]:=min2;
end;
bz:=-32000;
bestx:=0;besty:=0;
for y:=n downto 1 do
for x:=1 to n do
if (t^[i(x,y)]=0) then
if l1[x]+l2[y]> bz then
begin
bestx:=x;
besty:=y;
bz:=l1[x]+l2[y];
end;
bestziro:=bz;
end;
begin
assign(input,'input.txt');
assign(output,'vetvi.out');
reset(input);
rewrite(output);
nochered:=0;
read(n);
sizeofm:=n*(n+2)*2+2;
start_m:=getid;
sm:=matrix[start_m];
for q:=1 to n do
for w:=1 to n do
read(sm^[i(w,q)]);
addochered(start_m,0);
{ ;
bestziro(start_m);}
{Sobstvenno reshenie}
best:=maxint;
while true do
begin
if nochered=0 then break;
getochered(workm,workc);
{process MATRIX}
inc(workc,simplize(workm));
if workc> best then goto skip;
sm:=matrix[workm];
if sm^[1]=n-1 then
begin
best:=workc;
for q:=1 to n do
begin
bestmatr [q]:=sm^[i(q,n+2)];
bestmatr1[q]:=sm^[i(q,n+1)];
end;
goto skip;
end;
q:=bestziro(workm);
if q=-32000 then goto skip;
{Pravaia vetka}
if(bestx=0) or (besty=0) then goto skip;
rightm:=getid;
move(matrix[workm]^,matrix[rightm]^,sizeofm);
sm:=matrix[rightm];
sm^[i(bestx,besty)]:=-1;
addochered(rightm,workc+q);
{Levaia vetka}
leftm:=getid;
move(matrix[workm]^,matrix[leftm]^,sizeofm);
sm:=matrix[leftm];
{Dobavliaetsia rebro iz bestx v besty}
inc(sm^[1]);
sm^[i(bestx,n+2)]:=besty;
sm^[i(besty,n+1)]:=bestx;
first:=bestx;last:=besty;
if sm^[1]< >n-1 then
begin
while true do
begin
if sm^[i(last,n+2)]=0 then break;
last:=sm^[i(last,n+2)];
end;
while true do
begin
if sm^[i(first,n+1)]=0 then break;
first:=sm^[i(first,n+1)];
end;
sm^[i(last,first)]:=-1;
sm^[i(first,last)]:=-1;
sm^[i(besty,bestx)]:=-1;
end;
for w:=1 to n do
begin
sm^[i(w,besty)]:=-1;
sm^[i(bestx,w)]:=-1;
end;
addochered(leftm,workc);
skip:
{Free Matrix}
freeid(workm);
end;
{ freeid(start_m);}
if best=maxint then
begin
writeln('Путь не существует');
end else
begin
writeln('Длина пути:',best);
for q:=1 to n do
if bestmatr[q]=0 then break;
e:=q;
for curr:=1 to n do
if bestmatr[curr]=q then break;
while true do
begin
write(curr,' ');
curr:=bestmatr1[curr];
if curr=0 then
begin
writeln(e);
break;
end;
end;
end;
close(input);
close(output);
end.
Вывод
При решении поставленной задачи оба метода дали одинаковый результат, что показывает правильность понимания и выполнения курсовой работы. Таким образом, необходимо использовать следующие параметры контроля: x9,x4,x10,x3,x7,x1,x2.
Метод динамического программирования достаточно прост для выполнения, но имеет существенный недостаток: при его использовании для счёта вручную возникают вычислительные трудности даже для простых систем.
Метод ветвей и границ является более сложным для понимания, но он оказался проще при ручном счёте. Недостатком является большая сложность программирования метода.
Литература
Селезнев А.В., Добрица Б.Т., Убар Р.Р. «Проектирование автоматизированных систем контроля бортового оборудования летательных аппаратов» стр. 90-95
Алексеев О.Г. «Комплексное применение методов дискретной оптимизации» стр. 18-25