Практическая работа Вариант №5 (1085637)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

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

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

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

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

Вариант №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г.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов домашнего задания