Задача о ранце
Содержание и методы решения задачи о рюкзаке: динамическое программирование, полный перебор, ветвей и границ, жадный алгоритм. Сравнительная характеристика названных методов, условия их применения и оценка эффективности. Анализ полученных результатов.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 26.09.2017 |
Размер файла | 427,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Курсовая работа
Задача о ранце
Введение
Наука уделяет все большее и большее внимание вопросам организации и управления, что приводит к необходимости анализа целенаправленных сложных процессов с точки зрения их организации и структуры. Потребности практики вызвали к жизни специальные методы, которые удобно объединять под названием «Исследование операций», под которым понимается применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности.
Целью исследования операций является выявление наилучшего способа действия при решении той или иной задачи. Главная роль при этом отводится математическому моделированию. Для построения математической модели необходимо иметь строгое представление о цели функционирования исследуемой системы и располагать информацией об ограничениях, которые определяют область допустимых значений.
Данная курсовая работа предназначена для закрепления знаний по дисциплине «Исследование операций». Одной из задач, изучаемой в рамках данной дисциплины, является задача о ранце. Именно ее мы и рассмотрим.
Пусть имеется набор предметов, каждый из которых имеет два параметра - вес и ценность. И есть рюкзак, определенной вместимости. Задача заключается в том, чтобы собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака.
Воспринимать задачу в буквальном смысле и создавать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход, никто не собирается, т.к. тут все слишком просто, но существует и более широкое применение, а именно данная задача широко применяется на практике в прикладной математике, криптографии, экономике, логистике, генетике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов, склада и т.д.
Задача является NP-полной, то есть для нее не существует полиномиального алгоритма, решающего её за разумное время, в этом и заключается проблема. Либо мы выбираем быстрый алгоритм, но он, как известно, не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным из-за того, что поиск точного решения для больших значений займет слишком много времени.
1. Основные цели и задачи
Цель данной работы - выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.
Задача о ранце - одна из задач комбинаторной оптимизации. Свое название получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий вес (или объём) всех предметов ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
2. Методы решения задачи о рюкзаке
На практике очень часто возникают NP-полные задачи, задача о рюкзаке - одна из них. Конечно, надежд, на то, что для них найдется полиномиальный алгоритм, практически нет, но из этого не следует, что с задачей нельзя ничего сделать. Во-первых, очень часто удается построить полиномиальный алгоритм для NP-полной задачи, конечно, он даст приближенное, а не точное решение, но зато будет работать за реальное время. Во-вторых, данные могут быть таковы, что экспоненциальный алгоритм, например, переборный, сможет тоже работать на них разумное время. К точным методам относятся: полный перебор, метод ветвей и границ, динамическое программирование. К приближенным: жадные алгоритмы. Полный перебор - перебор всех вариантов (всех состояний) - малоэффективный, но точный метод. Метод ветвей и границ - по сути, сокращение полного перебора с отсечением заведомо «плохих» решений. ДП - алгоритм, основанный на принципе оптимальности Беллмана. Жадный алгоритм - основан на нахождении относительно хорошего и «дешевого» решения. Рассмотрим каждый из них подробнее.
2.1 Динамическое программирование (ДП-алгоритм)
В основе метода динамического программирования лежит принцип оптимальности Беллмана: «Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующих шагах был оптимальным». Проще говоря, оптимальное решение на i-том шаге находится исходя из найденных ранее оптимальных решений на предшествующих шагах. Из этого следует, что для того чтобы найти оптимальное решение на последнем шаге надо сначала найти оптимальное решения для первого, затем для второго и так далее пока не пройдем все шаги до последнего.
Имеется набор из 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]. Из двух вариантов выбирается тот, который дает наибольший результат. Рассмотрим алгоритм подробнее:
Рисунок 2.1.1
Рисунок 2.1.2
Рисунок 2.1.3
Динамическое программирование для задачи о рюкзаке дает точное решение, причем одновременно вычисляются решения для всех размеров рюкзака от 1 до MaxW, но какой ценой? Метод очень трудоемок при больших входных данных.
2.2 Полный перебор
Название метода говорит само за себя. Чтобы получить решение нужно перебрать все возможные варианты загрузки. Здесь мы будем рассматривать такую постановку задачи. В рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено), каждый предмет типа I имеет вес Wi и стоимость Pi, i=(1,2..N). Требуется определить максимальную стоимость груза вес, которого не превышает W. Очевидна простая рекурсивная реализация данного подхода (рисунок 2.2.1). Временная сложность данного алгоритма равна O (N!). Алгоритм имеет сложность факториал и может работать лишь с небольшими значениями N. С ростом N, число вариантов очень быстро растет, и задача становится практически неразрешимой методом полного перебора. На рисунке 2.2.2 показано дерево перебора, дерево имеет 4 уровня. В каждом кружочке показан вес предмета, корень дерева - нулевой вес, то есть когда рюкзак пуст. Первый предмет можно выбрать четырьмя способами, второй - тремя, третий - двумя, а дальше можем взять только один оставшийся предмет.
Рисунок 2.2.1
Рисунок 2.2.2
N - Количество предметов. Пусть MaxW - объем рюкзака, Pi - стоимость i-го предмета, Wi - вес i-го предмета.
2.3 Метод ветвей и границ
По существу, данный метод - это вариация полного перебора, с исключениями заведомо не оптимальных решений. Для полного перебора можно построить дерево решений. Если у нас есть какое-то оптимальное решение P, мы пытаемся улучшить его, но если на рассматриваемой в текущий момент ветви решение заведомо хуже, чем P то следует остановить поиск и выбрать другую ветвь для рассмотрения. Например, на рисунке 2.2.2 есть ограничение на вес рюкзака W=5. Тогда используя метод ветвей и границ можно сократить дерево перебора до такого, рисунок 2.2.3. Видно сразу, что количество вариантов для перебора уменьшилось сразу. А именно осталось 8 вариантов исхода, вместо 24 ранее. Но не всегда получается отсеять достаточно много вариантов, чтобы скорость работы была заметно увеличена, всегда можно подобрать такие входные данные, для которых метод ветвей и границ даст оценку по времени идентичную полному перебору.
Рисунок 2.2.3
программирование рюкзак алгоритм
2.4 Жадный алгоритм
В случае применения жадного алгоритма поступаем так: сортируем предметы по убыванию стоимости единицы каждого. , где Pi - относительная стоимость единицы предмета i, Wi - вес предмета i, Vi - стоимость предмета i. Всего N предметов. Пытаемся поместить в рюкзак все что помещается, и одновременно наиболее дорогое по параметру P. Оценим сложность метода. Для сортировки нам потребуется плюс проход по N предметам в цикле. Итого , что в общем случае равно . Скорость работы относительно других алгоритмов высока, но если посмотреть более внимательно, видно, что точное решение мы получим не всегда. Обратим внимание на следующую таблицу ниже (Таблица 1):
Таблица 1
Номер предмета (i) |
Вес предмета (кг) |
Цена (У.е) |
Относительная цена (У.е/кг) |
|
1 |
10 |
60 |
6 |
|
2 |
20 |
100 |
5 |
|
3 |
30 |
120 |
4 |
Как видно, предметы уже отсортированы. Пусть в рюкзак помещается 50 кг, следуя алгоритму, берем первый предмет, затем второй, третий - уже не помещается. Таким образом, в рюкзаке у нас 30 кг стоимостью 160 у. е., оставшееся место 20 кг. Но если бы мы взяли второй и третий предметы, общий вес поместился в рюкзак, и стоимость его была бы 220 у. е. Жадный алгоритм не дает оптимального решения, поэтому он является приближенным алгоритмом. Оказывается, качество решения можно улучшить, если сравнить полученный результат с максимальным коэффициентом . Предполагается, что все предметы не превосходят размера рюкзака, в противном случае их можно просто исключить из рассмотрения.
Рассмотрим непрерывную задачу о ранце, условия для нее те же самые, отличие лишь в том, что мы можем взять часть предмета. То есть предметы можно делить. Пусть у нас есть тот же набор что и в таб. 1, тогда следуя жадному алгоритму, берем первый и второй предметы, полностью третий предмет не помещается, т.к. места осталось всего на 20 кг, но мы можем брать части предметов, тогда возьмем 2/3 веса третьего предмета, соответственно и 2/3 его стоимости, таким образом мы нагрузили рюкзак полностью, стоимость груза стала равна 240 у. е. Для непрерывной задачи о рюкзаке жадный алгоритм будет давать оптимальное решение.
3. Сравнительный анализ методов
3.1 Динамическое программирование (ДП-алгоритм)
Недостатки:
· Веса предметов целые, если брать вещественные значения, ДП - алгоритм неприменим;
· Для больших значений N количества предметов ДП-алгоритм работает O().
Достоинства:
· Высокая скорость работы по сравнению с другими алгоритмами (для не больших значений N<50);
· Получаем точное решение;
· Имеем оптимальные загрузки рюкзака для всех его весов от 1 до MaxW.
3.2 Полный перебор
Недостатки:
· Входные данные не велики, т.к. с их увеличением растет и время выполнения;
· Временная сложность O (N!).
Достоинства:
· Полный перебор дает точное решение;
· Простота реализации.
3.3 Метод ветвей и границ
Недостатки:
· В худшем случае работает как полный перебор.
Достоинства:
· Возможно значительное сокращение времени работы;
· Простота реализации.
3.4 Жадный алгоритм
Недостатки:
· Всегда можно предоставить такой набор, при котором решение будет не точным.
Достоинства:
· Высокое время работы, ограниченное только скоростью сортировки, в среднем O(NlogN);
· Может работать с большими значениями N;
· Не использует дополнительных ресурсов компьютера;
· Простота реализации.
4. Пример решения задачи с помощью пакета экономических расчетов (ПЭР)
Для демонстрации наличия работоспособного программного обеспечения, направленного на решение задач по дисциплине, в том числе и упомянутой задачи о рюкзаке, рассмотрим решение с помощью программного продукта «ПЭР» - пакета экономических расчетов. Для примера возьмем условия задачи из пункта «2.1 Динамическое программирование (ДП-алгоритм)», а именно:
v вместимость рюкзака = 5;
v количество предметов = 3:
1) W1 = 1, P1 = 6;
2) W2 = 3, P2 = 12;
3) W3 = 2, P3 = 10.
После запуска, выбора раздела и ввода названия задачи программа просит ввести количество состояний - по сути, на данном этапе нужно указать, сколько предметов перечислено в задаче. В нашей задаче 3 предмета:
Рисунок 4.1
Затем мы конкретизируем задачу:
Рисунок 4.2
В следующем окне программа просит ввести условия нашей задачи, а именно максимальный вес ранца и характеристики предметов:
Рисунок 4.3
После ввода задачи, т.к. входные данные, откровенно говоря, небольшие, ее решение происходит, практически мгновенно. Пользователю остается лишь выбрать раздел №5 «Решение задачи»:
Рисунок 4.4
И в этом разделе посмотреть весь ход решения, либо перейти к итоговой таблице с конечным результатом:
Рисунок 4.5
Вот как она (таблица с конечным результатом) выглядит для нашей задачи (как видим, ответ сошелся с ответом, показанным в разделе «2.1 Динамическое программирование (ДП-алгоритм)»)
Рисунок 4.6
5. Модификации задачи
Кроме классической постановки задачи существуют и ее модификации. Для ознакомления приведу примеры некоторых из них:
1. Необходимо вывести только максимальную стоимость, набор нас не интересует.
2. В результате работы нужно получить не только максимальную стоимость, но и сам набор.
3. На размер рюкзака несколько ограничений (многомерность задачи).
4. Каждый предмет можно брать только лишь один раз.
5. Предметы можно брать произвольное количество раз.
6. Количество раз помещения предмета в рюкзак фиксировано. Либо для каждого предмета свое, либо для всех предметов одно.
7. Некоторые предметы должны обязательно быть уложены в рюкзак (имеют приоритет).
8. Находить несколько оптимальных решений (одинаковой стоимости, но с разным содержимым).
Заключение
В ходе исследования задачи о рюкзаке были выявлены три основных алгоритма решения. Полный перебор, динамическое программирование, жадный алгоритм. Также был рассмотрен метод ветвей и границ, но как сокращение полного перебора. Все методы разделены на две группы. Первая группа - точные методы, сюда входят ДП-алгоритмы, полный перебор и метод ветвей и границ. Вторая группа - приближенные методы, к таким методам относится жадный алгоритм. Выбор использования того или иного метода спорный вопрос, все зависит от постановки задачи, а также от того, какие цели поставлены. Если требуется найти точное решение, то конечно нужно использовать точные методы, при небольшом наборе входных данных, подойдет перебор или метод ветвей и границ в силу простоты реализации, при больших, следует использовать ДП-алгоритм. Если же точность решения не так важна, или входные данные таковы, что ни один из точных методов не работоспособен, остается применять только приближенные алгоритмы. Но остается возможность комбинирования различных методов для ускорения, или даже применение каких-либо «уловок» для конкретного примера. Безусловно, данная задача очень важна с точки зрения ее приложения в реальной жизни. Несмотря на свою «древность», «рюкзак» не только не забывается, а наоборот, интерес к нему только растет. Оптимальная загрузка транспорта помогает сокращать расходы, получать большую прибыль. Также задача применяется в криптографии и прикладной математике. Также мы убедились, что есть уже готовое работающее программное обеспечение (ПЭР) для решения задач по заданной дисциплине, в том числе и задачи о ранце.
Список использованной литературы
1. Шикин Е.В., Шикина Г.Е. Исследование операций: учеб. - М.: ТК Велби, Изд-во Проспект, 2006. - 280 с.
2. Ананий В. Левитин Глава 3. Метод грубой силы: Задача о рюкзаке // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. - М.: «Вильямс», 2006. - С. 160-163. - ISBN 0-201-74395-7
3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М.: «Вильямс», 2006. - С. 1296. - ISBN 0-07-013151-1
Размещено на Allbest.ru
Подобные документы
Задача о ранце как задача комбинаторной оптимизации. Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи. Классификация методов решения задачи о рюкзаке. Динамическое программирование. Метод ветвей и границ. Сравнительный анализ методов.
курсовая работа [1,7 M], добавлен 18.01.2011Методы ветвей и границ первого и второго порядка. Оптимальный и пассивный поиск. Недостатки метода Ньютона. Метод золотого сечения. Примеры унимодальных функций. Динамическое и линейное программирование. Метод Жордана-Гаусса. Решение задачи коммивояжера.
курсовая работа [1,1 M], добавлен 20.07.2012Общая характеристика динамического программирования: задачи о коммивояжере, о назначении, о теории расписаний. Численные методы ветвей и границ, методы отсечения. Задачи целостного программирования с булевыми переменными. Аддиктивный метод Балаша.
учебное пособие [534,1 K], добавлен 11.07.2010Задача об оптимальном графе для децентрализованного поиска. Жадный алгоритм. Модель Клайнберга. Математическая модель. Алгоритмы решения. Алгоритм локального поиска. Табу алгоритм. Метод ветвей и границ. Выбор между одинаковыми соседями. Стартовый граф.
дипломная работа [4,1 M], добавлен 23.10.2016Особенности технологии параллельного программирования, описание компилятора OpenMP (Open Multi-Processing) и MPI (Message Passing Interface). Постановка задачи о ранце и пример ее решения на С++. Решение задачи о ранце на OpenMP со многими потоками.
магистерская работа [1,8 M], добавлен 08.03.2012Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012Методы решения задачи о ранце. Алгоритм неявного лексикографического перебора. Разработка структуры данных, реализация алгоритма с её использованием, программная реализация. Проведение тестовой проверки. Входной и выходной файл, листинг программы.
курсовая работа [408,8 K], добавлен 22.10.2012Обзор алгоритмов решения задачи: точные методы, генетический и жадный алгоритмы. Характеристика жадного алгоритма: его описание, анализ точности приближения, вычислительной сложности. Программная реализация и проверка корректности и быстродействия.
курсовая работа [228,7 K], добавлен 14.10.2017Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.
курсовая работа [493,3 K], добавлен 27.12.2008Концептуальная модель операции. Математическая постановка задачи. Описание метода ветвей и границ, прямого перебора. Проектирование сценария диалога. Описание структур данных. Ручная реализация решения задачи с помощью алгоритма Литла и перебора.
курсовая работа [202,6 K], добавлен 14.12.2013