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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. (неопр.) . — 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, « от 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. (неопр.) // Proc. 40th Symp. on the Foundations of Computer Science. — 1999. 13 декабря 2019 года.
↑ Frigo, M.; Johnson, S. G. (англ.) // (англ.) (: journal. — 2005. — February (vol. 93 , no. 2). — P. 216—231 . — doi : . 25 февраля 2021 года.

Литература

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