Разбиение задачи на подзадачи как называется

6

Разбиение на подзадачи: почему работает, и почему нет

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

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

Возможность предсказывать лежит в основе создания коротких целей. Однако не всё так просто.
Если мы создаем предсказание с максимальной вероятностью (100%), то оно не создает позитивной мотивации. Например, нас не мотивирует то, что мы сидим на стуле, потому что мы с 100% вероятностью подсознательно предсказываем, что он не сломается под нами. Мы получаем только нейтральную реакцию, и даже не обращаем на нее внимание.

Мотивация же относится к тем случаям, когда предсказание не гарантирует достижение цели, но мы своими усилиями, на основе предсказания, всё же достигаем позитивного результата. Притом сила мотивации пропорциональна соотношению двух факторов: «бонус» и вероятность.

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

Каждый раз, когда мы подтверждаем своё предсказание, которое не было 100% вероятностным, мы получаем долю «позитива». Подсознание как бы дрессирует нас при помощи нейропептидов, чтобы мы вырабатывали новые эффективные предсказания, развивались.

Точно также действуют и короткие задачи.

Когда вы ставите короткую задачу, она не должна быть 100% предсказанной, то есть вы не должны детально четко знать каждый шаг по ее достижению. Это снижает «бонус», которым нас мотивирует подсознание. Если вы будете это знать, то такое задание не вызывает позитива, но является растратой ресурсов, так создается «рутина».

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

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

Собственно почему тогда задачи нужны именно короткие?

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

Если вы предсказываете, что сделаете модуль за 30 минут, подсознание дает мотивацию на достижение, так как считает, что вы будете непрерывно заниматься этим модулем и имеете вероятность его закончить именно через 30 минут.
Если же каждые 5 минут вас начинают «дергать», то подсознание может в результате понизить мотивацию, как эти «дерганья» начинают включаться в модель предсказания, и тем самым ваш модуль «стОит» для подсознания уже гораздо дороже, а такую цену оно возможно не готово платить.

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

Именно поэтому в таких случаях важно или не отвлекаться от выполнения модели предсказания, или уметь очень сильно и четко переключать своё сознание, чтобы также и переключалось предсказание. Это довольно сложно сделать, если вас переключают на другие дела, требующие умственных усилий, но гораздо легче, если эти переключения идут в область 100% предсказаний, например отлучиться в туалет.

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

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

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

HS2.0
Успехов вам в достижении собственных целей.

UPD1
Для тех, кому сразу сложно понять о чем идет речь, немного уточню.
Модели предсказания это не образное понятие, рожденное от наблюдения за человеком. Это принцип функционирования нейросетей неокортекса головного мозга. Именно у человека он развился до такой степени, что он создал механизмы позволяющие ему регулировать собственные мотивации при помощи нейропептидов (эндорфина).
Подробнее о моделях предсказания (как они формируются нейронами и как устроены) можете прочитать в книге «Об интеллекте» Джеффа Хокинса.
Данный материал относится не к классической наблюденческой психологии, а к нейробиологии и химии мозга. И естественно, что он значительно упрощен и сокращен, чтобы уложиться в формат хабра.

Декомпозиция целей и задач

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

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

Зачем нужна декомпозиция?

Декомпозиция очень часто используется в планировании, и это не случайно. Она помогает:

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

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

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

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

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

Другое дело, что в декомпозиция применяется осознанно, а значит и более эффективно.

Основные принципы

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

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

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

В принципе для построения деревьев можно использовать любую программу для создания схем — Microsoft Visio или, например, бесплатный сервис draw.io. Древовидные структуры умеют создавать и некоторые современные органайзеры, например, LeaderTask.

Но удобнее всего рисовать такие деревья в виде ментальных карт. Для этого вам потребуются специальные программы для их создания: , MindNode, MindManager, бесплатная Freemind

Итак, приступим. В общем виде декомпозиция выглядит так:

• Выбираем задачу или цель.
• Спрашиваем себя: какие шаги потребуется предпринять для ее осуществления? Записываем результат. У нас получаются цели (или задачи) порядка.
• Задаем к ним все тот же вопрос и снова записываем результат. Получаем цели порядка.
• Повторяем эту процедуру необходимое количество раз.

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

В процессе декомпозиции важно соблюдать следующие правила:

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

2. Стараться не делить задачи более чем на 7 подзадач. По правилу Джорджа Миллера мы способны за один раз удержать в памяти 7±2 объекта, и если подзадач окажется больше, нам будет труднее воспринимать свои планы. В таких случаях можно разделить задачи на группы по признаку:

Впрочем, последнее правило не является аксиомой: делайте так, как вам удобнее.

Способы декомпозиции

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

