Динамическое программирование. Задача о загрузке
Постановка классической задачи о рюкзаке. Основные способы решения задачи комбинаторной оптимизации. Выбор алгоритма решения задач и определение его сложности. Построение математической модели решения задач. Описание процедур и функций программ.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 08.12.2014 |
Размер файла | 718,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования и науки Российской Федерации
ФГБОУ ВПО Саратовский Государственный Университет
имени Н.Г. Чернышевского
Колледж радиоэлектроники имени П.Н. Яблочкова
КУРСОВАЯ РАБОТА
Программирование в компьютерных системах
Динамическое программирование. Задача о загрузке
Введение
1. Основная часть
1.1 Способы решения задач
1.2 Выбор алгоритма решения задач и определение его сложности
1.3 Построение математической модели решения задач
2. Расчетная часть
2.1 Расчет тестового примера
2.2 Описание процедур и функций программ
Заключение
Список использованных источников
Приложения
Введение
Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес wi и полезность pi , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.
Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.
Рассматриваемая нами задача является NP - полной, то есть для нее не существует полиномиального алгоритма , решающего её за разумное время, в этом и есть проблема. Либо мы выбираем быстрый алгоритм, но он как известно не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным для больших значений. Существует несколько модификаций задачи.
1) Каждый предмет можно брать только один раз.
2) Каждый предмет можно брать сколько угодно раз.
3) Каждый предмет можно брать определенное количество раз
4) На размер рюкзака имеется несколько ограничений.
5) Некоторые вещи имею больший приоритет, чем другие
Цель данной работы - описать метод задачи о загрузке методом динамического программирования.
Основной задачей курсового проектирования является реализовать алгоритм решения классической задачи о рюкзаке методом динамического программирования.
Постановка задачи о рюкзаке.
Задача о ранце - одна из задач комбинаторной оптимизации. Классическая задача о ранце известна очень давно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W - вместимость ранца. Традиционно полагают что Wi , Vi , W, P - целые неотрицательные числа, но встречаются и другие постановки, условия в которых могут отличаться. Возможны следующие вариации задачи:
Каждый предмет можно брать только один раз. Формализуем.
Пусть задано конечное множество предметов , для каждого , определена стоимость pi и вес wi , тогда нужно максимизировать
при ограничениях
где W-вместимость ранца, а xi=1, если предмет взят для загрузки и xi=0 если не взят. Если на размер рюкзака имеется только одно ограничение, то задача называется одномерной, в противном случае - многомерной.
Каждый предмет можно брать m раз. Формализация аналогична, разница лишь в том, что xi принимает значения на интервале (0..m).
Каждый предмет можно брать неограниченное количество раз. Очевидно, что xi лежит в диапазоне (0..[W/wi]) квадратные скобочки означают целую часть числа.
Если же значения весов и цен предметов не целые числа, такая задача будет называться непрерывной задачей о рюкзаке, если же числа целые, то соответственно дискретной. Например, если мы имеем дело с золотыми слитками, мы не можем их делить - это дискретная задача, а если с золотым песком, то это непрерывная задача о рюкзаке.
NP - полнота задачи.
Большинство используемых алгоритмов имеют полиномиальное время работы, если размер входных данных - n, то время их работы в худшем случае оценивается как
где k это константа. Но встречаются задачи, которые нельзя разрешить за полиномиальное время. Это класс NP - полных задач. Некоторые задачи этого класса на первый взгляд аналогичны задачам разрешимым за полиномиальное время, но это далеко не так. Задача называется NP - полной, если для нее не существует полиномиального алгоритма. Алгоритм называется полиномиальным, если его сложность O(N) в худшем случае ограничена сверху некоторым многочленом (полиномом) от N. Такие задачи возникают очень часто в различных областях: в булевой логике, в теории графов, теории множеств, кодировании информации, в алгебре, в биологии, физике, экономике, теории автоматов и языков. Считается что NP - полные задачи очень трудноразрешимы, а так же, что если хотя бы для одной из них удастся найти полиномиальный алгоритм, то такой алгоритм будет существовать для любой задачи из этого класса.
Над поиском полиномиальных алгоритмов к таким задачам трудились многие ученые, и все же и все же при таком разнообразии NP - полных задач, ни для одной из них до сих пор не найдено полиномиального алгоритма.
Из всего вышесказанного следует, что если известна NP - полнота задачи, то лучше потратить время на построение приближенного алгоритма, чем пытаться построить полиномиальный, или же, если это позволяют условия, использовать алгоритмы с экспоненциальной сложностью работы.
1. Основная часть
задача алгоритм программа комбинаторный
1.1 Способы решения задач
На практике очень часто возникают NP-полные задачи, задач о рюкзаке одна из них. Конечно надежд, на то, что для них найдется, полиномиальный алгоритм практически нет, но из этого не следует, что с задачей нельзя ничего сделать. Во первых, очень часто удается построить полиномиальный алгоритм для NP - полной задачи, конечно он даст приближенное, а не точное решение, но зато будет работать за реальное время. Во вторых, данные могут быть таковы, что экспоненциальный алгоритм, например переборный сможет работать на них разумное время. К точным методам относятся: Полный перебор, метод ветвей и границ, ДП - программирование. К приближенным: Жадные алгоритмы. Полный перебор - перебор всех вариантов (всех состояний) - малоэффективный, но точный метод. Метод ветвей и границ - по сути, сокращение полного перебора с отсечением заведомо “плохих” решений. ДП - алгоритм, основанный на принципе оптимальности Беллмана. Жадный алгоритм - основан на нахождении относительно хорошего и “дешевого” решения.
1.2 Выбор алгоритма решения задач и определение его сложности
Проанализировав перечисленные методы решения задач, выбираем динамическое программирование. Данный метод дает точное решение и выполняет все поэтапно.
В основе метода динамического программирования лежит принцип оптимальности Беллмана: ” Какого бы ни было состояния системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующих шагах был оптимальным”.
Проще говоря, оптимальное решение на i шаге находится исходя из найденных ранее оптимальных решений на предшествующих шагах. Из этого следует, что для того чтобы найти оптимальное решение на последнем шаге надо сначала найти оптимальное решения для первого, затем для второго и так далее пока не пройдем все шаги до последнего.
1.3 Построение математической модели решения задач
Имеется набор из N предметов. Пусть MaxW - объем рюкзака, Pi - стоимость i-го предмета, Wi - вес i-го предмета. Value [W, i] - максимальная сумма, которую надо найти. Суть метода динамического программирования на каждом шаге по весу 1<Wi<W находим максимальную загрузку Value[Wi, i], для веса Wi. Допустим мы уже нашли Value[1..W, 1..i-1], то есть для веса меньше либо равного W и с предметами, взятыми из 1..N-1. Рассмотрим предмет N, если его вес WN меньше W проверим стоит ли его брать.
Если его взять то вес станет W-Wi , тогда Value[W, i] = Value[W - Wi , i-1] + Pi (для Value[W - Wi , i-1]) решение уже найдено остается только прибавить Pi.
Если его не брать то вес останется тем же и Value[W , i] = Value [W - Wi, i-1]. =Из двух вариантов выбирается тот, который дает наибольший результат. Рассмотрим алгоритм подробнее.
Рис 1.1 Решение примера
Рис 1.2 Решение примера
Рис 1.3 Решение примера
Динамическое программирование для задачи о рюкзаке дает точное решение, причем одновременно вычисляются решения для всех размеров рюкзака от 1 до MaxW, но какой ценой? Для хранения таблицы стоимости и запоминания того, брался каждый предмет или нет, требуется порядка O(N*MaxW) памяти, временная сложность равна O(N*MaxW);
Опишем основную логику решения:
{Загружаем рюкзак если его вместимость = Weight} for Weight:=1 to MaxW do begin
for i:=1 to N do {берем предметы с 1 по N}
{если вес предмета больше Weight}
{или предыдущий набор лучше выбираемого}
if (W[i]>Weight) or (Value[Weight, i-1] >=
Value[Weight-W[i], i-1]+P[i]) then begin
{Тогда берем предыдущий набор}
Value[Weight, i]:=Value[Weight, i-1];
{говорим что вещь i не взята}
Take [Weight, i]:= false;
End
{иначе добавляем к предыдущему набору текущий предмет}
Else begin
Value [Weight, i]:=Value [Weight - W[i], i-1]
+P[i];
{говорим что вещь i взята}
Take [Weight, i]:= true;
End; End;
Блок схема основного алгоритма
Как было сказано ранее, алгоритм динамического программирования для `рюкзака' дает точное решение путем использования дополнительной памяти O(N*MaxW), временная сложность алгоритма так же будет порядка O(N*MaxW).
2. Расчетная часть
2.1 Расчет тестового примера
Контрольная работа содержит вопросы по N различным темам. Каждый вопрос типа i имеет вес Vi(i=1,2,…N), а также время, отводимое на ответ Wi. Максимально время, которое может затратить студент на контрольную работу W. Требуется определить максимальное количество баллов (вес), которое может набрать студент за отведенное время W=30. Данные приведены в таблице:
I |
Wi |
Vi |
|
15 26 34 43 5 66 75 87 |
2 3 1 4 7 5 3 2 |
2 3 2 4 6 5 4 2 |
Решить задачу, приведя ее к рекуррентным соотношениям. Сначала рассмотрим задачу в общей постановке.
Если обозначить количество вопросов типа і через ki, то задача принимает следующий вид
при ограничениях
ki-неотрицательные числа.
Если отбросить требования целочисленности ki, то решение задачи нетрудно найти с помощью симплекс-метода. В самом деле, так как остается лишь одно ограничение, базисной будет только одна переменная, и задача сводится к выбору типа і, для которого величина viW/wi принимает максимальное значение. Исходная задача не является задачей линейного программирования, и для ее решения необходимо использовать метод динамического программирования. Следует отметить, что рассматриваемая задача может быть также решена с помощью методов целочисленного программирования. Каждый из трех основных элементов модели ДП определяется следующим образом.1.Этап j ставится в соответствии типу j, j=1,2,…,N.2. Состояние yj на этапе j выражает суммарный вес вопросов, количество ответов на которые приняты на этапах j,j+1,…,N; при этом y1=W и yj=0,1,…,W при j=2,3,…,N.3. Варианты решения kj на этапе j описываются количеством вопросов типа j. Значение kj заключено в пределах от нуля до [W/wj], где [W/wj]-целая часть числа (W/wj). Пусть fi(yi)-максимальный суммарный вес вопросов, ответы на которые приняты на этапах j,j+1,…,N при заданном состоянии yj. Рекуррентное соотношение (для процедуры обратной прогонки) имеет следующий вид
Заметим, что максимальное допустимое значение kj ограничено величиной [yj/wj].
Это позволяет автоматически исключать все не являющиеся допустимыми варианты при заданном значении переменной состояния yj. Решение исходной задачи (см. приложение А):
Этап 8.
Этап 7.
Этап 6.
Этап 5.
Этап 4.
Этап 3.
Этап 2.
Этап 1.
Оптимальное решение определяется теперь следующим образом.
Из условия W=30 следует, что первый этап решения задачи при y1=30 дает оптимальное решение k1=0, которое означает, что на 0 (нуль) вопросов 1-го типа будут даны ответы.
Далее находим:
y1=30 |
k1=0 |
|
y2=y1-2*k1=30 |
k2=0 |
|
y3=y2-4*k2=30 |
k3=4 |
|
y4=y3-k3=26 |
k4=1 |
|
y5=y4-4*k4=22 |
k5=0 |
|
y6=y5-7*k5=22 |
k6=0 |
|
y7=y6-5*k6=22 |
k7=5 |
|
y8=y7-3*k7=7 |
k8=7 |
Соответственно оптимальным решением задачи является (0,0,4,1,0,0,5,7), соответственно максимально количество баллов, которое студент может набрать за отведенное время равно 46.
2.2 Описание процедур и функций программ
Procedure Init - предназначена для считывания исходных данных задачи из файла. В качестве исходных данных используется имя текстового файла с данными для расчета. В качестве итога работы процедуры является заполнение массивов W - массив, предназначен для указания веса предмета и массив P - который предназначен для хранения стоимостей вещей.
Procedure Solve - основная процедура, предназначена для вычисления задачи о рюкзаке. Сначала обнуляется массив Take , выбирается оптимум для веса Weight, берутся предметы с 1 по n, если вес предмета больше чем текущий вес, или предыдущий набор дороже выбираемого, тогда берем предыдущий набор, указываем что вещь I не взята, иначе добавляем к предыдущему набору текущий предмет.
Procedure Done - предназначена для записи результата выходных данных задачи в текстовый файл. В файле выводится наилучший набор, и номер расположения его в столбце.
Заключение
В ходе выполнения курсовой работы была изучена теория решения задачи о загрузке и разработан алгоритм и его программная реализация, позволяющая пользователю находить решение задачи при любых входных параметрах. Для разработки программного обеспечения я использовал среду программирования Delphi.
Список использованных источников
1. Царев, В.А. Проектирование, анализ и программная реализация структур данных и алгоритмов: Учебное пособие [Текст] / В.А. Царев, А.Ф. Дробанов. Череповец., 2009. - 22 с.
2. Визгунов, Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB [Текст] / Н.П. Визгунов. - Н. Новгород.: ННГУ, 2008. - 48 с.
3. Кузюрин, Н.Н Сложность комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин, С.А.Фомин. - 2005. - 79 с.
4. Окулов, С. М - Программирование в алгоритмах [Текст] / С.М. Окулов. - М.: БИНОМ. Лаборатория знаний, 2004. - 341 с.: ил.
5 .Вентцель Е. С. Элементы динамического программирования. -М.: Наука,1987.
Приложение
Текст программы
Program kursov1;
{$APPTYPE CONSOLE}
Uses SysUtils;
Const MaxW = 200; MaxN = 100;
var Value:array [0..MaxW,0..MaxN] of integer; {массив значений (сколько можно набрать для 1..W весов в 1..N предметов)}
Take :array [0..MaxW,0..MaxN] of boolean; {массив значений брали предмет или нет}
W,P:array [0..MaxN] of integer; {Массив весов, массив цен}
i, N, Weight, MaxWeight :integer;
procedure Init;
// Begin assign(input,'input.txt');
reset(input); readln(N, MaxWeight);
for i:=1 to N do readln(W[i], P[i]);
close(input); end;
procedure Solve; begin
fillchar(Take, sizeof(Take), false); {обнуляем}
fillchar(Value, sizeof(Value), 0);
for Weight:=1 to MaxWeight do begin {выбираем оптимум для веса Weight}
for i:=1 to N do {берем предметы с 1 по N}
{если вес предмета больше чем текущий вес рюкзака}
{или предыдущий набор дороже выбираемого}
if (W[i]> Weight) or (Value[Weight, i-1] >= Value[Weight-W[i], i-1]+P[i]) then begin Value[Weight, i]:= Value[Weight, i - 1];
{тогда берем предыдущий набор}
Take[Weight, i]:= false; {говорим что вещь i не взята}
End
else begin {иначе добавляем к предыдущему набору текущий предмет}
Value[Weight, i]:= Value[Weight - W[i], i-1] +P[i];
Take[Weight, i]:= true; {говорим что вещь i взята}
end; end; end;
procedure Done;
begin assign(output,'output.txt');
rewrite(output);
Writeln('Наилучший набор ' , Value[MaxWeight, N]);
Weight:= MaxWeight;
for i:= N downto 1 do if Take[Weight, i] then begin
Write(i); Weight:= Weight-W[i];
end; close (output); end;
begin
Init; Solve; Done; end.
Размещено на Allbest.ur
...Подобные документы
Задача о ранце как задача комбинаторной оптимизации. Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи. Классификация методов решения задачи о рюкзаке. Динамическое программирование. Метод ветвей и границ. Сравнительный анализ методов.
курсовая работа [1,7 M], добавлен 18.01.2011Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.
курсовая работа [844,3 K], добавлен 16.06.2011Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.
контрольная работа [118,5 K], добавлен 11.04.2012Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo.
курсовая работа [586,3 K], добавлен 04.04.2015Основные принципы разработки программ. Разработка алгоритма решения задачи о пересечении двухвыпуклым многоугольником. Реализация разработанного алгоритма на языке программирования. Тесты для проверки работы программы. Графическая иллюстрация решения.
курсовая работа [53,3 K], добавлен 20.11.2015Транспортная задача как одна из самых распространенных специальных задач линейного программирования: понятие, основное назначение. Формальное описание метода минимального элемента. Характеристика этапов разработки алгоритма решения поставленной задачи.
курсовая работа [713,3 K], добавлен 19.10.2012Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
курсовая работа [195,5 K], добавлен 08.11.2009Написание программ для решения различных выражений и задач. При решении каждой задачи предусмотрены: анализ введенных с клавиатуры исходных данных, выведение условия для выхода и вывод результатов. Проиллюстрированы результаты работы каждой программы.
контрольная работа [259,8 K], добавлен 22.05.2010Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Теоретические и практические аспекты решения прикладных задач с применением функций и процедур структурного (модульного) программирования. Особенности разработки схемы алгоритма и программы для вычисления массива z на языке Turbo Pascal 7.0, их описание.
курсовая работа [241,7 K], добавлен 11.12.2009Использование информационных технологий для решения транспортных задач. Составление программ и решение задачи средствами Pascal10; алгоритм решения. Работа со средствами пакета Microsoft Excel18 и MathCad. Таблица исходных данных, построение диаграммы.
курсовая работа [749,1 K], добавлен 13.08.2012Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Описание решения задачи, ее постановка, общий подход к решению. Представление исходных данных, условий задачи и целей ее решения. Составление алгоритма решения поставленной задачи. Написание программного обеспечения и тестирование конечного продукта.
курсовая работа [1,1 M], добавлен 03.07.2011Метод решения математической модели на примере решения задач аналитической геометрии. Описание согласно заданному варианту методов решения задачи. Разработка математической модели на основе описанных методов. Параметры окружности минимального радиуса.
лабораторная работа [310,6 K], добавлен 13.02.2009Ханойские башни: постановка задачи, условия перемещения дисков со стержня на стержень. Стратегия решения, используемые предикаты. Текст программы на языке Пролог. Построение модели решения задачи о ферзях. Примеры использования списков в языке Пролог.
презентация [72,0 K], добавлен 29.07.2012Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Сущность и назначение основных алгоритмов оптимизации. Линейное программирование. Постановка и аналитический метод решения параметрической транспортной задачи, математическая модель. Метод решения задачи об оптимальных перевозках средствами MS Excel.
курсовая работа [465,6 K], добавлен 24.04.2009Задачи оптимизации. Ограничения на допустимое множество. Классическая задача оптимизации. Функция Лагранжа. Линейное программирование: формулировка задач и их графическое решение. Алгебраический метод решения задач. Симплекс-метод, симплекс-таблица.
реферат [478,6 K], добавлен 29.09.2008