рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 2002 году

Жадный алгоритм или динамическое программирование - Курсовая Работа, раздел Программирование, - 2002 год - "Математико" Жадный Алгоритм Или Динамическое Программирование. И Жадные Алгоритмы, И Дина...

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

Мы проиллюстрируем возможные ловушки на примере двух вариантов классической оптимизационной задачи.

Дискретная задача о рюкзаке 0-1 knapsack problem состоит в следующем. Пусть вор пробрался на склад, на котором хранится n вещей. Вещь номер i стоит vi долларов и весит wi килограммов vi и wi - целые числа.

Вор хочет украсть товара на максимальную сумму, причем максимальный вес, который он может унести в рюкзаке, равен W число W тоже целое. Что он должен положить в рюкзак Непрерывная задача о рюкзаке fractional knapsack problem отличается от дискретной тем, что вор может дробить краденые товары на части и укладывать в рюкзак эти части, а не обязательно вещи целиком если в дискретной задаче вор имеет дело с золотыми слитками, то в непрерывной с золотым песком.

Обе задачи о рюкзаке обладают свойством оптимальности для подзадач. В самом деле, рассмотрим дискретную задачу. Вынув вещь номер j из оптимально загруженного рюкзака, получим решение задачи о рюкзаке с максимальным весом W wj и набором из n-1 вещи все вещи, кроме j-й. Аналогичное рассуждение подходит и для непрерывной задачи вынув из оптимально загруженного рюкзака, в котором лежит w килограммов товара номер j, весь этот товар, получим оптимальное решение непрерывной задачи, в которой максимальный вес равен W- w вместо W, а количество j-го товара равно wj-w вместо wj. Хотя две задачи о рюкзаке и похожи, жадный алгоритм дает оптимум в непрерывной задаче о рюкзаке и не дает в дискретной.

В самом деле, решение непрерывной задачи о рюкзаке с помощью жадного алгоритма выглядит так. Вычислим цены в расчете на килограмм всех товаров цена товара номер i равна viwi. Сначала вор берет по максимуму самого дорогого товара если весь этот товар кончился, а рюкзак не заполнен, вор берет следующий по цене товар, затес следующий, и так далее, пока не наберет вес W. Поскольку товары надо предварительно отсортировать по ценам, на что уйдет время Оn logn, время работы описанного алгоритма будет Оn logn. Чтобы убедиться в том, что аналогичный жадный алгоритм не обязан давать оптимум в дискретной задаче о рюкзаке, взгляните на рис. 2а. Грузоподъемность рюкзака 50кг, на складе имеются три вещи, весящие 10, 20 и 30кг и стоящие 60, 100 и 120 долларов соответственно.

Цена их в расчете на единицу веса равна 6,5 и 4. Жадный алгоритм для начала положит в рюкзак вещь номер 1 однако оптимальное решение включает предметы номер 2 и 3. Для непрерывной задачи с теми же исходными данными жадный алгоритм, предписывающий начать с товара номер 1, дает оптимальное решение рис. 2в. В дискретной задаче такая стратегия не срабатывает положив в рюкзак предмет номер 1, вор лишается возможности заполнить рюкзак под завязку, а пустое место в рюкзаке снижает цену наворованного в расчете на единицу веса. Здесь, чтобы решить, класть ли данную вещь в рюкзак, надо сравнить решения двух подзадач когда данная вещь заведомо лежит в рюкзаке и когда этой вещи в рюкзаке заведомо нет. Тем самым дискретная задача о рюкзаке порождает множество перекрывающихся подзадач типичный признак того, что может пригодиться динамическое программирование.

И действительно, к дискретной задаче о рюкзаке оно применимо. Рис. 2. В дискретной задаче о рюкзаке жадная стратегия может не сработать. а Вор должен выбрать две вещи из трех с тем, чтобы их суммарный вес не превысил 50кг. б Оптимальный выбор вторая и третья вещи если положить в рюкзак первую, то выбор оптимальным не будет, хотя именно она дороже всех в расчете на единицу веса. в Для непрерывной задачи о рюкзаке с теми же исходными данными выбор товаров в порядке убывания цены на единицу веса будет оптимален.

Вещь3 50 30120 100 100 60 120 602080 100 603030Вещь2 302020Вещь1 20201010101060100120рюкзак 220 160 180 240 а б в Глава 2 1. Применение жадного алгоритма.

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

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