1. Деление на этапы

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

Но это очень простой случай: здесь вся работа состоит из одинаковых шагов. Давайте возьмем более сложную цель — «построить дом».

Для начала разделим процесс строительства на главные этапы. Например, на такие:

Теперь каждый из них нужно разделить на этапы поменьше. Для примера сделаем декомпозицию «Фундамента»:

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

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

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

Для планирования некоторых целей и задач удобнее использовать диаграмму Гантта.

Советы:

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

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

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

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

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

2. Декомпозиция измеримых показателей

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

Давайте рассмотрим один нарочито простой пример.

Предположим, что каждое утро мы выполняем такое упражнение, как отжимания от пола. В настоящий момент мы делаем 4 подхода по 3 отжимания. Наша же цель — выполнять 4 подхода по 20 отжиманий, и на достижение этого показателя у нас есть 2 месяца.

Что ж, цель вполне осуществимая. Допустим, мы хотим ее достичь за 20 тренировок. Откроем Excel и запишем число занятий, начальный и конечный результат:

А теперь просто воспользуемся функцией автозаполнения:

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

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

Советы:

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

Учитывайте и непредвиденные трудности. Иногда удобно иметь сразу два графика: план максимум и план минимум.

3. Дерево зависимостей

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

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

Каждый из этих показателей можно опять же разложить на составляющие. Например:

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

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

Советы:

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

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

4. Одношаговая декомпозиция

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

Чтобы двигаться к цели в условиях нестабильности или неопределенности используйте одношаговую декомпозицию. Алгоритм работает так:

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

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

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

Советы:

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

• Работа над сайтом — 3 часа в день
• Генеральная уборка — 1 час в день
• Навести порядок в скачанных файлах — 15 минут в день

Оформить это время можно в виде регулярной задачи.

Заключение

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

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

Вопросы

В каких случаях декомпозиция не нужна?

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

Всегда ли декомпозиция полезна?

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

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

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

Что делать, если я тщательно разделил цель на подзадачи, а план полностью сорвался? Например, из-за того, что я не предусмотрел какие-то важные нюансы?

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

Что делать, если я распределил этапы по дням, но не уложился в сроки?

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

А что делать, если планы постоянно срываются?

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

Как разделить на подзадачи большую монотонную работу? Например, написание длинного текста, покраску забора, заполнение базы данных?

Такую работу удобнее делить не на подзадачи, а на различные временные отрезки. Воспользуйтесь, например, техникой Pomodoro.

Методы разбиения задач на подзадачи. Рекурсия, «Разделяй и властвуй» динамическое программирование Текст научной статьи по специальности «Математика»

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

Похожие темы научных работ по математике , автор научной работы — Наумов Лев Александрович

Текст научной работы на тему «Методы разбиения задач на подзадачи. Рекурсия, «Разделяй и властвуй» динамическое программирование»

Наумов Лев Александрович

МЕТОДЫ РАЗБИЕНИЯ ЗАДАЧ НА ПОДЗАДАЧИ. РЕКУРСИЯ, «РАЗДЕЛЯЙ И ВЛАСТВУЙ» ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Какие задачи решать труднее всего? Глупый вопрос, конечно же — сложные. За этим вопросом напрашивается другой, не менее глупый: решать то их, конечно, сложно, но, все-таки, как? На него ответить вообще нельзя. Все зависит от конкретной задачи. Однако мы попытаемся здесь описать один наиболее общий метод: их можно разбивать на «меньшие» подзадачи, которые уже решаются легче. В начале необходимо оговорить, что под словом «сложные» в данном случае мы будем понимать не сложные для программиста, а сложные для компьютера, трудоемкие задачи.

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

