КОМБИНАТОРНЫЕ  МЕТОДЫ:  РЕКУРСИЯ  И  ДИНАМИЧЕСКОЕ  ПРОГРАММИРОВАНИЕ

Броницкая  Наталья  Анатольевна

канд.  физ.-мат.  наук,  ННУ  им.  В.А.  Сухомлинского,  г.  Николаев

E-mail:  natbron@mail.ru

Дармосюк  Валентина  Николаевна

канд.  физ.-мат.  наук,  ННУ  им.  В.А.  Сухомлинского,  г.  Николаев

Бережецкая  Виктория  Геннадиевна

студентка,  ННУ  им.  В.А.  Сухомлинского,  г.  Николаев

В  связи  с  актуализацией  и  активизацией  олимпиадного  движения  в  программировании  во  всем  мире  в  целом  и  на  Украине  в  частности,  все  острее  встает  проблема  подготовки  студентов  к  участию  в  олимпиадах.  Такая  деятельность  является  основной  базой  для  подготовки  уверенного  специалиста.  Знание  методов  и  способов  олимпиадного  программирования  дает  твердую  основу  для  создания  программного  обеспечения.  В  последние  годы  олимпиадное  движение  в  Украине  приобрело  значительные  масштабы.  В  результате  этого  уровень  знаний  и  умений  студентов  существенно  повысился.  В  связи  с  этим  в  2012  году  Украина  для  участия  во  всемирной  студенческой  АСМ  олимпиаде  была  выделена  в  отдельный  регион  (The  2013  All-Ukrainian  Collegiate  Programming  Contest). 

С  2011  года  в  Николаевском  национальном  университете  им.  В.О.  Сухомлинского  начал  функционировать  научный  кружок  олимпиадного  программирования,  на  котором  рассматриваются  классические,  базовые  и  эвристические  алгоритмы  решения  олимпиадных  задач. 

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

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

Комбинаторные  методы  во  многом  носят  эвристический  характер,  индивидуальные  как  для  различных  классов  задач,  так  и  для  отдельных  задач.  Причем  нередко,  чем  более  оригинальным  является  такой  метод,  тем  эффективнее  задача  решается  на  ЭВМ.

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

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

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

Рекурсивными  называются  функции,  которые  вызывают  сами  себя.  Рекурсия  позволяет  очень  просто  (без  использования  циклов)  программировать  вычисления  функций,  заданных  рекуррентно.  Например,  общеизвестна  функция  факториала  f(n)  =n!:  f(0)  =1;  f(n)  =n*f(n  –  1).

Данная  операция  наглядно  разбивает  задачу  на  несколько  меньших  подзадач,  решение  каждой  из  которых  приводит  к  решению  исходной  задачи.  Таким  образом,  запущенная  функция  как  бы  «разворачивается»  к  решению  тривиальной  задачи  (для  факториала  –  случай,  когда  n=1  или  n=0),  а  затем  «сворачивается»  в  исходной.  Но  мы  видим,  что  такие  действия  вполне  совпадают  с  определением  метода  динамического  программирования.  Разница  лишь  в  "развёртывании".

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

Например,  если  рассматривать  всем  известную  последовательность  чисел  Фибоначчи,  то  можно  заметить,  что  для  генерации  n-ого  числа,  метод  динамического  программирования  выполнит  ровно  n  действий  —  непосредственно  поиск  каждого  следующего  числа  ровно  1  раз.  В  то  же  время  использование  рекурсии  требует  многократного  пересчета  одних  и  тех  же  чисел,  также  не  пропуская  ни  одного. 

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

В  ходе  исследования  была  рассмотрена  классическая  задача-игра  «Ханойская  башня»,  которая  заключается  в  следующем:  есть  три  стержня,  на  первый  из  них  надета  пирамидка  из  N  колец  (большие  кольца  снизу,  меньшие  сверху),  нужно  переместить  кольца  на  другой  стержень.  Разрешается  переводить  кольца  со  стержня  на  стержень,  но  класть  большее  кольцо  поверх  меньшего  нельзя.  Составить  программу,  которая  генерирует  последовательность  необходимых  действий. 

Отметим,  что  существует,  по  меньшей  мере,  два  способа  решения  этой  задачи:  рекурсивный  и  нерекурсивный  (перебора).  Рекурсивный  метод  в  данном  случае  является  более  очевидным,  однако  в  ходе  решения  становится  понятно,  что  реализация  рекуррентной  формулы  более  оптимальна  при  использовании  метода  динамического  программирования. 

