Жадный алгоритм задача о рюкзаке

Жадный алгоритм для задачи о рюкзаке состоит в следующем (считаем, что все предметы помещаются в рюкзак):
– Выбрать максимально дорогой предмет, стоимости Cmax .
– Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно-дорогими» предметами, пока они влезают.

Пусть стоимость этого решения Cgreedy
В зависимости от того, что больше, Cmax или Cgreedy, выбрать первое или второе решение.
Этот алгоритм имеет сложность O(n log(n)), и гарантирует нахождение решения, не хуже чем в два раза от оптимального.

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

Принцип жадного выбора

Говорят, что к оптимизационной задаче применим принцип жадного выбора (greedy choice property), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берет "самый жирный кусок”, а потом уже пытается сделать наилучший выбор среди оставшихся вариантов, каковы бы они ни были. Алгоритм динамического программирования принимает решение, просчитав заранее последствие всех вариантов.

Оптимальность для подзадач

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

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

Примером может служить задача о рюкзаке – она состоит в том, чтобы уложить в рюкзак вещи таким образом, чтобы их суммарный вес не превышал предельного значения W и суммарная стоимость вещей была максимальна. Задача имеет две разновидности – непрерывная задача и дискретная. Например, вещи неделимы (золотой слиток) и делимы (золотой песок).

Пусть имеется n вещей, каждая из которых имеет стоимость v i и вес w i .

Стратегия жадного алгоритма состоит в следующем: рассчитывается удельная цена вещи c i = v i /w i .

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

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

Министерство образования и науки Российской Федерации. Государственное образовательное учреждение высшего профессионального образования «Вятский государственный гуманитарный университет»

Кафедра прикладной математики и информатики

Методы решения задачи о рюкзаке

Выполнил студент 3 курса группы ПМ-31

Перевощиков Сергей Владимирович

Научный руководитель: к.п.н, доцент кафедры

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

Разова Елена Владимировна

Глава 1 Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи

1.1 Постановка задачи о рюкзаке

1.2 NP – полнота задачи

Глава 2 Методы решения задачи о рюкзаке

2.1 Классификация методов

2.2 Динамическое программирование

2.3 Полный перебор

2.4 Метод ветвей и границ

2.5 Жадный алгоритм

2.6 Сравнительный анализ методов

2.7 Модификации задачи

Классическая задача о рюкзаке (о загрузке) известна очень давно, ниже приведена ее формализация. Пусть есть N разных предметов, каждый предмет имеет вес w_i и полезность p_i , так же имеется максимальный вес W, который можно положить в рюкзак. Требуется собрать такой набор предметов P, чтобы полезность их была наибольшей, а суммарный вес не превышал W.[6]. Конечно, никто не собирается писать программу, чтобы наилучшим образом загрузить рюкзак, отправляясь в поход или в путешествие, тут все слишком просто, и никто не задумывается об этом, но существует и более широкое применение.

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

Рассматриваемая нами задача является NP – полной, то есть для нее не существует полиномиального алгоритма , решающего её за разумное время, в этом и есть проблема. Либо мы выбираем быстрый алгоритм, но он как известно не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным для больших значений. Существует несколько модификаций задачи.

1. Каждый предмет можно брать только один раз.

2. Каждый предмет можно брать сколько угодно раз.

3. Каждый предмет можно брать определенное количество раз

4. На размер рюкзака имеется несколько ограничений.

5. Некоторые вещи имею больший приоритет, чем другие

Цель данной работы – выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.

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

Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм.

1.1 Постановка задачи о рюкзаке

Задача о ранце – одна из задач комбинаторной оптимизации. Классическая задача о ранце известна очень давно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W – вместимость ранца. Традиционно полагают что W_i , V_i , W, P – целые неотрицательные числа, но встречаются и другие постановки, условия в которых могут отличаться.[6] Возможны следующие вариации задачи:

Каждый предмет можно брать только один раз. Формализуем. Пусть задано конечное множество предметов

Каждый предмет можно брать m раз. Формализация аналогична, разница лишь в том, что x_i принимает значения на интервале (0..m).

Каждый предмет можно брать неограниченное количество раз. Очевидно, что x_i лежит в диапазоне (0..[W/w_i ]) квадратные скобочки означают целую часть числа. [6]

Если же значения весов и цен предметов не целые числа, такая задача будет называться непрерывной задачей о рюкзаке, если же числа целые, то соответственно дискретной. Например, если мы имеем дело с золотыми слитками, мы не можем их делить – это дискретная задача, а если с золотым песком, то это непрерывная задача о рюкзаке.

1.2 NP – полнота задачи

Большинство используемых алгоритмов имеют полиномиальное время работы, если размер входных данных – n, то время их работы в худшем случае оценивается как

2.1 Классификация методов

На практике очень часто возникают NP-полные задачи, задач о рюкзаке – одна из них . Конечно надежд, на то что для них найдется полиномиальный алгоритм практически нет, но из этого не следует что с задачей нельзя ничего сделать. Во первых, очень часто удается построить полиномиальный алгоритм для NP – полной задачи, конечно он даст приближенное, а не точное решение, но зато будет работать за реальное время. Во вторых, данные могут быть таковы, что экспоненциальный алгоритм, например переборный сможет работать на них разумное время. К точным методам относятся: Полный перебор, метод ветвей и границ, ДП – программирование. К приближенным: Жадные алгоритмы. Полный перебор – перебор всех вариантов (всех состояний) –малоэффективный, но точный метод. Метод ветвей и границ – по сути сокращение полного перебора с отсечением заведомо “плохих” решений. ДП – алгоритм, основанный на принципе оптимальности Беллмана. Жадный алгоритм – основан на нахождении относительно хорошего и “дешевого” решения.

