Алгоритм разделяй и властвуй - Divide-and-conquer algorithm

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

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

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

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

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

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

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

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

Ранние исторические примеры

Ранние примеры этих алгоритмов в основном уменьшаются и побеждают - исходная проблема последовательно разбивается на отдельные подзадачи и действительно может быть решена итеративно.

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

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

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

Другой примечательный пример - алгоритм, изобретенный Анатолием Карацубой в 1960 году, который мог умножать два n- значных числа в операциях (в нотации Big O ). Этот алгоритм опроверг предположение Андрея Колмогорова 1956 года о том, что для этой задачи потребуются операции. ${\ Displaystyle О (п ^ {\ журнал _ {2} 3})}$ ${\ Displaystyle \ Omega (п ^ {2})}$

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

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

Решение сложных проблем

«Разделяй и властвуй» - это мощный инструмент для решения концептуально сложных проблем: все, что для этого требуется, - это способ разбить проблему на подзадачи, решить тривиальные случаи и объединить подзадачи с исходной проблемой. Точно так же уменьшение и победа требует только сведения проблемы к одной меньшей задаче, такой как классическая головоломка Ханойская башня , которая уменьшает перемещение башни высоты для перемещения башни высоты . ${\ displaystyle n}$ ${\ displaystyle n-1}$

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

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

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

Параллелизм

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

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

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

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

Контроль округления

В вычислениях с округленной арифметикой, например, с числами с плавающей запятой , алгоритм «разделяй и властвуй» может давать более точные результаты, чем внешне эквивалентный итерационный метод. Например, можно сложить N чисел либо с помощью простого цикла, который добавляет каждое значение к одной переменной, либо с помощью алгоритма D&C, называемого попарным суммированием, который разбивает набор данных на две половины, рекурсивно вычисляет сумму каждой половины, а затем добавляет две суммы. Хотя второй метод выполняет то же количество добавлений, что и первый, и оплачивает накладные расходы на рекурсивные вызовы, обычно он более точен.

Проблемы реализации

Рекурсия

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

Явный стек

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

Размер стопки

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

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

Выбор базовых случаев

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

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

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

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

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

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

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

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

Languages

In other projects