Прежде, чем перейти к основной части повествования, введем обозначение. Если в тексте Вы встретите такую запись: < к > (где к — на-

. ч^йма или /еосЗеННа обрщае&ся слмл « себе.

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

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

Этот механизм основан на использовании так называемой рекурсивной функции. Она обладает тем свойством, что прямо или косвенно обращается сама к себе. Рекурсией полезно пользоваться, если задачу можно разбить на подзадачи, решаемые за «разумное время», и если при этом суммарный размер подзадач — «небольшой». В предыдущем предложении так много кавычек из-за того, что общего определения «разумного времени» и «небольшого размера» дать нельзя. Значения, вкладываемые в эти понятия, зависят от задачи, целей, которые преследуются, приоритетов при построении решения и многого другого.

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

.рл^мигяш мо&а^м разбиений уадлги На

метров. Главное — не забыть проконтролировать, чтобы процесс когда-нибудь закончился. Для этого нужно, чтобы при некоторых значениях параметров функция больше не вызывала себя. Эти значения называются терминальными.

Продемонстрируем работу рекурсивного метода. В качестве примера рассмотрим вычисление суммы всех целых степеней x от 0 до некоторого n, сосчитаем значение функции f(х,n) = xn + xn-1 +. + x +1. Эта функция обладает определенный свойством, позволяющим нам применить рекурсию. Оно выражается в следующем равенстве: f (х,n) = х• (xn-1 + xn-2. + х +1) +1. Вы убедитесь в этом, если просто вынесете x за скобку из всех слагаемых, кроме последнего. Фактически, оно означает, что f (x, n) = x • f (x, n -1) +1, а это и есть рекуррентное соотношение, позволяющее перейти от решения задачи для n -1 к решению для n.

Остается один вопрос: а какое значение n считать терминальным? Ну, подумайте сами, результат возведения в какую степень нам всегда известен заранее, независимо от числа x? Конечно — в нулевую. Так пусть терминальным значением и будет n = 0.

Соответствующая рекурсивная процедура будет иметь вид:

function f(x:real; n:integer):real; begin

if n=0 then begin f:=1; exit;

На самом деле Вас «обманули», и мы надеемся, что Вы это уже заметили сами. Мотивация выбора нуля, как терминального значения параметра, совсем иная. Действительно, мы всегда знаем, что f (x,0) = 1. Но, посудите сами, разве нам не известно, что f (x,1) = x +1 ?, что f (x,2) = x2+x +1 ? Конечно, известно! Просто если бы мы выбрали, например, двойку как терминальное значение, то подсчитать f (x, 0) и f (x, 1) мы бы уже не смогли. В этой задаче стоило выбирать наименьшее n, для которого мо-

. fteKCffefeefa&ftoe cooHftoaeftue, ftefeeu&u лН решения ^л^лис n —1 e feeweftoa n.

жет потребоваться вычисление значения функции.

Помимо того, что терминальные значения должны быть предусмотрены, они должны еще и достигаться при рекурсивном вычислении. В приведенном выше примере это, очевидно, выполняется. Ведь начав с любого n, мы, постоянно вычитая из него единицу, рано или поздно, доберемся до нуля. Тем самым, «глубина рекурсии» у нас ограничена и равна n + 1. Вызов f (n) приведет к вычислению значения требуемой функции посредством вызова f самой из себя, n раз. То есть для всех значений второго параметра от n — 1 до 0. При этом глубина рекурсии равна n + 1, так как надо посчитать еще и сам первый вызов f (n). 3 1, 2 4

А вообще говоря, почему глубина рекурсии должна быть ограничена? Дело в том, что при программировании нужно исходить из того, что чрезмерная глубина может вызвать ошибку. Если функция будет бесконечно вызывать и вызывать себя же, то на определенном этапе это приведет к переполнению стека. При этом, выполнение программы, несомненно, не сможет продолжаться. О подробностях природы этого эффекта мы здесь говорить не будем. Однако, наверное, будет полезно упомянуть, что, например, в среде программирования Borland

. аагему гл^бсЯл fezKipfecuu далфЯя быНь o-tfeaftaiefta?

Pascal 7.0 есть средства, позволяющие следить и предотвратить возникновение этой ошибки. Открыв при отладке программы окно Call stack (это можно сделать через главное меню Debug I Call stack или сочетанием клавиш <Ctrl> + <F3>) Вы сможете наблюдать за последовательностью вызовов функций и изменением их параметров. Если при определенных обстоятельствах возникает ошибка «Stack overflow error», значит, Вам есть еще над чем поработать в реализуемом рекурсивном алгоритме. Или, как минимум, нужно наложить некоторые ограничения на область значений параметров. 3 3 ►

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

Рассмотрим сказанное выше поподробнее. Например, пусть какая-то задача оперирует с набором из n элементов. Было бы здорово разбить его на q наборов из меньшего числа элементов. Причем так, чтобы ни один из элементов не принадлежал более чем одному набору.

Итак, предположим, что набор разделяется на q непустых поднаборов, содержа-

6ft ^мсмоше&ся 6 рл^биеНии

,n элементов, соответствен-

но. Так как п, + п + . + п = п, то п. < п

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

Упомянутый выше частный случай достигается, когда каждую из сформулированных задач для (г = 1, 2, . д) можно также решить разбиением соответствующих поднаборов на более мелкие. Проделывая такую операцию рекурсивно до определенного предела (терминального значения длины поднабора), Вы можете получить решения подзадач для наборов из нескольких элементов. Затем уже легко построить решение всей задачи как некое объединение этих решений.

Рассмотрим пример применения данного механизма. Обсудим, так называемую сортировку слиянием. Пусть, например, нам дан набор из восьми чисел Т = <7, 6, 3, 7, 9, 2, 1, 4>. Наша задача заключается в том, чтобы отсортировать их, скажем, по возрастанию. Согласно методу «разделяй и властвуй», разделим его пополам, получим два поднабора Т1 = <7, 6, 3, 7>и Т2 = <9, 2, 1, 4>и будем над ними властвовать! А точнее, будем сортировать уже их, каждый отдельно. Как мы будем это делать? Конечно же, опять поделив и тот и другой наборы пополам (таким образом, мы получим Т11 = <7, 6>, Т12 = <3, 7>, Т21 = <9, 2>и Т22 = <1, 4>). Деление продолжим рекурсивно до того момента, пока не получим наборы из одного единственного элемента (Тш = <7>, Т112 = <6>, Т121 = <3>,

и Т222 = <4>). Естественно, такие наборы можно сразу считать отсортированными. Тогда объединим два упорядоченных набора. Причем так, чтобы их объединение опять было упорядоченным 3 4 ► . Проделаем это рекурсивно до тех пор, пока снова не получим набор, равный по длине исходному. На-

деемся, рисунок 1 поможет Вам понять, как именно должно осуществляться объединение наборов.

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

Выше мы рассказывали о том, что при решении задач рекурсивным методом существует опасность вызвать переполнение стека. Поэтому нужно стараться минимизировать глубину рекурсии. Читатель, наверное, согласится с тем, что разбивать исходный набор вплоть до поднаборов длины 1 вряд ли имеет смысл. Ведь набор из двух элементов уже можно упорядочить, проверив одно условие. Конечно, можно проверкой некоторого количества разных условий отсортировать и набор из четырех элементов. Однако это, пожалуй, уже лишнее. Так можно «вручную» сортировать наборы из любого наперед заданного числа элементов. 3 6 ► Механизм сортировки наборов с длиной, меньшей терминального значения, тоже можно предусмотреть.

А вот другой пример применения принципа «разделяй и властвуй». Рассмотрим часто встречаемую в программировании задачу о выпуклой оболочке на плоскости. Для конечного множества точек Q выпук-

. рл^би&Аеиь «сх&рМж Ллбор . .

лой оболочкой называется наименьший по площади выпуклый многоугольник, содержащий все точки из Q. Фактически, задача заключается в отыскании некоего подмножества Q (обозначим его S), все точки которого являются вершинами упомянутого многоугольника. Поясним сказанное выше примером. Пусть Q = <1, 2, 3, 4, 5, 6, 7, 8, 9, 10>(здесь числа — номера, индексы, идентификаторы точек, не более того). Точки располагаются так, как указано на рисунке 2. Их координаты задают их расположение. Вряд ли стоит приводить здесь некие конкретные числа, так как наша задача заключается в том, чтобы объяснить принцип, алгоритм решения.

Итак, выпуклой оболочкой является многоугольник, вершинами которого являются точки множества S. В данном случае 5 = <1, 4, 5, 6, 7, 9>. Соответствующий многоугольник показан на рисунке 3. Все оставшиеся точки (то есть те, которые принадлежат Q, но не принадлежат 5) располагаются внутри этого многоугольника.

Для построения выпуклой оболочки существует множество методов: просмотр

Грэхема, проход Джарвиса, метод добавления точек, «метод стрижки и поиска». Если Вас это заинтересовало, то о них Вы можно узнать из книги [1]. Мы же остановимся лишь на решении задачи приемом «разделяй и властвуй». Все происходит абсолютно так же, как при сортировке слиянием. Сначала необходимо разделить имеющееся множество точек на два подмножества, приблизительно равных по мощности (числу элементов). Причем сделать это нужно так, чтобы ни один из многоугольников, построенных на неких точках одной половинки как на вершинах, не пересекался ни с каким многоугольником, построенным на точках другой половинки. Достичь этого можно, разделив плоскость вертикальной прямой на две зоны.

Затем следует получить решение для обеих половинок. Результат представлен на рисунке 4.

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

не окажется лишь 3 точки, для которых выпуклая оболочка получается простым их соединением. Конечно, если в зоне было, например, всего 5 точек, то отделив 3, Вы получите зону в которой — 2 точки. Что же делать? Прочитайте описание излагаемого метода до конца и подумайте, является ли это проблемой.

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

Здесь результирующий прямоугольник обведен сплошными отрезками. Трудность

. улдлгу для клфдай уаЯи НуфНа реалЛ-ь ен<ш фе, рлуделЯЯ ее На д4е подуаНи.

. рлудемий-ь имеющееся . Ял дбл

при объединении заключается в выборе соединяемых точек. Почему мы предпочли отрезок 9-4 отрезкам 9-3, 9-10 и остальным? Дело в том, что нужно производить соединения так, чтобы все точки объединяемых многоугольников лежали по одну сторону от проводимой прямой, и чтобы получающийся многоугольник был минимален. Над этим правилом Вам предстоит подумать в задаче 7.

Ранее говорилось, что задача о выпуклой оболочке «часто встречается в программировании». Не надо из этого делать вывод, что программисты нередко решают задачи планиметрии. Просто многие проблемы из самых разных областей сводятся к построению выпуклой оболочки для некоторого множества, природа которого далека от геометрической, и понятие координат его элементов заменено на что-то специфические для данной задачи. 3 7, 8, 9, 10 ►

Нельзя не отметить, что применительно к задаче 8 этот метод дает существенный выигрыш в эффективности. А именно, он требует 1,5п -2 сравнений, в то время как обычный способ вычисления в цикле требует 2п — 3 (п — 1 на поиск минимума и п — 2 на поиск максимума; минимум в рассмотрении уже не участвует).

Метод «разделяй и властвуй» зачастую повышает эффективность на порядки. Чтобы познакомится с примерами, можно обратиться к книге [2]. Мы же переходим к основной теме — динамическому программированию.

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

.¿лулгу мо^Но рл^бш&ь Ял по/^лфлш, решаемые «рл^ужНое бремя».

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

Как и техника «разделяй и властвуй», динамическое программирование позволяет построить решение общей задачи, разбивая ее на подзадачи и объединяя их решения. Однако, как было продемонстрировано выше, при использовании метода «разделяй и властвуй» нужно производить разбиение на системы независимых подзадач. А при динамическом программировании необходимо разделение на взаимосвязанные подзадачи. Дробить следует так, чтобы у подзадач были общие части, общие «подподзадачи», если угодно. Если бы в такой ситуации мы использовали метод «разделяй и властвуй», то эти самые «подподзадачи» решались бы по нескольку раз. Динамический метод, решив ее однажды, запоминает результат в специальном хранилище, как правило, -таблице. Когда этот результат понадобится, будет достаточно лишь обратиться к соответствующей ее ячейке.

Давайте вместе рассмотрим следующую задачу. Пусть нам дана таблица ¥, состоящая из п строк и т столбцов. В каждой ячейке таблицы может содержаться либо «0», либо «1». От нас требуется найти сторону наибольшего квадрата из единиц, который есть в этой таблице.

Поясним сказанное примером ¥ для п и т равных 6.

. ЛребуеЛся Лай&и ойораЛу Камбал-шего коядра,* едиЛщ.

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

Как же ее решать? Очевидно, полный перебор всевозможных вариантов — дело не очень перспективное, особенно при больших п и т.

Предлагается следующее решение: заведем таблицу D, равную по размеру К В каждую ее клетку [г, у] поместим величину стороны квадрата из единиц, имеющего нижний правый угол в клетке ^[г, у]. Ясно, что там, где в ^ были нули, там и в D будут нули.

Для приведенной выше исходной таблицы вспомогательная таблица D должна выглядеть так:

просто переносятся из ^ в Д — очевиден. Ведь на них мы можем обнаружить либо квадрат со стороной равной единице (то есть просто -«1»), либо ноль, который вообще не может являться «нижним правым углом квадрата из единиц».

Как же заполнять D дальше, при 2 < г < п и 2 < у < т? Нули, как уже неоднократно говорилось, просто переписываются. А что делать, если ^ [г, у]=1? Ясно, что D [г, у] отлична от единицы, только если ее левый ^ [г,у — 1]), верхний ^ [г — 1, у]) и левый верхний (Т) [/ — 1, у — 1]) со-^ седи содержат не ноль. Причем содержимое клетки ^ [г, у] может продлить лишь наименьший из квадратов, упирающихся в его соседей. Формально, это означает, что D [г, у] = тгп^ [г — 1, у], D [г, у — 1], D [г — 1, у — 1]) + 1. Это и понятно, так как к квадрату, которому соответствует D [г — 1, у], могла добавиться, как максимум, только одна строка. К квадрату, учтенному в D [г, у — 1], — только один столбец. А к D [г — 1, у — 1] — одна строка и один столбец. Таким образом, размер результирующего квадрата не может превышать D [г — 1,у] + 1, D [г,у — 1] + 1 и D [г — 1,у -1] + 1. Это, пожалуй, вполне исчерпывающе объясняет написанную формулу.

Теперь сведем имеющиеся результаты относительно D воедино. Получим:

^[г, у], при г = 1 или у = 1 0, если ^[г, у] = 0

т1п(Дг — 1, у], Дг, у — 1], Дг — 1, у — 1]) + 1 ,

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

при 2 < г < п и 2 < у < т.

Как реализовать вычисление D на компьютере? Сначала — заполнить первую строку и столбец. А затем — вычислять в двойном цикле по г и у от меньших индексов — к большим. При таком подходе Вы защищены от того, что может потребоваться значение из ячейки, которое еще не вычислялось. 3 11 ►

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

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

. обращение а определенным ячейкам Ллёмщи.

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

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

Сказанное выше не означает, что этот метод не стоит использовать. Наоборот, предыдущий абзац, скорее, — лишний аргумент в пользу его применения. К тому же, он полезен, когда не все подзадачи решаются несколько раз. 3 12 ►

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

Для нахождения наибольшей общей подпоследовательности последовательностей X и У нужно:

1) Если последний элемент последовательности X совпадает с последним элементом последовательности У, то решать задачу для этих последовательностей без последних элементов, а

потом приписать этот элемент к результату.

2) Если последний элемент последовательности X не совпадает с последним элементом последовательности У, решать две задачи. Первая — для последовательности X без последнего элемента

и последовательности У. Вторая — для последовательности У без последнего элемента и последовательности X. Наибольший из результатов и будет наибольшей общей подпоследовательностью.

Таким образом, получилось очевидное перекрытие подзадач: ведь наибольшую общую подпоследовательность для X и У без последних элементов придется искать, как в случае 1, так, вероятно, и в случае 2. Очевидно, что в этой ситуации имеет смысл сохранять результаты вычислений в таблице. Обозначим за с [г, у] длину наибольшей общей подпоследовательности для последовательности X, состоящей из г элементов, и последовательности У — из у элементов. Тогда приходим к соотношению:

с[г — 1, у — 1] + 1, если г, у > 0

и последние элементы совпадают, тах(с[г, у — 1], с[г — 1, у]), если г, у > 0 и последние элементы не совпадают.

Как Вы, должно быть, уже догадались, с [г, у'] и составляет содержание одноименной таблицы, необходимой для корректной работы метода динамического программирования. Здесь г = 0, 1, . , т, а у = 0, 1, . , п.

Кроме того, потребуется вторая таблица Ь, в которой Ь [г, у] хранит «происхождение» с [г, у]. Ведь возможны 3 варианта появления конкретного значения с [г, у]: от с[г — 1, у — 1], от с[г, у — 1] или от с[г — 1, у]. Очень красивым и экономичным решением для организации Ь было бы такое, при котором на каждую ячейку отводилось бы 2 бита. Таким образом, одна ячейка могла бы хранить значения от 0 до 3. Этого было бы вполне достаточно (даже одно — лишнее), а интерпретировать их можно было бы так:

0 — значение для инициализации ячеек Ь. На самом деле, конечно, оно не нужно, но что ему без дела пропадать ©.

1 — с [г,у] «произошло» от с [г — 1,у — 1].

2 — с [г, у] «произошло» от с [г, у — 1].

3 — с [г, у] «произошло» от с [г — 1, у].

Теперь, пусть алгоритм выполнен и

таблицы Ь и с заполнены. Как получить Z? Нужно из клетки Ь [т, п] проделать путь до

^уфЯо Ь [т, п] проф&хо&ь до

ЯекоЛорой кле&ки. Ь [ 0, р].

некоторой клетки Ь [0, р] или Ь [г, 0] (для какого-нибудь р или г), выписывая одинаковые члены последовательностей X и У. Звучит угрожающе, не правда ли? Посмотрите на рисунок 6, и, надеемся, Вам станет понятнее.

На рисунке представлено некое совмещение информации таблиц Ь и с для X = <А, В, С, В, D, А, В>и У = <В, D, С, А, В, А>. Число в каждой клетке соответствует значению с [г, у] для нее. Стрелочка — некое наглядное представление информации ячейки Ь [г, у]. Она указывает на ту ячейку, от которой «произошло» с [г, у]. Такое представление очень удобно для построения пути из Ь [т, п]. Оно просто заключается в прохождении по этим стрелкам до тех пор, пока не будет достигнута граница матрицы. Клет-

Что такое динамическое программирование

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

Представим хакера, который пытается взломать какой-то пароль перебором всех комбинаций символов. Если пароль допускает 10 цифр, 26 маленьких букв, 26 больших букв и 32 специальных символа (например, значок доллара), то для каждого символа в пароле есть 94 кандидата. Значит, чтобы взломать перебором пароль, состоящий из одного символа, потребуется 94 проверки. Если в пароле два символа — 94 кандидата на первую позицию, 94 кандидата на вторую позицию — то придется перебрать аж 94*94 = 8836 возможных пар. Для пароля из десяти символов потребуется уже перебор 94^10 комбинаций.

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

Экспоненциальное время — это долго. Даже O(2^N) — это просто непозволительно долго. Настолько долго, что никому и в голову не придет запустить подобный алгоритм даже на простых данных — ведь на решение такой задачи с сотней элементов потребуются тысячи, миллионы или миллиарды лет вычислений. А в реальной жизни нужно решать задачи с намного большим количеством элементов. Как же быть?

Дело в том, что многие задачи без эффективного алгоритма решения можно решить за привлекательное время с помощью одной хитрости — динамического программирования.

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

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

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

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

В самых простых случаях эта таблица будет состоять только из одной строки — аналогично обычному массиву. Эти случаи будут называться одномерным динамическим программированием, и потреблять O(n) памяти. Например, алгоритм эффективного вычисления чисел Фибоначчи использует обычный массив для запоминания вычисленных промежуточных результатов. Классический рекурсивный алгоритм делает очень много бессмысленный работы — он по миллионному разу рассчитывает то, что уже было рассчитано в соседних ветках рекурсии.

В самых распространённых случаях эта таблица будет выглядеть привычно и состоять из строчек и столбиков. Обычная таблица, похожая на таблицы из Excel. Это называется двумерным динамическим программированием, которое при n строках и n столбцах таблицы потребляет O(n*n) = O(n^2) памяти. Например, квадратная таблица из 10 строк и 10 столбцов будет содержать 100 ячеек. Чуть ниже будет подробно разобрана именно такая задача.

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

Что нужно, чтобы решить задачу динамически, помимо ее исходных данных? Всего три вещи:

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

Разберем эти принципы на примере.

Пример решения задачи

Демонстрационным подопытным выступит классическая задача динамического программирования — Расстояние Левенштейна. Несмотря на кажущееся сложным название, в действительности это задача о трансформации одного слова в другое путем добавления, удаления и замены букв с минимальным количеством операций.

Эта задача может быть сформулирована так: найти минимальное «расстояние» между двумя словами. Расстоянием в этом случае будет минимальное количество операций, которые нужно применить к первому слову, чтобы получить второе (или наоборот).

Доступных операции у нас три:

• insert — добавить одну букву в любое место в слове, в том числе в самое начало и в конец
• delete — удалить одну букву из любого места в слове
• replace — заменить одну букву в определенном месте на другую букву

Все эти операции имеют равную стоимость: +1 к расстоянию между словами.

Возьмем для примера два простых слова, MONEY и MONKEY. Какое минимальное количество операций необходимо, чтобы превратить MONEY в MONKEY? Находчивый человеческий глаз быстро смекнет, что одна: добавить букву K после между третьей и четвертой буквой.

Возьмем случай посложнее. Попробуем превратить слово SUNDAY в слово SATURDAY, и увидим, что количество комбинаций, которые нужно перебрать, потенциально очень велико. Если решать задачу перебором, то можно рассмотреть все возможные комбинации, как в примере со взломом пароля. Вместо возможных 94 символов-кандидатов у нас есть три операции — insert, delete, replace. Три комбинации для первой буквы, 3*3 для двух букв, 3*3*3 для трех букв, 3^N для N букв. Комбинаторный взрыв.

Динамическое решение

Приступим к динамическому решению. Для начала, создадим таблицу и разместим исходные слова на ее краях, оставив немного свободного места. Второй столбик и вторую строчку буем использовать для пустых строк — их часто обозначают символом ε, читается epsilon. Аналог того, что вы имеете в виду, когда используете пустую строку на своем языке программирования: String eps = “”.

Теперь заполним второй столбик и вторую строчку, руководствуясь абсолютно интуитивными соображениями: как превратить пустую строку в какую-то строку? Конечно же, добавить в нее нужные символы! Например, чтобы перевести ε в SATU, необходимо добавить букву S, букву A, букву T и букву U. Четыре операции. Что делать с превращением ε в ε (вторая строка, второй столбец)? Элементарно — ничего делать не нужно, ноль действий.

Теперь нужна система простых правил, с помощью которой мы сможем заполнить таблицу. Таблица будет именоваться D, а первая строчка и столбик останутся на ее полях. Работать с таблицей мы будем, как с двухмерным массивом: D[0, 2] означают ячейку на пересечении нулевой строки и второго столбика. В нашем примере D[0, 2] = 2.

Также назовём слово по вертикали A, а слово по горизонтали B. Эта парочка нам нужна, чтобы иметь доступ к оригинальным словам на полях. Из-за дополнительных колонок в для ε индексы в A и B отличаются от индексов в таблице. Если быть точнее — они сдвинуты на единицу. A[0] = S, A[1] = U, A[2] = N, B[7] = Y, и так далее.

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

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

Что следует записать в ячейку D[1,1] как результат перехода из S в S? Интуитивно ясно, что для этого ничего делать и не нужно, ноль операций. Запишем в ячейку ноль. На что похоже это значение, учитывая, что вычитать ничего нельзя? Среди соседей ноль есть только по диагонали.

Что записать в ячейку D[2,1] как результат перехода из SU в S? Нужно удалить букву U — значит, это одна операция. По-сути, стоимость перехода из SU в S будет равно стоимости удаления буквы U и перехода из S в S (чья стоимость уже была посчитана и лежит в ячейке D[1,1]).

Теперь посмотрим на ячейку D[1,2], переход из S в SA. Да, именно, стоимость перехода будет равна стоимости добавления буквы A и перехода из S в S, итого единица.

Последняя ячейка, D[2,2], переход из SU в SA. Самым оптимальным решением было бы заменить букву U на букву A, плюс цена бесплатного перехода из S в S.

В самой правой нижней ячейке содержится финальная стоимость перехода из слова SU в слово SA. Аналогичным образом можно заполнить всю таблицу. Из ячейки D[6,8] мы узнали, что переход из слова SUNDAY в слово SATURDAY стоит минимум три операции. Жирным шрифтом выделим оптимальный путь.

Давайте проследим его по шагам. Переход из S в S ничего не стоит. Переход из S в SA стоит одну операцию. Переход из S в SAT стоит две операции. Переход из SU в SATU стоит две операции. Переход из SUN в SATUR стоит три операции. Переход из SUND в SATURD стоит три операции (стоимость предыдущего перехода плюс нулевая цена перехода из D в D). Переход из SUNDA в SATURDA стоит три операции. Наконец, переход из SUNDAY в SATURDAY требует тех же трёх операций.

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

Вот так, собственно, и выглядит большинство решений из мира динамического программирования. Кстати, это решение имеет название — алгоритм Вагнера-Фишера. Забавный факт: этот алгоритм практически параллельно опубликовали разные группы незнакомых ученых с разных концов планеты в эпоху, когда еще не был интернета. Товарищи Вагнер и Фишер, кстати, были далеко не первыми.

Давайте теперь рассмотрим, в чем отличия приеменения этого алгоритма от решения перебором.

Анализ решения

Как уже было сказано, решение перебором этой задачи простой рекурсией имеет временную сложность O(3^n), но не требует лишней памяти — значит, O(1) операций в памяти.

Какие издержки у динамического решения? Давайте представим, что сравниваются слова равной длины, по n символов в слове. Все решение сводится к заполнению таблицы с n+1 строчками (отдельная для пустой строки ε), и n+1 столбиками. Значит, используется (n+1)^2 ячеек. Не будем считать копейки, и округлим количество ячеек до n^2. Для каждой ячейки мы будем проверять трех ее соседей, что требует константного времени O(1). Значит, на заполнение всей таблицы потребуется O(n^2) операций.

Какой будет расход памяти? Для таблицы с n^2 ячеек нам нужно O(n^2) памяти.

Если слова разной длины, то можно либо смотреть по самому длинному, либо несколько повысить степень сложности формулы. Например, если первое слово имеет длину n, а второе — m, то потребуется O(nm) времени и O(nm) памяти.

Основная идея динамического программирования должна прослеживаться в представленном примере: мы жертвуем солидным количеством памяти (O(nm) вместо O(1)), но получаем просто сумасшедший выигрыш во времени (O(nm) против O(3^n)).

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

Преимущества:

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

Универсальность. One Ring to rule them all — создание компактной системы из нескольких правил для заполнения таблицы гарантирует решение задачи на любых данных. Ни исключений, ни пограничных случаев, несколько строчек, — и сложная проблема решена.

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

Недостатки:

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

Когнитивная нагрузка. Решение запутанной задачи с помощью компактной система правил — очень заманчивая идея. Но тут есть один нюанс: для составления или хотя бы для понимания этих систем правил необходимо научиться «думать на динамическом программировании». Это является причиной довольно спорной репутации динамического программирования.

Области применения

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

Ученые в этой области занимаются «оцифровыванием» биологического материала, а так же хранением и анализом полученной информации. В этой науке сотни захватывающих аспектов, и она ставит перед разработчиками очень серьезные задачи, ведь данных невероятно много. Например, в геноме человека около трех миллиардов пар нуклеотидов (кирпичиков ДНК). Одна пара обычно кодируется одним байтом, в итоге выходит около трех миллиардов байт информации на один-единственный геном — три гигабайта данных на одно человека.

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

Это только один пример. Биоинформатика буквально живет динамическим программированием — вот еще несколько примеров:

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

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