Итак, можно сделать определенные выводы о том, что должен делать компьютер, когда он принимает решение, куда поставить выпавшее число. Рассмотрим процедуру принятия решения компьютером procedure Tform1.MCxinteger x-число которое выпало из колоды var s1,s2real p1,o1,p, o,x1,y1integer qwpat begin MVxMVx-1 массив, который отвечает за числа оставшиеся в колоде s21000 x10 y10 if n1 then число выпавшее первым ставиться в клетку с координатой 1,1. begin x11 y11 p1 o1 end else for p1 to 5 do for o1 to 5 do if ap, o0andverp, o,x1 then если в данной клетке нет числа, то в нее заносится число begin s10 ap, ox for p11 to 5 do qwp1ap, p1 составляется комбинация по строке s1reitqw и считается е возможный рейтинг for p11 to 5 do qwp1ap1,p составляется комбинация по столбцу s1s1reitqw и считается е возможный рейтингв сумме с предыдущим if po then begin for p11 to 5 do qwp1ap1,p1 составляется комбинация по диагонали s1s1reitqw и считается е возможный рейтингв сумме с предыдущим end if p6-o then begin for p11 to 5 do qwp1ap1,6-p1 чем меньше рейтинг, тем больше шансов выпасть s1s1reitqw у комбинации см. функцию REIT end if s1 s2 then проверка оптимума для данной позиции begin s2s1 x1p X1 и Y1 необходимые координаты клетки y1o end ap, o0 end stringgrid2.Cellsx1,y1inttostrx Устанавливаем число ax1,y1x mcva, ver if n25 then for p1 to 5 do for o1 to 5 do begin case p of 1cm1oap, o 2cm2oap, o 3cm3oap, o 4cm4oap, o 5cm5oap, o end case o of 1cm6pap, o 2cm7pap, o 3cm8pap, o 4cm9pap, o 5cm10pap, o end if p6-o then cm12pap, o if po then cm11pap, o end end Компьютер при принятии решения каждый раз обращается к данной процедуре, в которой выпавшее число устанавливается в каждую пустую клетку.

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

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

Это и есть жадный алгоритм. 2. Правила игры. Имеется набор из 52 карточек, на которых записаны числа от 1 до 13, причем карточки с каждым из этих чисел встречаются четырежды.

Имеется квадратное поле с 25 клетками. Программа случайным образом извлекает какую-либо из этих карточек и выдает записанное на ней число. Каждый игрок вы и компьютер заносит это число в одну из клеток квадрата. Так продолжается до тех пор, пока все клетки квадрата не будут заполнены.

По окончании игры заполнение соответствующего квадрата оценивается определенным количеством очков. Цель игры разместить числа в клетках так, чтобы набрать наибольшее количество очков в соответствии с данной таблицей Комбинация чиселВ ряду или столбцеПо диагоналиЗа 2 одинаковых числа10 очков20 очковЗа 2 пары одинаковых чисел20 очков30 очковЗа 3 одинаковых числа40 очков50 очковЗа 3 одинаковых числа и два других одинаковых числа80 очков90 очковЗа 4 одинаковых числа160 очков170 очковЗа 5 последовательных чисел, но необязательно по порядку расположенных50 очков60 очковЗа три раза по 1 и два раза по 13100 очков110 очковЗа числа 1,10,11,12 и 13, но необязательно по порядку расположенных150 очков160 очковЗа 4 единицы200 очков210 очков 3.

– Конец работы –

Эта тема принадлежит разделу:

"Математико"

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

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Правильность алгоритма
Правильность алгоритма. Не для всех задач жадный алгоритм дает оптимальное решение, но для нашей дает. Убедимся в этом. Теорема 1. Алгоритм Greedy-Activity- Selector дает набор из наибольшего возмо

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

Оптимальность для подзадач
Оптимальность для подзадач. Говоря иными словами, решаемые с помощью жадных алгоритмов задачи обладают свойством оптимальности для подзадач have optimal substructure оптимальное решение всей задачи

Руководство пользователя
Руководство пользователя. Перед вами игровое поле Ваше поле - поле, которое заполняете вы сами. Поле компьютера - поле, которое заполняет компьютер. Число - число, которое выпало, его и надо

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги