Алгоритм «разделяй и властвуй»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Параллелизм

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

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

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

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

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

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

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

Рекурсия

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

Явный стек

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

Размер стека

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

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

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

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

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

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

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

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

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

Динамическое программирование для перекрывающихся подзадач

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

См. также

Ссылки

^ Блаут, Ричард (14 мая 2014 г.). Быстрые алгоритмы обработки сигналов . Издательство Кембриджского университета. стр. 139–143. ISBN 978-0-511-77637-3 .
^ Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Стейн (31 июля 2009 г.). Введение в алгоритмы . С Прессой. ISBN 978-0-262-53305-8 .
^ Брассард, Г., и Брэтли, П. Основы алгоритмики, Прентис-Холл, 1996.
^ Анани В. Левитин, Введение в разработку и анализ алгоритмов (Аддисон Уэсли, 2002).
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Дональд Э. Кнут, Искусство компьютерного программирования: Том 3, Сортировка и поиск , второе издание (Аддисон-Уэсли, 1998).
^ Хайдеман, М.Т., Д.Х. Джонсон и К.С. Буррус, « Гаусс и история быстрого преобразования Фурье », журнал IEEE ASSP Magazine, 1, (4), 14–21 (1984).
^ Кнут, Дональд (1998). Искусство компьютерного программирования: Том 3. Сортировка и поиск . п. 159 . ISBN 0-201-89685-0 .
^ Karatsuba, Anatolii A. ; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR . 146 : 293–294. Translated in Карацуба, А.; Офман, Ю. (1963). «Умножение многозначных чисел на автоматах» . Доклады советской физики . 7 : 595–596. Бибкод : 1963СФД....7..595К .
^ М. Фриго; CE Лейзерсон; Х. Прокоп (1999). «Алгоритмы, не обращающие внимания на кэш» . 40-й ежегодный симпозиум по основам информатики (кат. № 99CB37039) . стр. 285–297. дои : 10.1109/SFCS.1999.814600 . ISBN 0-7695-0409-4 . S2CID 62758836 .
^ Николас Дж. Хайэм, « Точность суммирования с плавающей запятой », SIAM J. Scientific Computing 14 (4), 783–799 (1993).
↑ Перейти обратно: Перейти обратно: ^а ^б Фриго, М.; Джонсон, С.Г. (февраль 2005 г.). «Проектирование и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . дои : 10.1109/JPROC.2004.840301 . S2CID 6644892 .
^ Раду Ругина и Мартин Ринар, « Развертывание рекурсии для программ «разделяй и властвуй »» в книге «Языки и компиляторы для параллельных вычислений» , глава 3, стр. 34–48. Конспекты лекций по информатике, том. 2017 (Берлин: Springer, 2001).

[1] Блаут, Ричард (14 мая 2014 г.). Быстрые алгоритмы обработки сигналов . Издательство Кембриджского университета. стр. 139–143. ISBN 978-0-511-77637-3 .

[CormenLeiserson2009-2] Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Стейн (31 июля 2009 г.). Введение в алгоритмы . С Прессой. ISBN 978-0-262-53305-8 .

[3] Брассард, Г., и Брэтли, П. Основы алгоритмики, Прентис-Холл, 1996.

[4] Анани В. Левитин, Введение в разработку и анализ алгоритмов (Аддисон Уэсли, 2002).

[Knuth3-5] Перейти обратно: Перейти обратно: ^а ^б ^с Дональд Э. Кнут, Искусство компьютерного программирования: Том 3, Сортировка и поиск , второе издание (Аддисон-Уэсли, 1998).

[Heideman84-6] Хайдеман, М.Т., Д.Х. Джонсон и К.С. Буррус, « Гаусс и история быстрого преобразования Фурье », журнал IEEE ASSP Magazine, 1, (4), 14–21 (1984).

[7] Кнут, Дональд (1998). Искусство компьютерного программирования: Том 3. Сортировка и поиск . п. 159 . ISBN 0-201-89685-0 .

[8] Karatsuba, Anatolii A. ; Yuri P. Ofman (1962). "Умножение многозначных чисел на автоматах". Doklady Akademii Nauk SSSR . 146 : 293–294. Translated in Карацуба, А.; Офман, Ю. (1963). «Умножение многозначных чисел на автоматах» . Доклады советской физики . 7 : 595–596. Бибкод : 1963СФД....7..595К .

[cahob-9] М. Фриго; CE Лейзерсон; Х. Прокоп (1999). «Алгоритмы, не обращающие внимания на кэш» . 40-й ежегодный симпозиум по основам информатики (кат. № 99CB37039) . стр. 285–297. дои : 10.1109/SFCS.1999.814600 . ISBN 0-7695-0409-4 . S2CID 62758836 .

[10] Николас Дж. Хайэм, « Точность суммирования с плавающей запятой », SIAM J. Scientific Computing 14 (4), 783–799 (1993).

[fftw-11] Перейти обратно: Перейти обратно: ^а ^б Фриго, М.; Джонсон, С.Г. (февраль 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).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Структуры данных и алгоритмы
Структуры данных	Множество Ассоциативный массив Бинарное дерево поиска Дерево Фенвика График Хэш-таблица Куча Связанный список Очередь Дерево сегментов Куча Нить Дерево Три
Алгоритмы	Возврат Бинарный поиск Поиск в ширину Поиск методом перебора Поиск в глубину Разделяй и властвуй Динамическое программирование Обход графа Складывать Жадный Хэш-функция Минимакс Онлайн Рандомизированный Рекурсия Поиск корней Сортировка Потоковое вещание Развертка линии Поиск строк Топологическая сортировка
Список структур данных Список алгоритмов