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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (неопр.). — MIT Press, 2009. — ISBN 978-0-262-53305-8.
↑ Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
↑ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).
↑ ¹ ² ³ Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
↑ Heideman, M. T., D. H. Johnson, and C. S. Burrus, «Gauss and the history of the fast Fourier transform Архивная копия от 31 июля 2020 на Wayback Machine», IEEE ASSP Magazine, 1, (4), 14-21 (1984).
↑ Donald Knuth. The Art of Computer Programming: Volume 3 Sorting and Searching (англ.). — 1998. — P. 159. — ISBN 0-201-89685-0.
↑ А. Карацуба; Ю. Офман. Умножение многозначных чисел на автоматах (рус.) // Доклады Академии наук. — 1962. — Т. 146. — С. 293—294.
↑ M. Frigo; C. E. Leiserson; H. Prokop. Cache-oblivious algorithms (неопр.) // Proc. 40th Symp. on the Foundations of Computer Science. — 1999. Архивировано 13 декабря 2019 года.
↑ ¹ ² Frigo, M.; Johnson, S. G. The design and implementation of FFTW3 (англ.) // Proceedings of the IEEE^[англ.] : journal. — 2005. — February (vol. 93, no. 2). — P. 216—231. — doi:10.1109/JPROC.2004.840301. Архивировано 25 февраля 2021 года.

Литература

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

[CormenLeiserson2009-1] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (неопр.). — MIT Press, 2009. — ISBN 978-0-262-53305-8.

[2] Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.

[3] Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

[Knuth3-4] ¹ ² ³ Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).

[Heideman84-5] Heideman, M. T., D. H. Johnson, and C. S. Burrus, «Gauss and the history of the fast Fourier transform Архивная копия от 31 июля 2020 на Wayback Machine», IEEE ASSP Magazine, 1, (4), 14-21 (1984).

[6] Donald Knuth. The Art of Computer Programming: Volume 3 Sorting and Searching (англ.). — 1998. — P. 159. — ISBN 0-201-89685-0.

[7] А. Карацуба; Ю. Офман. Умножение многозначных чисел на автоматах (рус.) // Доклады Академии наук. — 1962. — Т. 146. — С. 293—294.

[cahob-8] M. Frigo; C. E. Leiserson; H. Prokop. Cache-oblivious algorithms (неопр.) // Proc. 40th Symp. on the Foundations of Computer Science. — 1999. Архивировано 13 декабря 2019 года.

[fftw-9] ¹ ² Frigo, M.; Johnson, S. G. The design and implementation of FFTW3 (англ.) // Proceedings of the IEEE^[англ.] : journal. — 2005. — February (vol. 93, no. 2). — P. 216—231. — doi:10.1109/JPROC.2004.840301. Архивировано 25 февраля 2021 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]