В информатике разделяй и властвуй — это парадигма разработки алгоритмов . Алгоритм разделяй и властвуй рекурсивно разбивает задачу на две или более подзадач одного и того же или связанного типа, пока они не станут достаточно простыми для непосредственного решения. Затем решения подзадач объединяются , чтобы дать решение исходной задачи.
Метод «разделяй и властвуй» является основой эффективных алгоритмов для многих задач, таких как сортировка (например, быстрая сортировка , сортировка слиянием ), умножение больших чисел (например, алгоритм Карацубы ), поиск ближайшей пары точек , синтаксический анализ (например, нисходящие анализаторы ) и вычисление дискретного преобразования Фурье ( БПФ ). [1]
Разработка эффективных алгоритмов «разделяй и властвуй» может быть сложной. Как и в математической индукции , часто необходимо обобщить задачу, чтобы сделать ее поддающейся рекурсивному решению. Корректность алгоритма «разделяй и властвуй» обычно доказывается математической индукцией, а его вычислительная стоимость часто определяется путем решения рекуррентных соотношений .
Парадигма «разделяй и властвуй» часто используется для поиска оптимального решения проблемы. Ее основная идея заключается в разложении данной проблемы на две или более похожих, но более простых подзадач, их поочередном решении и составлении их решений для решения данной проблемы. Достаточно простые задачи решаются напрямую. Например, чтобы отсортировать заданный список из n натуральных чисел , разбейте его на два списка примерно по n /2 чисел в каждом, отсортируйте каждый из них по очереди и перемешайте оба результата соответствующим образом, чтобы получить отсортированную версию данного списка (см. рисунок). Этот подход известен как алгоритм сортировки слиянием .
Название «разделяй и властвуй» иногда применяется к алгоритмам, которые сводят каждую проблему только к одной подзадаче, например, к алгоритму двоичного поиска для поиска записи в отсортированном списке (или его аналогу в числовых вычислениях , алгоритму деления пополам для поиска корня ). [2] Эти алгоритмы могут быть реализованы более эффективно, чем общие алгоритмы «разделяй и властвуй»; в частности, если они используют хвостовую рекурсию , их можно преобразовать в простые циклы . Однако в рамках этого широкого определения каждый алгоритм, использующий рекурсию или циклы, можно рассматривать как «алгоритм разделяй и властвуй». Поэтому некоторые авторы считают, что название «разделяй и властвуй» следует использовать только тогда, когда каждая проблема может порождать две или более подзадач. [3] Название «уменьшай и властвуй » было предложено вместо этого для класса с одной подзадачой. [4]
Важное применение принципа «разделяй и властвуй» — оптимизация, [ нужен пример ] , где, если пространство поиска уменьшается («обрезается») на постоянный множитель на каждом шаге, общий алгоритм имеет ту же асимптотическую сложность, что и шаг отсечения, при этом константа зависит от множителя отсечения (путем суммирования геометрической прогрессии ); это известно как отсечение и поиск .
Ранними примерами таких алгоритмов являются, прежде всего, алгоритмы «уменьшение и преодоление» — исходная задача последовательно разбивается на отдельные подзадачи и действительно может быть решена итеративно.
Двоичный поиск , алгоритм «уменьшай и властвуй», где подзадачи имеют примерно половину исходного размера, имеет долгую историю. Хотя четкое описание алгоритма на компьютерах появилось в 1946 году в статье Джона Мочли , идея использования отсортированного списка элементов для облегчения поиска восходит по крайней мере к Вавилонии в 200 году до нашей эры. [5] Другим древним алгоритмом «уменьшай и властвуй» является алгоритм Евклида для вычисления наибольшего общего делителя двух чисел путем сведения чисел к все меньшим и меньшим эквивалентным подзадачам, который датируется несколькими столетиями до нашей эры.
Ранним примером алгоритма «разделяй и властвуй» с несколькими подзадачами является описание Гауссом в 1805 году того, что сейчас называется алгоритмом быстрого преобразования Фурье (БПФ) Кули–Тьюки [6], хотя он не анализировал количество его операций количественно, и БПФ не получили широкого распространения, пока не были заново открыты более столетия спустя.
Ранним алгоритмом D&C с двумя подзадачами, который был специально разработан для компьютеров и должным образом проанализирован, является алгоритм сортировки слиянием , изобретенный Джоном фон Нейманом в 1945 году . [7]
Другим ярким примером является алгоритм , изобретенный Анатолием А. Карацубой в 1960 году [8], который мог умножать два n - значных числа за операции (в нотации Big O ). Этот алгоритм опроверг гипотезу Андрея Колмогорова 1956 года о том, что для этой задачи потребуются операции.
В качестве другого примера алгоритма «разделяй и властвуй», который изначально не включал компьютеры, Дональд Кнут приводит метод, который обычно используется почтовым отделением для маршрутизации почты: письма сортируются в отдельные мешки для разных географических областей, каждый из этих мешков в свою очередь сортируется на партии для более мелких субрегионов, и так далее, пока они не будут доставлены. [5] Это связано с радиксной сортировкой , описанной для сортировочных машин с перфокартами еще в 1929 году. [5]
Разделяй и властвуй — мощный инструмент для решения концептуально сложных проблем: все, что для этого требуется, — это способ разбить проблему на подзадачи, решить тривиальные случаи и объединить подзадачи в исходную проблему. Аналогично, для уменьшения и властвования требуется только свести проблему к одной меньшей задаче, например, классической головоломке «Ханойская башня» , которая сводит перемещение башни высотой к перемещению башни высотой .
Парадигма «разделяй и властвуй» часто помогает в открытии эффективных алгоритмов. Она была ключом, например, к быстрому методу умножения Карацубы , алгоритмам быстрой сортировки и сортировки слиянием, алгоритму Штрассена для умножения матриц и быстрым преобразованиям Фурье.
Во всех этих примерах подход D&C привел к улучшению асимптотической стоимости решения. Например, если (a) базовые случаи имеют ограниченный по константе размер, работа по разделению задачи и объединению частичных решений пропорциональна размеру задачи , и (b) существует ограниченное число подзадач размером ~ на каждом этапе, то стоимость алгоритма «разделяй и властвуй» будет .
Алгоритмы «разделяй и властвуй» естественным образом адаптированы для выполнения на многопроцессорных машинах, особенно в системах с общей памятью , где обмен данными между процессорами не нужно планировать заранее, поскольку отдельные подзадачи могут выполняться на разных процессорах.
Алгоритмы «разделяй и властвуй» естественным образом стремятся эффективно использовать кэши памяти . Причина в том, что как только подзадача становится достаточно маленькой, она и все ее подзадачи, в принципе, могут быть решены в кэше , без доступа к более медленной основной памяти . Алгоритм, разработанный для использования кэша таким образом, называется забывающим кэш , потому что он не содержит размер кэша в качестве явного параметра . [9] Более того, алгоритмы D&C могут быть разработаны для важных алгоритмов (например, сортировки, БПФ и умножения матриц), чтобы быть оптимальными алгоритмами, забывающими кэш — они используют кэш, вероятно, оптимальным образом, в асимптотическом смысле, независимо от размера кэша. Напротив, традиционный подход к использованию кэша — это блокировка , как в оптимизации гнезда циклов , где задача явно делится на фрагменты соответствующего размера — это также может оптимально использовать кэш, но только когда алгоритм настроен на конкретные размеры кэша конкретной машины.
Такое же преимущество существует и в отношении других иерархических систем хранения данных, таких как NUMA или виртуальная память , а также для нескольких уровней кэша: как только подзадача становится достаточно маленькой, ее можно решить на заданном уровне иерархии, не обращаясь к более высоким (более медленным) уровням.
В вычислениях с округленной арифметикой, например, с числами с плавающей точкой , алгоритм «разделяй и властвуй» может давать более точные результаты, чем внешне эквивалентный итерационный метод. Например, можно сложить N чисел либо простым циклом, который добавляет каждый элемент данных к одной переменной, либо алгоритмом D&C, называемым парным суммированием , который разбивает набор данных на две половины, рекурсивно вычисляет сумму каждой половины, а затем складывает две суммы. Хотя второй метод выполняет то же количество сложений, что и первый, и оплачивает накладные расходы рекурсивных вызовов, он обычно более точен. [10]
Алгоритмы «разделяй и властвуй» естественным образом реализуются как рекурсивные процедуры . В этом случае частичные подзадачи, ведущие к решаемой в данный момент задаче, автоматически сохраняются в стеке вызовов процедур . Рекурсивная функция — это функция, которая вызывает сама себя в своем определении.
Алгоритмы «разделяй и властвуй» также могут быть реализованы нерекурсивной программой, которая сохраняет частичные подзадачи в некоторой явной структуре данных, такой как стек , очередь или приоритетная очередь . Такой подход обеспечивает большую свободу в выборе подзадачи, которая должна быть решена следующей, что важно в некоторых приложениях — например, в рекурсии в ширину и методе ветвей и границ для оптимизации функций. Этот подход также является стандартным решением в языках программирования, которые не поддерживают рекурсивные процедуры.
В рекурсивных реализациях алгоритмов D&C необходимо убедиться, что для стека рекурсии выделено достаточно памяти, в противном случае выполнение может завершиться неудачей из-за переполнения стека . Алгоритмы D&C, которые эффективны по времени, часто имеют относительно небольшую глубину рекурсии. Например, алгоритм быстрой сортировки может быть реализован так, что для сортировки элементов ему никогда не потребуется больше, чем вложенные рекурсивные вызовы .
Переполнение стека может быть трудно избежать при использовании рекурсивных процедур, поскольку многие компиляторы предполагают, что стек рекурсии является непрерывной областью памяти, и некоторые выделяют для него фиксированный объем пространства. Компиляторы также могут сохранять больше информации в стеке рекурсии, чем это строго необходимо, например, адрес возврата, неизменяемые параметры и внутренние переменные процедуры. Таким образом, риск переполнения стека можно снизить, минимизировав параметры и внутренние переменные рекурсивной процедуры или используя явную структуру стека.
В любом рекурсивном алгоритме существует значительная свобода в выборе базовых случаев — небольших подзадач, которые решаются напрямую для завершения рекурсии.
Выбор наименьших или самых простых возможных базовых случаев более элегантен и обычно приводит к более простым программам, поскольку приходится рассматривать меньше случаев и их легче решать. Например, алгоритм быстрого преобразования Фурье может остановить рекурсию, когда на входе находится один образец, а алгоритм быстрой сортировки списков может остановиться, когда на входе находится пустой список; в обоих примерах необходимо рассмотреть только один базовый случай, и он не требует обработки.
С другой стороны, эффективность часто повышается, если рекурсия останавливается на относительно больших базовых случаях, и они решаются нерекурсивно, что приводит к гибридному алгоритму . Эта стратегия позволяет избежать накладных расходов на рекурсивные вызовы, которые выполняют мало или вообще не выполняют работы, а также может позволить использовать специализированные нерекурсивные алгоритмы, которые для этих базовых случаев более эффективны, чем явная рекурсия. Общая процедура для простого гибридного рекурсивного алгоритма — это короткое замыкание базового случая , также известное как рекурсия на расстоянии вытянутой руки . В этом случае перед вызовом функции проверяется, приведет ли следующий шаг к базовому случаю, что позволяет избежать ненужного вызова функции. Например, в дереве вместо рекурсии к дочернему узлу и последующей проверки того, является ли он нулевым, проверка нуля перед рекурсией; позволяет избежать половины вызовов функций в некоторых алгоритмах на двоичных деревьях. Поскольку алгоритм D&C в конечном итоге сводит каждую проблему или подпроблему к большому числу базовых экземпляров, они часто доминируют в общей стоимости алгоритма, особенно когда накладные расходы на разделение/объединение невелики. Обратите внимание, что эти соображения не зависят от того, реализована ли рекурсия компилятором или явным стеком.
Так, например, многие библиотечные реализации быстрой сортировки переключатся на простой циклический алгоритм сортировки вставкой (или аналогичный), как только количество сортируемых элементов станет достаточно малым. Обратите внимание, что если бы пустой список был единственным базовым случаем, сортировка списка с записями повлекла бы за собой максимальное количество вызовов быстрой сортировки, которые ничего не делали бы, но немедленно возвращали бы результат. Увеличение базовых случаев до списков размером 2 или меньше устранит большинство этих ничего не делающих вызовов, и в более общем случае базовый случай больше 2 обычно используется для сокращения доли времени, затрачиваемого на накладные расходы на вызов функций или манипуляции со стеком.
В качестве альтернативы можно использовать большие базовые случаи, которые все еще используют алгоритм «разделяй и властвуй», но реализовать алгоритм для предопределенного набора фиксированных размеров, где алгоритм может быть полностью развернут в код, который не имеет рекурсии, циклов или условных операторов (связанных с техникой частичной оценки ). Например, этот подход используется в некоторых эффективных реализациях FFT, где базовые случаи являются развернутыми реализациями алгоритмов FFT «разделяй и властвуй» для набора фиксированных размеров. [11] Методы генерации исходного кода могут использоваться для создания большого количества отдельных базовых случаев, желаемых для эффективной реализации этой стратегии. [11]
Обобщенная версия этой идеи известна как «развертывание» или «огрубление» рекурсии, и были предложены различные методы для автоматизации процедуры укрупнения базового случая. [12]
Для некоторых задач разветвленная рекурсия может в конечном итоге оценивать одну и ту же подзадачу много раз. В таких случаях может быть полезно идентифицировать и сохранять решения этих перекрывающихся подзадач, метод, который обычно известен как мемоизация . Доведенный до предела, он приводит к восходящим алгоритмам «разделяй и властвуй», таким как динамическое программирование .
