Основные сведения о гимназии

Финансово-хозяйственная деятельность

Платные образовательные услуги

Стипендии и иные выплаты

Авторизация



Рейтинг@Mail.ru

Информатика и ИКТ в современной школе

 

 

GISMETEO: Погода по г. Руза

Жадные алгоритмы в решении задач (интегрированный курс математика - информатика)
(5 голоса, среднее 4.40 из 5)
Автор: Кучуева Н.П.   

 

Содержание

Введение……………………………………………………………….3

Понятие алгоритма, основные свойства……………………………..4

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

и жадные алгоритмы…………………………………………………..9

Задачи………………………………………………………………….12

Заключение……………………………………………………………20

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

 

 

 

Введение

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

В естественных науках, в частности программировании, актуальными являются задачи оптимизации. В таких задачах может существовать множество различных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). Многие такие задачи сравнительно быстро и просто решаются с помощью жадных алгоритмов. Такой алгоритм делает на каждом шаге локально оптимальный выбор, допуская, что итоговое решение также окажется оптимальным. Однако это не всегда так, но для большого числа алгоритмических задач жадные алгоритмы действительно дают оптимальное решение. Нужно отметить, что вопрос о применимости жадного алгоритма в каждом классе задач решается отдельно, однако для обоснования общего решения существует теория матроидов. В данной работе мы рассмотрим основные понятия, связанные с алгоритмами,  свойства алгоритмов, ознакомимся с понятием жадного алгоритма и основной идеей динамического программирования и рассмотрим способ реализации решения задач оптимизации с помощью данных алгоритмов на языках программирования Java и Pascal.

 

 

 

 

 

 

 

 

 

 Понятие алгоритма, основные свойства алгоритмов

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

Термин «Алгоритм» происходит от algorithmi - латинского написания имени Аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила выполнения четырех арифметических действий над ними в десятичной системе счисления.

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

Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численными алгоритмами.

Алгоритмы, в соответствии с которыми решение поставленных задач сводится к логическим действиям, называются логическими алгоритмами.

Примерами  логических алгоритмов могут служить алгоритмы поиска минимального числа, поиска пути на графе, поиски пути в лабиринте и другие.

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

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

Рассмотрим некоторые свойства алгоритмов:

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

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

Результативность (конечность) - алгоритм должен приводить к решению задачи за конечное число шагов.

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

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

  Первое правило –при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.

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

  Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

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

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

  Алгоритм – неопределяемое понятие теории алгоритмов. Алгоритм каждому определенному набору входных данных ставит в соответствие некоторый набор выходных данных, т. е. вычисляет (реализует) функцию. При рассмотрении конкретных вопросов в теории алгоритмов всегда имеется в виду какая-то конкретная модель алгоритма.

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

  Выделим следующие виды алгоритмов:

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

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

