Разделяй и властвуй (информатика)

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

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

Разделяй и властвуй подход для сортировки списка (38, 27, 43, 3, 9, 82, 10) в порядке возрастания. Верхняя половина: разбиение на подсписки; средний: список на один элемент тривиальный отсортирован; нижняя половина сочинения отсортированных подсписков.

Основная идея схемы состоит в том, чтобы разложить задачу на две или более сходных, но более простых подзадач, решить их поочерёдно и скомпоновать их решения. Например, чтобы отсортировать заданный список из $n$ натуральных чисел, необходимо разбить его на два списка примерно из $n/2$ чисел каждый, отсортировать каждый из них по очереди и скомпоновать оба результата соответствующим образом, чтобы получить отсортированную версию данного списка. Этот подход известен как алгоритм сортировки слиянием.

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

Примеры

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

Ранний пример алгоритма «разделяй и властвуй» с несколькими подзадачами — гауссово (1805) описание метода, известного в современности как быстрое преобразование Фурье Кули — Тьюки.

Ранний алгоритм «разделяй и властвуй» из двух подзадач, который был специально разработан для компьютеров и должным образом проанализирован, является алгоритмом сортировки слиянием, изобретённый Джоном фон Нейманом в 1945 году.

Типичный пример — алгоритм сортировки слиянием. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока сортируемая часть массива содержит хотя бы два элемента (чтобы можно было её разбить на две части). Время работы этого алгоритма составляет $O(n\log n)$ операций, тогда как более простые алгоритмы требуют $O(n^{2})$ времени, где $n$ — размер исходного массива.

Ещё один примечательный пример — это алгоритм Карацубы умножения двух чисел из $n$ цифр путём $O(n^{\log _{2}3})$ числа операции. Этот алгоритм опроверг гипотезу Колмогорова 1956 года о том, что для этой задачи потребовалось бы $O(n^{2})$ операций.

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

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

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

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

Во всех этих примерах подход «разделяй и властвуй» привёл к улучшению асимптотической стоимости решения в самом решении. Например, если базовый вариант имеет размер, ограниченный постоянной, то работа по разбиению задачи и объединению частичных решений пропорциональна размеру задачи $n$ и существует ограниченное число $p$ подзадач приблизительного размера $n/p$ на каждом этапе, тогда эффективность алгоритма «разделяй и властвуй» будет равна $O(n\log _{p}n)$.

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

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

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

Проблемы применения

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

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

В рекурсивных реализациях алгоритмов «разделяй и властвуй» необходимо убедиться, что для стека рекурсии выделено достаточно памяти, иначе выполнение может завершиться неудачей из-за переполнения стека. Алгоритмы «разделяй и властвуй», которые эффективны по времени, часто имеют относительно небольшую глубину рекурсии. Например, алгоритм, быстрой сортировки может быть реализован таким образом, что он никогда не требует больше, чем $\log _{2}n$ вложенных рекурсивных вызовов для сортировки n элементов.

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

Выбор базовых вариантов

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

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

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

Таким образом, например, многие библиотечные применения быстрой сортировки превратятся в простой алгоритм сортировки вставки на основе цикла (или аналогичный), как только количество элементов, подлежащих сортировке, будет достаточно мало. Причём, если бы пустой список был единственным базовым случаем, то сортировка списка с $n$ записями привела бы к максимальному $n$ числу вызовов быстрых сортировок, которые ничего не сделают, но сразу же вернутся. Увеличение базовых случаев до списков размером 2 или менее приведёт к устранению большинства из этих вызовов «ничего не сделать», и в более общем случае базовый случай размером более 2 обычно используется для уменьшения доли времени, затрачиваемого на выполнение служебных функций или манипуляции стеком.

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

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

Совместное использование повторяющихся подзадач

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

См. также

• Основная теорема о рекуррентных соотношениях
• Декомпозируемая агрегатная функция
• Модель «ветвление — слияние»
• Математическая индукция
• MapReduce
• Эвристический алгоритм

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.