Практическая работа Вариант №5 (Домашняя работа 5 вариант)

МОСКВОСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

ПРАКТИЧЕСКАЯ РАБОТА

по дисциплине: «Методы оптимизации»

на тему: «Динамическое программирование»

Вариант №5

ВЫПОЛНИЛ:

студент 2-го курса гр ИТ-6

Кульнев А.М.

ПРОВЕРИЛ:

ст. преподаватель кафедры ИТ-6

Русаков А.М.

Цель работы:

1) Изучить метод динамического программирования.

2) Применить метод динамического программирования к решению практической задачи прокладки оптоволоконного кабеля между двумя пунктами A и B.

Исходные данные:

Ответы:

Стоимость минимального маршрута: 448

Маршрут прокладки кабеля за минимальную стоимость: sv sv sv sv sv

Алгоритм решения задачи:

Листинг программы:

function [min_stoimost,marshrut]=untitled2(dan)

clc

dan

ndem=length(dan);

for z=1:2:ndem

for i=1:2:z

j=ndem-z+i;

dan(i,j)=minimum(i,j,dan);

end

end

for z=3:2:ndem-1

for i=ndem:-2:z

j=i-z+1;

dan(i,j)=minimum(i,j,dan);

end

end

dan(ndem,1)=minimum(ndem,1,dan);

dannie_marshruta=dan;

min_stoimost=dan(ndem,1);

kol=1;

mar='';

i=ndem;

j=1;

while ((i>1) && (j<ndem+1))

[marij,ii,jj] = marshrutij(i,j,dan);

mar{kol}=marij;

i=ii;

j=jj;

kol=kol+1;

end

dannie_marshruta

mar

marshrut=mar;

function rez=minimum(i,j,dan)

ndem=length(dan);

sever=Inf;

vostok=Inf;

sv=Inf;

z=i-1;

if ((z>1) && (z<ndem))

sever=dan(z,j);

end

z=j+1;

if ((z>1) && (z<ndem))

vostok=dan(i,z);

end

zi=i-1;

zj=j+1;

if ((zi>1) && (zi<ndem) && ((zj>1) && (zj<ndem)))

sv=dan(zi,zj);

end

z=i-2;

if ((z>=1) && (z<=ndem))

sever=sever+dan(z,j);

end

z=j+2;

if ((z>=1) && (z<=ndem))

vostok=vostok+dan(i,z);

end

z1=i-2;

z2=j+2;

if ((z1>=1) && (z1<=ndem) && (z2>=1) && (z2<=ndem))

sv=sv+dan(z1,z2);

end

r=min(min(sever,sv),vostok);

if r==Inf

rez=0;

else

rez=r;

end

function [rez,ii,jj]=marshrutij(i,j,dan)

ndem=length(dan);

sever=Inf;

vostok=Inf;

sv=Inf;

z=i-2;

if ((z>=1) && (z<=ndem))

if ((dan(i,j)-dan(i-1,j))==dan(z,j))

sever=dan(z,j);

end

end

z=j+2;

if ((z>=1) && (z<=ndem))

if ((dan(i,j)-dan(i,j+1))==dan(i,z))

vostok=dan(i,z);

end

end

z1=i-2;

z2=j+2;

if ((z1>=1) && (z1<=ndem) && (z2>=1) && (z2<=ndem))

if ((dan(i,j)-dan(i-1,j+1))==dan(z1,z2))

sv=dan(z1,z2);

end

end

r='m';

m=min(sv,min(sever,vostok));

if sever==m

r='s v';

end

if vostok==m

r='v s';

end

if sv==m

r='sv';

end

ii=i-2;

jj=j+2;

rez=char(r);

Контрольная распечатка:

Вывод:

В результате проделанной работы научился решать группу задач по нахождению минимальной стоимости методом динамического программирования.

г.Москва 2012г.