Эвристический алгоритм(от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.

Линейный алгоритм– набор команд (указаний), выполняемых последовательно во времени друг за другом.

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

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

  На практике наиболее распространены следующие формы представления алгоритмов:

–       словесная (записи на естественном языке);

–       графическая (изображения из графических символов);

–       псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

–       программная (тексты на языках программирования).

  Итак, мы ознакомились с некоторыми основными понятиями теории алгоритмов.

 

 

 

 

 

 

 

 

 

 

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

 

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

По своему принципу динамическое программирование напоминает метод «разделяй и властвуй»:  задача делится на подзадачи (которые либо являются очевидными, либо сводятся к своим подзадачам), и обединяются решения данных подзадач. Но есть и некоторые отличия: например, таких подзадач обычно относительно немного, что позволяет решить каждую подзадачу единожды, а результат занести в некий массив. Такой подход называется memoization. Небольшое кол-во подзадач, многие из которых приходится решать много раз называется перекрытием подзадач и является характерным признаком динамического программирования.Вторым характерным признаком излагаемого метода является оптимальность для подзадач. Говорят, что задача обладает таким свойством, если оптимальное решение задачи содержит оптимальные решения ее подзадач.

  Общий метод построения алгоритмов по принципу динамического программирования следующий:

1.     Хорошо понять условие;

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

3.     Написать рекуррентное соотношение (если мы разбиваем задачу на подзадачи, значит, можем выразить качество решения задачи либо через ее подзадачи, либо элементарным образом);

4.     Вычислить оптимальное значение параметра для всей задачи. Тут возможно два варианта:  если задача решается рекурсивно, значит процедура делит заданную ей задачу на подзадачи (предварительно выяснив, не является ли задача тривиальной и проверив, не решалась ли она ранее; тогда нужно лишь взять уже готовое решение из соответствующего массива) и, получив решение, «ставит флаг», что эта подзадача уже решена. Такое решение называется решением сверху вниз,  т.е. берем глобальную задачу, потом решаем только необходимые для нее подзадачи. Если же рекурсия невозможна по техническим или еще каким-нить причинам, то применяется такой подход: решаются сначала элементарные подзадачи, потом только те, которые требуют результатов уже решенных подзадач и т. д., пока не будет решена общая задача. Такой метод называется решением снизу вверх  в большинстве случаев он оказывается быстрее, но менее понятным и простым, хотя есть и исключения.

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

  Но для многих оптимизационных задач есть более простые и быстрые алгоритмы, чем динамическое программирование. Одними из них являются жадные алгоритмы. В жадном алгоритме(greedy algorithm) всегда делается выбор, который кажется самым лучшим в данный момент, т.е. производится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи. Динамическое программирование и жадные алгоритмы тесно связаны между собой. Связь их обусловлена наличием оптимальной подструктуры задачи, т.е. в оптимальном решении задачи находятся оптимальные решения подзадач. Жадный подход строит решение посредством последовательности шагов, на каждом из которых получается частичное решение  поставленной задачи, пока не будет получено полное решение. При этом на каждом шаге - и это является главным в рассматриваемом методе - выбор должен быть

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

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

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

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

  Рассмотрим простой пример задачи, решаемой жадным алгоритмом: 

Как выплатить сумму в 98 копеек монетами номиналом 1, 2, 5, 10 и 25 копеек так, чтобы общее количество монет было минимально?

Решение:

Жадный алгоритм в этом случае состоит в том, чтобы на каждом шаге построения решения использовать монеты  максимального номинала, с тем чтобы их было как можно меньше (достижение локального минимума). Сначала мы берем три монеты по 25 копеек (4 монеты дают сумму, большую чем требуется). Остается выплатить 98- 25*3=23 копейки.

На втором шаге мы берем очередные наибольшие по номиналу монеты, которыми можно выдать недостающую сумму, - две монеты по 10 копеек.

Два следующих шага дают нам по одной двух- и однокопеечной монете, тем самым позволяя выплатить всю сумму 7  монетами. (Заметим, что такой жадный алгоритм подходит не для любой суммы и набора монет -например,сумму в 15 копеек монетами 1,5 и 11 копеек можно выплатить тремя монетами по 5 копеек, но применение жадного алгоритма даст нам пять монет - 11 копеек и четыре монеты по 1 копейке. Однако, решая эту задачу методом динамического  программирования, мы получим правильный ответ).

  Как правило, жадные алгоритмы интуитивно привлекательны и просты. Но, несмотря на несомненную простоту применения, для каждой задачи требуется подчас весьма сложное доказательство  применимости жадного алгоритма для ее решения. Жадные алгоритмы основаны на сложной теории, базирующейся на абстрактной  комбинаторной структуре, которая носит название «матроид».

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

 

Задачи

 

Задача 1.  «ЗАДАЧА О РЮКЗАКЕ»

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

Путешественник собрался в поход. Перед ним 5 предметов, для каждого  известна ценность (стоимость) (4, 1, 8, 7, 1)  и определен вес (6, 5, 3, 1, 7) . Имеется рюкзак объема 15 . Требуется упаковать рюкзак так, чтобы общая ценность упакованных предметов была наибольшей и их общий вес не превосходил объем рюкзака.

Решение:

Составим таблицу значений, которая будет отображать соответствие между ценой и весом предметов:

предмет

цена

вес

 1

4

6

2

1

5

3

8

3

4

7

1

5

1

7

Жадный алгоритм для задачи о рюкзаке состоит в следующем:

вначале множество предметов  упорядочивается по убыванию «удельной ценности» (или цены единицы веса) предметов,  затем, начиная с пустого множества, к приближенному решению  (сначала оно пустое) последовательно прибавляются предметы из упорядоченного множества ;

при каждом очередном добавлении предмета в рюкзак выполняется проверка, не превосходит ли его вес величины оставшегося запаса объема рюкзака;

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

Приведем код программы, реализующий решение данной задачи, на языке java:

 

import static java.lang.Math.*;

   public class Rucksack {

   private int[] weight = {2, 2, 6, 5};

   private int[] value = {6 ,3, 5, 4};

      public  int rucksack(int i, int Capanoity){

        if (i == value.length - 1){

        if (Capanoity < weight[i])

        return 0;

        else

        return value[i];

        }

      else {

      if (Capanoity < weight[i]){

      return rucksack(i+1, Capanoity-weight[i]);

      }

      else

      return max(rucksack(i+1, Capanoity), rucksack(i+1,Capanoity - weight[i])+value[i]);

      }

   }

  

    public static void main(String[] args) {

        Rucksack demo = new Rucksack();

        System.out.println(max(20,45));

        System.out.println("Maximal rucksackvalue is: " + demo.rucksack(0, 10));

 

 

       }

  }

 

Такимобразом, Maximal rucksackvalue is: 14.

 

Задача 2.

Три станка обрабатывают детали с одинаковой скоростью. Известны длительности обработки nдеталей; порядок обработки не важен. Обработка деталей не прерывается- станок переключается на обработку следующей детали мгновенно. Необходимо так распределить детали между станками, чтобы обработка последней из них закончилась как можно скорее.

Решение:

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

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

Таким образом, получим (рассмотрим псевдкод на языке паскаль):

По этому алгоритму детали с длительностью обработки 12, 8, 7, 5, 4 распределяются по станкам так: 12, 8+4, 7+5. Очевидно, лучше быть не может. Однако, если длительности 12, 8, 7, 5, 4, 2, то жадный алгоритм даст распределение 12+2, 8+4, 7+5 с моментом окончания 14, хотя распределение 12, 8+5, 7+4+2 имеет момент окончания 13.

Можно сделать следующий вывод: с помощью жадного алгоритма можно решить  задачу, требующую перебора, очень быстро, но это решение может быть не наилучшим.

 

Задача 3.

Некий путешественник задумал повторить путь А.Н. Радищева "Из Петербурга в Москву", для чего решил воспользоваться личным автомобилем. Путешественник решил так спланировать свой маршрут, чтобы минимизировать затраты. Для этого ему нужно было знать, сколько на его пути встретится заправочных станций и на каком расстоянии друг от друга они находятся. Помимо всего прочего приходилось учитывать, что емкость бензобака машины ограничена. Требуется определить, какое минимальное количество заправок ему нужно посетить.

Считать, что первая АЗС находится в Петербурге, а последняя в Москве.

Di - расстояние от i-ой до (i+1)-ой заправки;

S  - расстояние, которое машина может проехать с полным баком;

L  - расстояние от Петербурга до Москвы.

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

Решение:

В данной задаче жадный алгоритм будет работать таким образом:

1.       Путешественник заправляет полный бак в исходной точке маршрута( Петербурге);

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

Реализацию данного алгоритма представим на языке Pascal:

Const

 MaxN = 1000;

 

Var

 d: Array [1..MaxN] of Integer;

 i,j,N,S,dd: Integer;

 

Begin

 Assign(Input,'input.txt');

 Assign(Output,'output.txt');

 Reset(Input);

 ReWrite(Output);

 ReadLn(N,S);

 for i:=1 to N-1 do

   Begin

     Read(d[i]);

     if d[i] > S then

       begin       

         WriteLn('No way');

         Close(Output);

         Halt(0);

       end;

   end;

 Write('1 ');

 i:=1;

 While i < N-1 do

   Begin

     j:=i;

     dd:=d[i];

     While (dd <= S) and (j < N-1) do

       Begin

         Inc(j);

         Inc(dd,d[j]);

       end;

     if dd > S then

       Write(j,' ');

     i:=j;

   end;

 Close(Input);

 Close(Output);

end.

 

Задача 4.

Перед праздниками шеф получает очень много приглашений на торжественные заседания. Чтобы лучше планировать свое время, шеф ввел правило, чтобы в каждом из приглашений четко указывался отрезок  времени заседаний . Шеф не любит половинчатых решений, поэтому или находится на заседании все указанное время, или не приходит на него. Между посещениями заседаний должен быть хотя бы минимальный перерыв, то есть шеф может успеть на j-е заседание по списку приглашений, если . Напишите программу, позволяющую шефу посетить как можно больше заседаний.

Решение:

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

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

 

Приведем код программы на языке Pascal:

 

 

const MAXN = 5000;

type Inv = record

           a, b, : londint; idx: word

          end;

  aInv = array [1..MAXN] of Inv;

  aAns = array [1..MAXN] of byte;

… {процедура эффективной сортировки массива записей}

varinvit: aInv;           {интервалы приглашений}

i, N : word;

res: aAns;                 {массив для ответа}

b_prev: longint;           {момент последнего выбранного заседания}

BEGIN

   read(N);

   fori:= 1 toNdobegin{заполняем массив интервалов приглашений}

   read(invit[i].idx := i;                     {егоначальныйномер}

   end;

…{вызов процедуры эффективной сортировки,

 упорядочивающей записи массива по возрастанию b}

fillchar(res,N,#0);          { массив ответа инициализируем нулями }

b_prev:= -1;                 {-1 меньше любого допустимого а; такая

                  инициализация позволяет не выделять выбор первого

                  приглашения}

for i:= 1 to N do begin

{первый интервал, не пересекающийся с предыдущим, принимается}

if invit[i].a > b_prev then begin

    res[invit[i].idx]:= 1;              { указываем его в ответе и }

    b_prev:= invit[i].b;                    { изменяем последнее b}

end;

end;

for i:= 1 to N do                                   { выводответа}

  wrute (res[i]);

END.

 

 

Задача 5.

Монетный двор выпускает монеты номиналом 25, 10, 5, 2, 1 копеек. Разработать программу, которая позволяла бы сумму в  N копеек разменять данными монетами, используя жадный алгоритм.

 

Решение: приведем пример такой программы, реализованный на языке java:

 

import javax.swing.JOptionPane;

import java.lang.*;

public class Exchange {

  public static void main(String[] args,double c) {

   double  a1= 25.0; double a2 = 10.0; double a3 = 5.0; double a4 = 2.0; double a5 = 1.0;

     String S = JOptionPane.showInputDialog("Vvedite symmy monet");

     double n = Double.parseDouble(S);

      double b1 = Math.max(a1, a2);

       double b2 = Math.max(a3, b1);

        double b3 = Math.max(a4, b2);

         double b4 = Math.max(a5, b3);

 

       for (int i=1; i<= n; i++){

        double mon1 = n/b4;

         double ost1 = n%b4;

         double  mon2 = ost1/b3;

         double ost2= ost1%b3;

         double mon3 = ost2/b2;

         double ost3 = ost2%b2;

         double mon4 = ost3/b1;

         double ost4 = ost3%b1;

         double mon5= ost4/a5;

         double k = mon1 + mon2+ mon3 + mon4 + mon5;

         JOptionPane.showMessageDialog(null,"Koli4estvo monet="+ k);

        }

}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Заключение

 

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

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

Основными достоинствами жадных алгоритмов является их простота и нетребовательность к ресурсам.

Жадные (градиентные) алгоритмы, действуют по принципу "максимальный выигрыш на каждом шаге". Такая стратегия не всегда ведет к конечному успеху - иногда выгоднее сделать не наилучший, казалось бы, выбор на очередном шаге с тем, чтобы в итоге получить оптимальное решение (пример неэффективности применения жадного алгоритма был разобран на примере частной задачи о размене монет). Но тем не менее, существует большое количество задач, для которых применение жадных алгоритмов оказывается оправданным.

 

 

 

 

 

Используемая литература:

 

 

 

1.     Д. Ш. Матрос,  Г. Б. Поднебесова, «Теория алгоритмов», М. 2002;

2.     М. Гудрич, Р. Тамассия, « Структуры данных и алгоритмы в java», М.2003;

3.     И. Н. Порублев, А. Б. Ставровский, «Алгоритмы и программы. Решение олимпиадных задач», М. 2007;

4.     И. В. Красиков, И. Е. Красикова, «Алгоритмы просто как 2*2», М. 2007;

5.     О. Л. Голицина, И. И. Попов,  «Основы алгоритмизации и программирования», М. 2008.

 
 

Опросы

Ваши любимые предметы