Высокоцровневые методы информатики и првые методы информатики и программированияограммирования

5.8.6 Дп, жадный алгоритм или что-то другое?

Между ДП и жадными алгоритмам- и есть нечто общее. Решаемые с п омощью жадных алгоритмов зад- ачи, как и задачи, решаемые с помощью ДП, обладают свойством оптимальности для подзадач  ког- да оптимальное решение всей за- дачи содержит в себе оптимальные решения подзадач. Если А  оптимальный набор заявок, содержащий заявку 1, то А' = А \ {1}  оптимальный набор за- явок для подмножества заявок, для которых b[i] >= e[1]. Из-за этого об- щего свойства иногда может по- явиться желание применить ДП в ситуации, где хватило бы жадного алгоритма, или наоборот, приме- нить жадный алгоритм к задаче, в которой он не выдаст оптимально- го решения (как в дискретной зада- че о рюкзаке).

Алгоритм надо выбирать не толь- ко в зависимости от возможнос- тей, но и от ваших нужд (напри- мер, если нет четкой необ- ходимости получить самое опти- мальное решение). Яркий пример  та же задача коммивояжера. Алго- ритм ее решения NP-полон, что означает, что кроме как с помо- щью полного перебора задачу ре- шить невозможно (этот факт ма- тематически доказан). Да, для на- хождения самого краткого пути требуется экспоненциальное чис- ло шагов. А что, если задачу надо решить в краткий срок, причем хоть как-то минимизировать путь для обхода всех пунктов? На по- мощь приходит жадный алгоритм, который будет всего лишь при- близительным алгоритмом, но он найдет один из кратчайших (хотя и не обязательно самый корот- кий) вариантов обхода. Алгоритм работает таким образом. Допус- тим, мы находимся в вершине i. Рассмотрим расстояния от i ко всем вершинам, в которых мы еще не были, и выберем среди них вершину j с минимальным расстоянием к i. Далее, двигаем- ся в вершину j и проделываем для нее то же самое, что и для вершины i, и т.д. Остановимся тогда, когда во всех вершинах мы уже побывали, и соединим послед- нюю с первой. Общая сложность алгоритма  О(n²), и часто такой алгоритм дает решение, близкое к оптимальному.

Остается лишь дать ответ на не- сколько часто возникающих вопро- сов:

1) Как для конкретной задачи уз- нать, выдаст ли жадный алгоритм оптимальное решение? К сожале- нию, здесь нет общих рецептов. Кроме свойства оптимальности для подзадач существует еще одна особенность  это принцип жадно- го выбора. Говорят, что к задаче применим принцип жадного выбо- ра, если последовательность ло- кально-оптимальных (жадных) вы- боров дает глобально оптимальное решение. В общем случае нужно попытаться провести доказатель- ство, аналогичное тому, что было в доказательстве правильности ре- шения задачи о выборе заявок. Сначала мы показали, что жадный выбор на первом шаге не закрыва- ет путь к оптимальному решению: для любого решения есть другое, согласованное с жадным выбором и не хуже первого. Потом мы пока- зали„что подзадача, возникшая после жадного выбора на первом шаге, аналогична исходной. По ин- дукции следует, что такая последо- вательность жадных выборов дает оптимальное решение.

2) Какое же различие между жад- ными алгоритмами и динамичес- ким программированием? На каж- дом шаге жадный алгоритм берет «самый жирный кусок», а потом уже пытается сделать наилучший выбор среди оставшихся. ДП-алго- ритм принимает решение, просчи- тав заранее решения для всех под- задач.

Литература

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: "Вильямс", 2001. – 384 с.
Бентли Д. Жемчужины творчества программистов. – М.: Радио и связь, 1990.
Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.
Вирт Н. Алгоритмы и структуры данных. – М: Мир, 1989. – 360 с.
Грин Д., Кнут Д. Математические методы анализа алгоритмов. – М: Мир, 1987.
Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981.
Дейкстра Э. Дисциплина программирования. – М: Мир, 1978.
Кнут Д.Е. Искусство программирования для ЭВМ. В 3-х томах. – М.: Мир, 1976.
Кнут Д.Е. Искусство программирования. В 3-х томах. – М.: "Вильямс", 2000.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. – М.: МЦНМО, 2001.
Лэгсам Й., Огенстайн М. Структуры данных для персональных ЭВМ. – М.: Мир, 1989. – 586с.
Матьяш В.А., Путилов В.А., Фильчаков В.В., Щекин С.В. Структуры и алгоритмы обработки данных. – Апатиты, КФ ПетрГУ, 2000. – 80 с.
Оре О. Графы и их применение. – М.: Мир, 1965.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980.
Сибуя М., Ямамото Т. Алгоритмы обработки данных. – М: Мир, 1986. – 218 с.
Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987.
Харари Ф. Теория графов. – М: Мир, 1973.

Русскоязычные ресурсы InterNet

http://algo.4u.ru/
http://algolist.manual.ru/
http://alglib.chat.ru/
http://algo.do.ru/
http://hcinsu.chat.ru/
http://algolist.da.ru/
http://progstone.narod.ru/links/wantalgo.html
http://www.sevmashvtuz.edu/links/algorithms.html

Содержание