В  статье  [1]  была  решена  задача  достройки  латинского  квадрата  по  заданной  прямоугольной  матрице.  Отметим,  что  в  качестве  метода  решения  был  выбран  перебор  с  отходом  назад,  который  является  действенным,  однако  не  оптимальным.  Впоследствии  эта  задача  была  решена  нами  методом  рекуррентных  формул,  что  позволило  значительно  сократить  время  работы  программы.

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

Коммивояжёр  ездит  по  городам  с  целью  сбыта  товаров  разного  рода.  Он  всегда  начинает  и  заканчивает  свой  путь  в  одном  и  том  же  городе.  На  проживание  во  всех  городах  коммерсант  тратит  одинаковую  сумму  денег.  Поэтому  существенна  только  сумма  на  проезд  из  города  в  город.  Есть  список  городов  и  стоимость  проезда  между  некоторыми  парами  из  них.

Для  справки,  коммивояжёр  —  разъездной  представитель  торговой  фирмы,  предлагающий  покупателям  товары  по  имеющимся  у  него  образцам,  каталогам  и  тому  подобное.

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

Формулировка  задачи

·     внутри  города  проезд  ничего  не  стоит;

·     проезд  между  двумя  городами  напрямую  стоит  одинаково  в  оба  конца;

·     стоимость  —  целое  число  от  1  до  10000;

·     городов  не  более  100.

Стоимости  проезда  между  парами  городов  записаны  в  следующем  формате:

<Количество  стоимостей>  <Начальный  город>

<Город>  <Город>  <Стоимость>

<Город>  <Город>  <Стоимость>

<Город>  <Город>  <Стоимость>

…

Результат  записывается  в  следующем  формате:

<Количество  городов  в  пути>

<Город>  <Город>  <Город>  …

Город  задаётся  названием  без  пробела.  Длина  названия  города  не  более  30  символов. 

На  первый  взгляд,  для  решения  такой  задачи  достаточно  хранить  самые  оптимальные  промежуточные  пути  и  тогда  сразу  получаем  динамический  алгоритм.  Например,  рассмотрим  тройки  городов  и  для  каждой  тройки  определим,  в  какой  последовательности  лучше  всего  её  проходить.  Затем  рассмотрим  все  четвёрки  городов.  Решения  для  четвёрок  можно  найти  на  основе  известных  решений  для  троек  и  так  далее.  Но  дело  в  том,  что  число  возможных  наборов    городов  и    возможных  очень  быстро  растёт.  Например,  50  городов  из  100  можно  выбрать  100  891  344  545  564  193  334  812  497  256  способами.  Таким  образом,  запоминать  промежуточные  решения  нет  никакой  возможности  —  их  слишком  много  даже  для  n=100,  а  на  практике  нужно  решать  задачи  с  n=10⁶.  Для  задачи  коммивояжёра  на  плоскости  можно  использовать  ряд  эвристических  идей,  которые  позволяют  находить  приемлемые  решения  за  разумное  время.  Но  при  этом  даже  для  случая  точек  на  плоскости  задача  коммивояжёра  остаётся  полиномиально  неразрешимой,  то  есть  не  существует  алгоритма,  который  бы  находил  самый  оптимальный  путь  коммивояжёра  за  время  ограниченное  полиномом  C+n^k  произвольной  степени  k  при  любой  константе .

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

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

На  популярном  в  Украине  сайте  с  on-line  проверкой  для  подготовки  к  олимпиадному  программированию  e-olimp.com  представлена  достаточно  большая  подборка  задач,  решаемых  описанными  в  статье  методами.

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

1. Беллман  Р.  Динамическое  программирование.  /  М.:  Изд-во  иностранной  литературы,  1960,  400  с. 
2. Броницька  Н.А.,  Дармосюк  В.М.,  Хомічук  Р.,  Бережецька  В.  Програмування  комбінаторних  задач  на  прикладі  латинських  квадратів  //  «Наукові  записки.  Серія:  Педагогічні  науки».  2012.  Випуск  109.
3. Задача  коммивояжёра//  Википедия  –  свободная  энциклопедия.  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  ru.wikipedia.org/wiki/Задача_коммивояжёра  (дата  обращения:  20.05.2013).
4. Методы  программирования  //  Алгоритмы  и  методы  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://algolist.manual.ru/maths/combinat/sequential.php  (дата  обращения:  23.04.2013).
5. Сайт  олимпиадного  программирования  с  on-line  проверкой  //  Список  задач  [Электронный  ресурс]  —  Режим  доступа.  —  URL:  http://www.e-olimp.com.ua/problems  (дата  обращения:  26.05.2013).