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

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

Этот метод «разделяй и властвуй» является основой эффективных алгоритмов для решения всех видов проблем, таких как сортировка (например., быстрая сортировка, Сортировка слиянием ), умножение больших чисел (например, Алгоритм Карацубы ), найдя ближайшая пара точек, синтаксический анализ (например., нисходящие парсеры ), и вычисляя дискретное преобразование Фурье (БПФ ).[1]

Понимание и разработка алгоритмов «разделяй и властвуй» - это сложный навык, требующий хорошего понимания природы основной проблемы, которую необходимо решить. Как при доказательстве теорема к индукция, часто бывает необходимо заменить исходную задачу более общей или сложной задачей, чтобы инициализировать рекурсию, а систематического метода поиска надлежащего обобщения не существует.[требуется разъяснение ] Эти сложности «разделяй и властвуй» проявляются при оптимизации расчета Число Фибоначчи с эффективной двойной рекурсией.[Зачем? ][нужна цитата ]

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

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

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

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

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

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

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

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

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

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

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

Другой примечательный пример - алгоритм изобретен Анатолий Александрович Карацуба в 1960 г.[8] что может умножить два п-значные числа в операции (в Обозначение Big O ). Этот алгоритм опровергнут Андрей Колмогоров гипотеза 1956 г. для этой задачи потребуются операции.

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

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

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

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

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

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

Во всех этих примерах подход D&C привел к улучшению асимптотическая стоимость решения. Например, если: а) базовые случаи имеют постоянный ограниченный размер, работа по разделению задачи и объединению частичных решений пропорциональна размеру проблемы п, и (б) существует ограниченное число п подзадач размера ~ п/п на каждом этапе стоимость алгоритма «разделяй и властвуй» составит O (п бревнопп).

Параллелизм

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

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

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

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

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

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

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

Рекурсия

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

Явный стек

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ Блаут, Ричард. Быстрые алгоритмы обработки сигналов. Издательство Кембриджского университета. С. 139–143. ISBN  978-0-511-77637-3.
  2. ^ Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Штайн (31 июля 2009 г.). Введение в алгоритмы. MIT Press. ISBN  978-0-262-53305-8.
  3. ^ Брассард Г. и Брэтли П. Основы алгоритмики, Прентис-Холл, 1996.
  4. ^ Ананий Валерьевич Левитин, Введение в разработку и анализ алгоритмов (Аддисон Уэсли, 2002).
  5. ^ а б c Дональд Э. Кнут, Искусство программирования: Том 3, Сортировка и поиск, второе издание (Addison-Wesley, 1998).
  6. ^ Хайдеман, М. Т., Д. Х. Джонсон и К. С. Буррус "Гаусс и история быстрого преобразования Фурье ", IEEE ASSP Magazine, 1, (4), 14–21 (1984).
  7. ^ Кнут, Дональд (1998). Искусство программирования: Том 3: сортировка и поиск. п.159. ISBN  0-201-89685-0.
  8. ^ Карацуба, Анатолий А.; Юрий Петрович Офман (1962). "Умножение многозначных чисел на автоматах". Доклады Академии Наук СССР. 146: 293–294. Переведено на «Умножение многозначных чисел на автоматах». Советская физика.. 7: 595–596. 1963.
  9. ^ М. Фриго; К. Э. Лейзерсон; Х. Прокоп (1999). "Алгоритмы без кеширования". Proc. 40-й симпозиум. Об основах информатики: 285–297. Дои:10.1109 / SFFCS.1999.814600. ISBN  0-7695-0409-4. S2CID  62758836.
  10. ^ Николас Дж. Хайэм "Точность суммирования с плавающей запятой ", SIAM J. Научные вычисления 14 (4), 783–799 (1993).
  11. ^ а б Frigo, M .; Джонсон, С. Г. (февраль 2005 г.). «Дизайн и реализация FFTW3» (PDF). Труды IEEE. 93 (2): 216–231. CiteSeerX  10.1.1.66.3097. Дои:10.1109 / JPROC.2004.840301. S2CID  6644892.
  12. ^ Раду Ругина и Мартин Ринард "Рекурсия для программ "разделяй и властвуй" " в Языки и компиляторы для параллельных вычислений, глава 3, стр. 34–48. Конспект лекций по информатике т. 2017 (Берлин: Springer, 2001).