Войти
В информатике, разделяй и властвуй - это парадигма построения алгоритма на основе многоразветвленной рекурсии. Алгоритм «разделяй и властвуй» работает путем рекурсивного разбиения проблемы на две или более подзадач одного и того же или родственного типа, пока они не станут достаточно простыми для непосредственного решения. Затем решения подзадач объединяются, чтобы дать решение исходной проблемы.
Этот метод «разделяй и властвуй» является основой эффективных алгоритмов для решения всех видов проблем, таких как сортировка (например, quicksort, merge sort ), умножение больших чисел (например, алгоритм Карацубы ), поиск ближайшей пары точек, синтаксический анализ (например,, нисходящие синтаксические анализаторы ) и вычисление дискретного преобразования Фурье (FFT ).
Понимание и разработка алгоритмов «разделяй и властвуй» - это сложный навык, требующий хорошего понимание природы основной проблемы, которую необходимо решить. Как и при доказательстве теоремы с помощью индукции, часто необходимо заменить исходную проблему более общей или сложной проблемой, чтобы для инициализации рекурсии, и не существует систематического метода нахождения надлежащего обобщения. Эти сложности, связанные с разделением и владением, видны при оптимизации вычисления числа Фибоначчи с эффективной двойной рекурсией.
Коррекция Правильность алгоритма «разделяй и властвуй» обычно подтверждается математической индукцией, а его вычислительные затраты часто определяются путем решения рекуррентных соотношений.
Разделяй и -конвертирующий подход для сортировки списка (38, 27, 43, 3, 9, 82, 10) в порядке возрастания. Верхняя половина: разделение на подсписки; mid: одноэлементный список легко сортируется; нижняя половина: составление отсортированных подсписок. Парадигма «разделяй и властвуй» часто используется для поиска оптимального решения проблемы. Его основная идея состоит в том, чтобы разложить данную проблему на две или более похожих, но более простых подзадач, решить их по очереди и составить их решения для решения данной проблемы. Проблемы достаточной простоты решаются напрямую. Например, чтобы отсортировать данный список из n натуральных чисел, разделите его на два списка примерно по n / 2 чисел в каждом, отсортируйте каждый из них по очереди и соответствующим образом чередуйте оба результата, чтобы получить отсортированную версию данного списка (см. картина). Этот подход известен как алгоритм сортировки слиянием .
Название «разделяй и властвуй» иногда применяется к алгоритмам, которые сводят каждую проблему только к одной подзадаче, например, алгоритм двоичного поиска для поиска записи в отсортированном списке ( или его аналог в численных вычислениях, алгоритм деления пополам для нахождения корня ). Эти алгоритмы могут быть реализованы более эффективно, чем общие алгоритмы «разделяй и властвуй»; в частности, если они используют хвостовую рекурсию, их можно преобразовать в простые циклы. Однако согласно этому широкому определению каждый алгоритм, использующий рекурсию или циклы, может рассматриваться как «алгоритм разделения и владения». Поэтому некоторые авторы считают, что название «разделяй и властвуй» следует использовать только тогда, когда каждая проблема может порождать две или более подзадач. Вместо этого для класса одной подзадачи было предложено имя уменьшение и победа .
Важное применение принципа «разделяй и властвуй» - это оптимизация, когда пространство поиска сокращается («сокращается»)) с постоянным множителем на каждом шаге, общий алгоритм имеет ту же асимптотическую сложность, что и шаг сокращения, с константой, зависящей от фактора сокращения (путем суммирования геометрического ряда ); это известно как сокращение и поиск.
Ранние примеры этих алгоритмов в основном уменьшают и побеждают - исходная проблема последовательно разбивается на отдельные подзадачи и действительно может быть решена итеративно.
Двоичный поиск, алгоритм «убывай и властвуй», в котором подзадачи составляют примерно половину исходного размера, имеет долгую историю. Хотя четкое описание алгоритма на компьютерах появилось в 1946 году в статье Джона Мочли, идея использования отсортированного списка элементов для облегчения поиска восходит, по крайней мере, к Вавилонии в 200 г. до н. э. Другой древний алгоритм уменьшения и победы - это алгоритм Евклида для вычисления наибольшего общего делителя двух чисел путем сокращения чисел до все меньших и меньших эквивалентных подзадач, который датируется несколькими столетиями до нашей эры..
Ранним примером алгоритма «разделяй и властвуй» с множеством подзадач является описание Гаусса в 1805 году того, что сейчас называется быстрым преобразованием Фурье Кули – Тьюки (БПФ), хотя он не анализировал количество операций количественно, и БПФ не получили широкого распространения, пока не были заново открыты более века спустя.
Первым алгоритмом DC с двумя подзадачами, который был специально разработан для компьютеров и должным образом проанализирован, является алгоритм сортировки слиянием, изобретенный Джоном фон Нейманом в 1945 году.
Другим ярким примером является алгоритм , изобретенный Анатолием А. Карацуба в 1960 году, который может умножать два n-значных числа в 
В качестве еще одного примера алгоритма «разделяй и властвуй», изначально не использовавшего компьютеры, Дональд Кнут приводит метод, который почтовое отделение обычно использует для маршрутизации почты: письма сортируются в отдельные пакеты для разных географических регионов, каждый из этих пакетов сам сортируется по партиям для более мелких субрегионов, и так далее, пока они не будут доставлены. Это связано с сортировкой по основанию, описанной для машин сортировки перфокарт еще в 1929 году.
«Разделяй и властвуй» - мощный инструмент для решения концептуально сложных проблем: все, что для этого требуется, - это способ разбить проблему на подзадачи, решить тривиальные случаи и объединить подзадачи с исходной проблемой. Точно так же уменьшение и победа требует только сведения проблемы к одной меньшей задаче, такой как классическая головоломка Ханойская башня, в которой перемещение башни высотой n сводится к перемещению башни высотой n - 1.
Парадигма «разделяй и властвуй» часто помогает в открытии эффективных алгоритмов. Это было ключом, например, к методу быстрого умножения Карацубы, алгоритмам быстрой сортировки и сортировки слиянием, алгоритму Штрассена для умножения матриц и быстрым преобразованиям Фурье.
Во всех этих примерах подход DC привел к улучшению асимптотической стоимости решения. Например, если (а) базовые случаи имеют постоянный ограниченный размер, работа по разделению проблемы и объединению частичных решений пропорциональна размеру проблемы n, и (б) существует ограниченное число p подзадач размера ~ n / p на каждом этапе, тогда стоимость алгоритма «разделяй и властвуй» будет O (n log p n).
Алгоритмы разделения и владения естественным образом адаптированы для выполнения на многопроцессорных машинах, особенно в системах с разделяемой памятью, в которых обмен данными между процессорами не выполняется. необходимо планировать заранее, потому что отдельные подзадачи могут выполняться на разных процессорах.
Алгоритмы разделения и владения, естественно, имеют тенденцию эффективно использовать кеши памяти. Причина в том, что как только подзадача становится достаточно маленькой, она и все связанные с ней подзадачи, в принципе, могут быть решены в кэше, без доступа к более медленной основной памяти. Алгоритм, предназначенный для использования кеша таким образом, называется без учета кеша, потому что он не содержит размер кеша в качестве явного параметра. Более того, алгоритмы DC могут быть разработаны для важных алгоритмов (например, сортировки, БПФ и умножения матриц) как оптимальные алгоритмы без учета кеширования - они используют кеш, вероятно, оптимальным образом, в асимптотическом смысле, независимо от размера кеша. Напротив, традиционный подход к использованию кеша - это блокирование, как в оптимизации вложенности циклов, где проблема явно разделена на фрагменты соответствующего размера - это также может использовать кеш оптимально, но только когда алгоритм настроен для конкретных размеров кеша конкретной машины.
Такое же преимущество существует в отношении других иерархических систем хранения, таких как NUMA или виртуальная память, а также для нескольких уровней кеша: один раз под- проблема достаточно мала, ее можно решить в рамках данного уровня иерархии, без доступа к более высоким (более медленным) уровням.
В вычислениях с округленной арифметикой, например с числами с плавающей запятой алгоритм «разделяй и властвуй» может дать более точные результаты, чем внешне эквивалентный итерационный метод. Например, можно сложить N чисел либо с помощью простого цикла, который добавляет каждую точку данных к одной переменной, либо с помощью алгоритма DC под названием попарное суммирование, которое разбивает набор данных на две половины, рекурсивно вычисляет сумму каждую половину, а затем складывает две суммы. Хотя второй метод выполняет то же количество добавлений, что и первый, и оплачивает накладные расходы на рекурсивные вызовы, он обычно более точен.
Алгоритмы «разделяй и властвуй» естественным образом реализуются как рекурсивные процедуры. В этом случае частичные подзадачи, ведущие к решаемой в настоящее время, автоматически сохраняются в стеке вызовов процедур . Рекурсивная функция - это функция, которая вызывает себя в пределах своего определения.
Алгоритмы разделения и владения также могут быть реализованы нерекурсивной программой, которая сохраняет частичные подзадачи в некоторой явной структуре данных, такой как стек , очередь или очередь приоритета. Этот подход дает больше свободы в выборе подзадачи, которая должна быть решена следующей, функция, которая важна в некоторых приложениях, например в рекурсии в ширину и в методе ветвей и границ для оптимизации функций. Этот подход также является стандартным решением для языков программирования, не поддерживающих рекурсивные процедуры.
В рекурсивных реализациях алгоритмов DC необходимо убедиться, что для стека рекурсии выделено достаточно памяти, иначе выполнение может завершиться неудачно из-за переполнения стека . Эффективные по времени алгоритмы DC часто имеют относительно небольшую глубину рекурсии. Например, алгоритм быстрой сортировки может быть реализован так, чтобы он никогда не требовал более 
Может быть трудно избежать переполнения стека при использовании рекурсивных процедур, поскольку многие компиляторы предполагают, что стек рекурсии является непрерывной областью памяти, и некоторые выделяют для нее фиксированный объем пространства. Компиляторы также могут сохранять в стеке рекурсии больше информации, чем это строго необходимо, например адрес возврата, неизменяемые параметры и внутренние переменные процедуры. Таким образом, риск переполнения стека может быть уменьшен путем минимизации параметров и внутренних переменных рекурсивной процедуры или использования явной структуры стека.
В любом рекурсивном алгоритме существует значительная свобода в выборе базовых случаев, небольших подзадач, которые решаются напрямую, чтобы завершить рекурсию.
Выбор наименьшего или простейшего возможных базовых случаев более элегантен и обычно приводит к более простым программам, потому что меньше случаев для рассмотрения и их легче решать. Например, алгоритм БПФ может остановить рекурсию, когда входной сигнал представляет собой одну выборку, а алгоритм сортировки списка быстрой сортировки может остановиться, когда входом является пустой список; в обоих примерах необходимо рассмотреть только один базовый случай, и он не требует обработки.
С другой стороны, эффективность часто повышается, если рекурсия останавливается в относительно больших базовых случаях, и они решаются нерекурсивно, что приводит к гибридному алгоритму. Эта стратегия позволяет избежать накладных расходов, связанных с рекурсивными вызовами, которые работают мало или совсем не работают, а также может позволить использовать специализированные нерекурсивные алгоритмы, которые для этих базовых случаев более эффективны, чем явная рекурсия. Общая процедура для простого гибридного рекурсивного алгоритма заключается в сокращении базового случая, также известном как рекурсия на расстоянии. В этом случае, приведет ли следующий шаг к базовому случаю, проверяется перед вызовом функции, избегая ненужного вызова функции. Например, в дереве вместо рекурсивного перехода к дочернему узлу с последующей проверкой, является ли он нулевым, проверяя null перед рекурсивным выполнением; это позволяет избежать половины вызовов функций в некоторых алгоритмах двоичных деревьев. Поскольку алгоритм DC в конечном итоге сокращает каждый экземпляр проблемы или подзадачи до большого числа базовых экземпляров, они часто доминируют в общей стоимости алгоритма, особенно когда накладные расходы на разделение / объединение невелики. Обратите внимание, что эти соображения не зависят от того, реализована ли рекурсия компилятором или явным стеком.
Таким образом, например, многие библиотечные реализации быстрой сортировки переключатся на простой алгоритм сортировки вставкой на основе цикла (или аналогичный), как только количество сортируемых элементов станет достаточно малым. Обратите внимание, что если бы пустой список был единственным базовым случаем, сортировка списка с n записями повлекла бы за собой максимум n вызовов быстрой сортировки, которые ничего не сделали бы, кроме немедленного возврата. Увеличение базовых случаев до списков размером 2 или меньше устранит большинство этих бездействующих вызовов, и в более общем случае базовый вариант больше 2 обычно используется для уменьшения доли времени, затрачиваемой на служебные вызовы функций или манипуляции со стеком.
В качестве альтернативы можно использовать большие базовые случаи, которые по-прежнему используют алгоритм «разделяй и властвуй», но реализуют алгоритм для заранее определенного набора фиксированных размеров, где алгоритм может быть полностью развернут в код без рекурсии, циклов или условных выражений (связанных с техникой частичной оценки ). Например, этот подход используется в некоторых эффективных реализациях БПФ, где базовыми случаями являются развернутые реализации алгоритмов БПФ «разделяй и властвуй» для набора фиксированных размеров. Методы генерации исходного кода могут использоваться для создать большое количество отдельных базовых случаев, желательных для эффективной реализации этой стратегии.
Обобщенная версия этой идеи известна как «разворачивание» или «укрупнение» рекурсии, и были предложены различные методы для автоматизации процедуры расширение базового случая.
Для некоторых проблем разветвленная рекурсия может закончиться многократным повторением одной и той же подзадачи. В таких случаях, возможно, стоит определить и сохранить решения этих перекрывающихся подзадач, метод, широко известный как мемоизация. Если следовать до предела, это приводит к восходящим алгоритмам разделения и владения, таким как динамическое программирование и анализ диаграммы.
 | Wikimedia Commons СМИ, связанные с алгоритмами «разделяй и властвуй». |
