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

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

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

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

Разделяй и властвуй

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

Парадигма «Разделяй и властвуй» часто используется для поиска оптимального решения той или иной проблемы. Его основная идея состоит в том, чтобы разложить данную задачу на две или более сходных, но более простых подзадач, решить их поочередно и скомпоновать их решения. Например, чтобы отсортировать заданный список из n натуральных чисел, необходимо разбить его на два списка примерно из n /2 чисел каждый, отсортировать каждый из них по очереди и скомпоновать оба результата соответствующим образом, чтобы получить отсортированную версию данного списка (см. рисунок). Этот подход известен как алгоритм сортировки слиянием.

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

Примеры

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

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

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

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

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

Еще один примечательный пример - это алгоритм, придуманный Карацуба Анатолием Александровичем в 1960 году, умножения двух чисел из n цифр путем [math]\displaystyle{ O(n^{\log_2 3}) }[/math] числа операции (большое обозначение O). Этот алгоритм опроверг гипотезу Андрея Колмогорова 1956 год о том, что для этой задачи потребовалось бы [math]\displaystyle{ O(n^2) }[/math] операций.

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

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

Решение сложных задач

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

Эффективность алгоритма

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

Во всех этих примерах подход «Разделяй и властвуй» привел к улучшению ассимптотической стоимости решения в самом решении. Например, если (a) базовый вариант имеет размер, ограниченный постоянной, то работа по разбиению задачи и объединению частичных решений пропорциональна размеру задачи n, и (b) существует ограниченное число p подзадач размера ~ n/p на каждом этапе, тогда эффективность алгоритма «Разделяй и властвуй» будет равна O(n log_pn).

Параллелизм

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

Доступ к памяти

Алгоритмы «Разделяй и властвуй» естественным образом стремятся эффективно использовать кэш память. Причина заключается в том, что как только подзадача достаточно мала, она и все ее подзадачи могут в принципе быть решены в кэше, не обращаясь к более медленной основной памяти. Алгоритм, предназначенный для использования кэша таким образом, называется cache-oblivious, потому что он не содержит размер кэша в качестве явного параметра. Кроме того, алгоритмы «Разделяй и властвуй» могут быть разработаны для важных алгоритмов (например, сортировка, БПФ  и умножение матриц), чтобы стать оптимальными cache-oblivious алгоритмами - они используют кэш, вероятно, оптимальным способом, в асимптотическом смысле, независимо от размера кэша. Напротив, традиционный подход к использованию кэша – блокировка, как и в оптимизации вложенных циклов, где задача явно разделена на куски соответствующего размера — это также может использовать кэш оптимально, но только тогда, когда алгоритм настроен для конкретного размера кэша конкретной машины.

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

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

Рекурсия

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

Явный стек

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

Размер стека

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

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

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

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

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

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

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

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

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

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

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

См. также

• Основная теорема о рекуррентных соотношениях
• Decomposable aggregate functions
• Fork–join model
• Математическая индукция
• MapReduce
• Эвристический алгоритм

Литература

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