Введение понятие комбинаторики


Когда применим жадный алгоритм



Download 0,79 Mb.
bet7/10
Sana10.02.2023
Hajmi0,79 Mb.
#909914
TuriРеферат
1   2   3   4   5   6   7   8   9   10
Bog'liq
алгоритм и программа решения задач комбинаторики

Когда применим жадный алгоритм


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

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


Говорят, что к оптимизационной задаче применим принцип жадного выбора, если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берёт «самый жирный кусок», а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были; алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.
Как доказать, что жадный алгоритм даёт оптимальное решение? Это не всегда тривиально, но в типичном случае такое доказательство следует схеме, использованной в задаче о заявках. Сначала мы доказываем, что жадный выбор на первом шаге не закрывает пути к оптимальному решению: для всякого решения есть другое, согласованное с жадным выбором и не худшее первого. Затем показывается, что подзадача, возникающая после жадного выбора на первом шаге, аналогична исходной, и рассуждение завершается по индукции.

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


Говоря иными словами, решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач: оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. (С этим свойством мы уже встречались, говоря о динамическом программировании.) Например, задаче о заявках мы видели, что если — оптимальный набор заявок, содержащий заявку номер 1, то  — оптимальный набор заявок для меньшего множества заявок  , состоящего из тех заявок, для которых  .

Жадный алгоритм или динамическое программирование?


И жадные алгоритмы, и динамическое программирование основываются на свойстве оптимальности для подзадач, поэтому может возникнуть искушение применить динамическое программирование в ситуации, где хватило бы жадного алгоритма или напротив, применить жадный алгоритм к задаче, в которой он не даст оптимума. Проиллюстрируем возможные ловушки на примере двух вариантов классической оптимизационной задачи.
Дискретная задача о рюкзаке состоит в следующем. На складе хранится вещей. Вещь номер стоит  гривен и весит  килограммов ( - целые числа). Необходимо набрать в рюкзак товара на максимальную сумму, причём максимальный вес, который можно унести в рюкзаке, равен  (число тоже целое). Что нужно положить в рюкзак?
Непрерывная задача о рюкзаке отличается от дискретной тем, что можно дробить товары на части и укладывать в рюкзак эти части, а не обязательно вещи целиком (если в дискретной задаче мы имеем дело с золотыми слитками, то в непрерывной — с золотым песком).
Обе задачи о рюкзаке обладают свойством оптимальности для подзадач. В самом деле, рассмотрим дискретную задачу. Вынув вещь номер из оптимально загруженного рюкзака, получим решение задачи о рюкзаке с максимальным весом  и набором из  вещи (все вещи, кроме -ой). Аналогичное рассуждение проходит и для непрерывной задачи: вынув из оптимально загруженного рюкзака, в котором лежит  килограммов товара номер , весь этот товар, получим оптимальное решение непрерывной задачи, в которой максимальный вес равен  (вместо ), а количество -го товара равно  (вместо ).
Хотя две задачи о рюкзаке и похожи, жадный алгоритм даёт оптимум в непрерывной задаче о рюкзаке и не даёт в дискретной. В самом деле, решение непрерывной задачи о рюкзаке с помощью жадного алгоритма выглядит так. Вычислим цены (в расчёте на килограмм) всех товаров (цена товара номер равна  ). Сначала берём по максимуму самого дорогого товара; если весь этот товар кончился, а рюкзак не заполнен, то берём следующий по цене товар, затем следующий, и так далее, пока не наберём вес Поскольку товары надо предварительно отсортировать по ценам, на что уйдёт время  , время работы описанного алгоритма будет .
Чтобы убедиться в том, что аналогичный жадный алгоритм не обязан давать оптимум в дискретной задаче о рюкзаке, рассмотрим следующий пример. Грузоподъемность рюкзака 50 кг. На складе есть три вещи, весящие 10, 20 и 30 кг и стоящие 60, 100 и 120 гривен соответственно. Цена их в расчёте на единицу веса равна 6, 5 и 4. Жадный алгоритм для начала положит в рюкзак вещь номер 1, а затем 2. Это даст 160 гривен. Но оптимальное решение включает предметы номер 2 и 3 и дает 220 гривен.
Для непрерывной задачи с теми же исходными данными жадный алгоритм даст правильное решение. В дискретной задаче, положив предмет номер 1, мы лишаемся возможности заполнить рюкзак «под завязку», а пустое место снижает цену товаров в рюкзаке. Здесь, чтобы решить, стоит ли класть вещь в рюкзак, следует рассмотреть две подзадачи: если данная вещь заведомо лежит в рюкзаке и если вещи заведомо нет. Тем самым дискретная задача порождает множество перекрывающихся подзадач – типичный признак того, что может пригодиться динамическое программирование. И действительно, в данном случае оно применимо.

Download 0,79 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   10




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish