РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ МЕТОДОМ ЖАДНЫХ АЛГОРИТМОВ. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

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

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

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

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

Рисунок 1. Алгоритм.

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

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

- К ним можно применить принцип жадного выбора.

- К ним применимо свойство оптимальности для подзадач.

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

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

Существует определенная схема доказательства оптимальности:

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

2. Объясняется, что подзадача, которую надо решить после первого шага, идентична данной.

3. Рассуждение идет от частного к общему.

Если наилучшее решение содержит наилучшее решение подзадач, то задача содержит свойство оптимальности для подзадач.

Если рассматривать принцип динамического программирования, то алгоритм в этом случае строится так:

1.Необходимо правильно понять условие;

2. Необходимо так разбить задачу, чтобы лучшее решение задачи содержало лучшие решения всех подзадач.

3. Необходимо найти рекуррентное соотношение;

4. Необходимо вычислить самое лучшее значение параметра для всей задачи. На этом этапе рассматриваются два варианта:

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

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

2) Если же рекурсия невозможна, то используют другой подход:

- сначала находятся решения для элементарных подзадач,

- потом находят только такие, которые используют результаты уже решенных подзадач. Этот метод получил название снизу вверх.

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

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

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

1.вероятным, он должен удовлетворять условиям задачи;

2.локально оптимальным;

3. окончательным, если он уже сделан, то не может быть изменен.

Важно отметить, что методом жадного выбора не всегда можно получить верное решение.

Рассмотрим задачу и посмотрим, как будет работать жадный алгоритм.

Необходимо разменять 98 копеек монетами достоинством 1 копейка, 2 копейки, 5 копеек, 10 и 25 копеек таким образом, чтобы число монет было наименьшим.

Что же будет делать жадный алгоритм? На каждом шаге он будет выбирать самые крупные монеты.

1 шаг: выбираем три монеты по 25 копеек. У нас остается 23.

2 шаг: выбираем две монеты по 10 копеек. Осталось 3.

3 шаг: выбираем 2 копейки. Осталась 1

4 шаг: выбираем последнюю монету в 1 копейку.

Таким образом, жадный алгоритм предложил нам такое решение: 7 монет.

Теперь рассмотрим пример размена 15 копеек монетами в 1, 2 и 11 копеек.

1 шаг: берем монету в 11 копеек.

2 шаг: берем четыре монеты по 1 копейки.

Таким образом, мы получим решение в 5 монет, хотя эту сумму можно набрать тремя монетами по 5 копеек.

Метод динамического программирования дал бы на правильный ответ.

Жадные алгоритмы очень просты, но, несмотря на это, надо понимать, когда его целесообразно применять.

Список литературы:

1. Балдин, К.В. Математическое программирование: Учебник / К.В. Балдин, Н.А. Брызгалов, А.В. Рукосуев. - М.: Дашков и К, 2013. - 220 c.

2. Гринченков, Д.В. Математическая логика и теория алгоритмов для программистов: Учебное пособие / Д.В. Гринченков, С.И. Потоцкий. - М.: КноРус, 2013. - 206 c.

3.  Игошин, В.И. Теория алгоритмов: Учебное пособие / В.И. Игошин. - М.: ИНФРА-М, 2013. - 318 c.

4.  Крупский, В.Н. Математическая логика и теория алгоритмов: Учебное пособие для студентов учреждений высшего проф. образования / В.Н. Крупский, В.Е. Плиско. - М.: ИЦ Академия, 2013. - 416 c.