2.2 Динамическое программирование

В основе метода динамического программирования лежит принцип оптимальности Беллмана:”Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующих шагах был оптимальным”. Проще говоря оптимальное решение на i шаге находится исходя из найденных ранее оптимальных решений на предшествующих шагах. Из этого следует, что для того чтобы найти оптимальное решение на последнем шаге надо сначала найти оптимальное решения для первого, затем для второго и так далее пока не пройдем все шаги до последнего.

Имеется набор из N предметов. Пусть MaxW – объем рюкзака, P_i – стоимость i-го предмета, W_i – вес i-го предмета. Value [W, i] – максимальная сумма, которую надо найти. Суть метода динамического программирования – на каждом шаге по весу 1

Ниже приведен алгоритм точного решения целочисленной задачи о рюкзаке. Предлагаемый алгоритм требует меньше вычислительных ресурсов и возможно несколько проще алгоритма динамического программирования (ДП).

Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.

Введение

Описание алгоритма решения задачи о рюкзаке с элементами псевдокода

INPUT: // Входные данные
Массивы исходных данных (ИД) содержат целые веса W и вещественные стоимости P предметов W(1. N) > 0 и P(1. N) > 0
где N число предметов и C > 0 – вместимость рюкзака.
OUTPUT: // Выходные данные
Булев массив X(1. N), где X(i) = 1, если предмет с номером i входит в решение, и X(i) = 0, если предмет с номером i не входит в решение.

START // начало алгоритма

Этап 1 // сортировка ИД
Сортируем ИД в порядке уменьшения удельной стоимости предметов:
P(1) / W(1) >= P(2) / W(2) >= . >= P(i) / W(i)>=… >= P( N) / W(N)
где P(i) > 0 стоимость предмета i , W(i) >0 вес предмета i.
В массиве X(1. N) все элементы первоначально = 0.
Для снижения потребности в памяти для алгоритма определяем минимальный вес в наборе ИД W_min = min( W )

Этап 2 // инициализация рабочих массивов
Создаем массив вещественных чисел LP размерностью (W_min… С)
и массив целых чисел LCr размерностью (W_min… С) . Заносим в массив LP и LCr данные первого элемента из отсортированного списка ИД
где P(1) стоимость и W(1) вес первого предмета в отсортированном списке ИД.

Этап 3 // заполнение рабочих массивов

Пусть W(i) и P(i) вес и стоимость текущего элемента ИД.
Создаем пустой массив вещественных чисел Clone размерностью (W_min… С).
Вносим в массив Clone стоимость текущего элемента ИД .
Копируем в массив Clone ненулевые данные из массива LP добавляя стоимость P(i) текущего элемента и увеличивая его индекс на его вес W(i), при условии что индекс в Clone не превзойдет вместимости рюкзака C.

Проводим модификацию массивов LP, LCr на основе данных массива Clone. Обновляем в массивах LP,LCr только те элементы стоимость которых в Clone больше чем в LP.

Этап 4 // формирование результата, обратный спуск
В массиве LP находим максимальное значение стоимости Pmax = MAX( LP ), это стоимость найденного оптимального решения. Индекс найденного в массиве элемента равен весу решения, обозначим его Wr, т.е. LP( Wr) = Pmax. Внесем первый найденный элемент в X:
далее

Выходим из цикла UNTIL и повторяем этапы 2, 3, 4 ( только на этапе 2 массивы LP, LCr не создаем, a заполняем нулями ). Повторять этап 1 (сортировка ИД) не нужно. Это по существу рекурсия, но из за предварительной сортировки ИД, она будет не глубокой. На некоторых наборах ИД рекурсии вообще может не быть. При повторе расчетов рассматриваем только те ИД, индекс которых меньше LCr( Wr ) и снижаем требуемый размер рюкзака до достигнутого веса Wr.

FINISH // конец алгоритма
Стоимость найденного решения Σ P(i) X(i), вес Σ W(i) X(i).
Правильность расчета итоговой стоимости рюкзака легко доказывается по индукции. Восстановление оптимального набора предметов, тоже не вызывает затруднений. Представленный алгоритм позволяет получить точное решение целочисленной задачи о рюкзаке.

Итоговые замечания

1. Общая сложность представленного алгоритма складывается из сложности сортировки ИД и сложности выполнения этапа 3 алгоритма (с учетом числа итераций). Время работы этапа 3 пропорционально числу предметов на вместимость рюкзака (N * C). Заранее определить число итераций достаточно сложно. Число итераций может варьироваться от до числа предметов в решении Σ X(i). При каждой итерации возникающей на этапе 4 объем вычислений на этапах 2, 3 уменьшается. Верхняя оценка временной сложности всего алгоритма не превышает N * C * ( число итераций + 1)
2. Потребность алгоритма в памяти пропорциональна вместимости рюкзака C и не зависит от числа предметов во входном наборе данных N, что выгодно отличает его от метода ДП.
3. Внутренние циклы этапа 3 легко выполняются параллельно.
4. При большом разбросе удельной стоимости предметов, если на этапе 3 алгоритма в верхней части массива LP перестают происходить изменения, можно прерывать этап 3 и не рассматривать оставшиеся предметы с низкой удельной стоимостью.
5. Если вместимость рюкзака С, достаточно велика, так что массивы размерности С не могут быть созданы по техническим причинам или веса предметов являются вещественными числами, то предложенный алгоритм может быть легко модифицирован заменой массивов связанными списками.
6. Является ли данный алгоритм полиномиальным или нет, я не берусь судить.