Русская Википедия:Разделяй и властвуй (информатика)
Шаблон:Значения «Разделяй и властвуй» в информатике — схема разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Корректность работы алгоритма, следующего парадигме «разделяй и властвуй», чаще всего доказывается с помощью метода математической индукции, а время работы определяется либо путём непосредственного решения соответствующего рекуррентного уравнения, либо применением основной теоремы о рекуррентных соотношениях.
Основная идея схемы состоит в том, чтобы разложить задачу на две или более сходных, но более простых подзадач, решить их поочерёдно и скомпоновать их решения. Например, чтобы отсортировать заданный список из <math>n</math> натуральных чисел, необходимо разбить его на два списка примерно из <math>n/2</math> чисел каждый, отсортировать каждый из них по очереди и скомпоновать оба результата соответствующим образом, чтобы получить отсортированную версию данного списка. Этот подход известен как алгоритм сортировки слиянием.
Характеристика «разделяй и властвуй» иногда применяется к алгоритмам, которые сводят каждую задачу только к одной подзадаче, таким как алгоритм двоичного(бинарного) поиска для нахождения записи в отсортированном списке (или его частный случай, алгоритм бисекции для поиска корней)[1]. Эти алгоритмы могут быть реализованы более эффективно, чем общие алгоритмы «разделяй и властвуй»; в частности, если они используют хвостовую рекурсию, они могут быть преобразованы в простые циклы. Однако в соответствии с этим широким определением каждый алгоритм, использующий рекурсию или циклы, может рассматриваться как «алгоритм разделения и завоевания». Поэтому некоторые авторы считают, что название «разделяй и властвуй» следует использовать только тогда, когда каждая задача может порождать две или более подзадач.[2]Вместо этого было предложено имя уменьшай и властвуй для класса одиночных задач.[3]
Примеры
Ранними примерами таких алгоритмов являются в первую очередь «уменьшай и властвуй» — исходная задача последовательно разбивается на отдельные подзадачи, и в действительности может быть решена итеративно. Двоичный поиск, в котором подзадачи имеют примерно половину исходного размера, известен со времён Вавилона, хотя чёткое описание как компьютерного алгоритма получил в 1946 году в статье Джона Мокли[4]. Ещё один древний алгоритм типа «уменьшай и властвуй» — алгоритм Евклида для вычисления наибольшего общего делителя из двух чисел путём уменьшения чисел до меньших и меньших эквивалентных подзадач, который датируется несколькими веками до нашей эры.
Ранний пример алгоритма «разделяй и властвуй» с несколькими подзадачами — гауссово (1805) описание метода, известного в современности как быстрое преобразование Фурье Кули — Тьюки[5].
Ранний алгоритм «разделяй и властвуй» из двух подзадач, который был специально разработан для компьютеров и должным образом проанализирован, является алгоритмом сортировки слиянием, изобретённый Джоном фон Нейманом в 1945 году.[6]
Типичный пример — алгоритм сортировки слиянием. Чтобы отсортировать массив чисел по возрастанию, он разбивается на две равные части, каждая сортируется, затем отсортированные части сливаются в одну. Эта процедура применяется к каждой из частей до тех пор, пока сортируемая часть массива содержит хотя бы два элемента (чтобы можно было её разбить на две части). Время работы этого алгоритма составляет <math>O(n \log n)</math> операций, тогда как более простые алгоритмы требуют <math>O(n^2)</math> времени, где <math>n</math> — размер исходного массива.
Ещё один примечательный пример — это алгоритм Карацубы[7] умножения двух чисел из <math>n</math> цифр путём <math>O(n^{\log_2 3})</math> числа операции. Этот алгоритм опроверг гипотезу Колмогорова 1956 года о том, что для этой задачи потребовалось бы <math>O(n^2)</math> операций.
В качестве ещё одного примера изначально некомпьютерного алгоритма «разделяй и властвуй» Кнут приводит метод маршрутизации почтовых отправлений: письма сортируются в отдельные пакеты, предназначенные для разных географических районов, каждый из этих пакетов делится на партии для более мелких подрайонов и так далее, пока они не будут доставлены[4]. На том же принципе основе реализована с поразрядная сортировка перфокарт (IBM, 1929)[4].
Преимущества
«Разделяй и властвуй» — мощный инструмент для решения концептуально сложных задач: все, что требуется для этого, — это найти случай разбивания задачи на подзадачи, решения тривиальных случаев и объединения подзадач в исходную задачу. Аналогично, «уменьшай и властвуй» требует только свести проблему к одной меньшей проблеме, такой как классическая Ханойская башня, которая сводит решение к перемещению башни высоты n к перемещению башни высоты n − 1.
Парадигма часто помогает в открытии эффективных алгоритмов. Это послужило ключом, например, к быстрому методу умножения Карацубы, алгоритмам быстрой сортировки и сортировки слиянием, алгоритму Штрассена для умножения матриц и быстрых преобразований Фурье.
Во всех этих примерах подход «разделяй и властвуй» привёл к улучшению асимптотической стоимости решения в самом решении. Например, если базовый вариант имеет размер, ограниченный постоянной, то работа по разбиению задачи и объединению частичных решений пропорциональна размеру задачи <math>n</math> и существует ограниченное число <math>p</math> подзадач приблизительного размера <math>n/p</math> на каждом этапе, тогда эффективность алгоритма «разделяй и властвуй» будет равна <math>O(n \log_p n</math>.
Алгоритмы «разделяй и властвуй» естественным образом адаптированы для выполнения многопроцессорными машинами, особенно системами с общей памятью, в которых передача данных между процессорами не должна планироваться заранее, поскольку отдельные подзадачи могут выполняться на разных процессорах.
Алгоритмы «разделяй и властвуй» естественным образом стремятся эффективно использовать кэш-память: как только подзадача достаточно мала, она и все её подзадачи могут в принципе быть решены в кэше, не обращаясь к более медленной основной памяти. Алгоритм, предназначенный для использования кэша таким образом, называется Шаблон:Нп2, потому что он не содержит размер кэша в качестве явного параметра[8]. Традиционный подход к использованию кэша — блокировка, как и в Шаблон:Iw, где задача явно разделена на куски соответствующего размера, — также может использовать кэш оптимально, но только тогда, когда алгоритм настроен для конкретного размера кэша конкретной машины.
То же самое преимущество существует в отношении других иерархических систем хранения данных, таких как NUMA или виртуальная память, а также для нескольких уровней кэша: как только подзадача достаточно мала, она может быть решена в пределах данного уровня иерархии, без доступа к более высоким (более медленным) уровням.
Проблемы применения
Алгоритмы «разделяй и властвуй» естественным образом применяются в виде рекурсивных методов. В этом случае частные подзадачи, ведущие к той, которая в настоящее время решается, автоматически сохраняются в стеке вызовов процедур. Рекурсивная функция — это числовая функция числового аргумента, которая в своей записи содержит себя же.
Такие алгоритмы также могут быть применены нерекурсивной программой, которая хранит частные подзадачи в некоторой явной структуре данных, такой как стек , очередь или приоритетная очередь .Такой подход позволяет получить большую свободу в выборе подзадачи, которая должна быть решена следующей. Особенность, которая важна в некоторых приложениях — например, в методе ветвления и привязки для оптимизации функций. Этот подход также является стандартным решением в языках программирования, которые не обеспечивают поддержку рекурсивных процедур.
В рекурсивных реализациях алгоритмов «разделяй и властвуй» необходимо убедиться, что для стека рекурсии выделено достаточно памяти, иначе выполнение может завершиться неудачей из-за переполнения стека. Алгоритмы «разделяй и властвуй», которые эффективны по времени, часто имеют относительно небольшую глубину рекурсии. Например, алгоритм, быстрой сортировки может быть реализован таким образом, что он никогда не требует больше, чем <math>\log_2 n</math> вложенных рекурсивных вызовов для сортировки n элементов.
Переполнение стека может быть трудно избежать при использовании рекурсивных процедур, так как многие компиляторы предполагают, что стек рекурсии является смежной областью памяти, и некоторые выделяют для него фиксированное количество пространства. Компиляторы также могут сохранять в стеке рекурсии больше информации, чем это строго необходимо, например, возвращаемый адрес, неизменяемые параметры и внутренние переменные процедур. Таким образом, риск переполнения стека может быть уменьшен путём минимизации параметров и внутренних переменных рекурсивной процедуры или использованием явной структуры стека.
Выбор базовых вариантов
В любом рекурсивном алгоритме существует значительная свобода в выборе базовых случаев, небольших подзадач, которые решаются непосредственно для завершения рекурсии.
Выбор самых маленьких или простейших возможных базовых случаев, является более элегантным и обычно приводит к более простым программам, потому что в таком варианте меньше случаев для рассмотрения, и их легче решить. Например, быстрое преобразование Фурье может остановить рекурсию, когда входные данные являются одним образцом, а алгоритм сортировки списка быстрой сортировкой может остановиться, когда входные данные являются пустым списком; в обоих примерах есть только один базовый случай для рассмотрения, и он не требует обработки.
С другой стороны, эффективность часто повышается, если рекурсия останавливается в относительно больших базовых случаях, и они решаются нерекурсивно, что приводит к Шаблон:Iw. Эта стратегия позволяет избежать накладывания рекурсивных вызовов, которые работают мало или не работают, а также может позволить использовать специализированные нерекурсивные алгоритмы, которые для этих базовых случаев являются более эффективными, чем явная рекурсия. Общая процедура для простого гибридного рекурсивного алгоритма заключается в коротком замыкании базового случая, также известного как рекурсия на расстоянии вытянутой руки. В этом случае перед вызовом функции проверяется, приведёт ли следующий шаг к базовому регистру, избегая ненужного вызова функции. Поскольку алгоритм «разделяй и властвуй» в конечном итоге сводит каждый пример проблемы или подзадачи к большому числу базовых экземпляров, они часто доминируют в общей эффективности алгоритма, особенно когда накладные расходы на разделение/присоединение невелики. Причём эти соображения не зависят от того, реализуется ли рекурсия компилятором или явным стеком.
Таким образом, например, многие библиотечные применения быстрой сортировки превратятся в простой алгоритм сортировки вставки на основе цикла (или аналогичный), как только количество элементов, подлежащих сортировке, будет достаточно мало. Причём, если бы пустой список был единственным базовым случаем, то сортировка списка с <math>n</math> записями привела бы к максимальному <math>n</math> числу вызовов быстрых сортировок, которые ничего не сделают, но сразу же вернутся. Увеличение базовых случаев до списков размером 2 или менее приведёт к устранению большинства из этих вызовов «ничего не сделать», и в более общем случае базовый случай размером более 2 обычно используется для уменьшения доли времени, затрачиваемого на выполнение служебных функций или манипуляции стеком.
В качестве альтернативы можно использовать большие базовые случаи, которые все ещё используют алгоритм «Разделяй и властвуй», но реализуют алгоритм для предопределенного набора фиксированных размеров, где алгоритм может быть полностью развёрнут в код, который не имеет рекурсии, циклов или условных обозначений (связанных с методикой частичной оценки). Например, этот подход используется в некоторых эффективных применениях быстрого преобразования Фурье, где базовыми случаями являются развёрнутые реализации алгоритмов «разделяй и властвуй» для набора фиксированных размеров[9]. Методы генерации исходного кода могут быть использованы для получения большого числа отдельных базовых случаев, желательных для эффективного осуществления этой стратегии.
Обобщенный вариант этой идеи известен как рекурсия «разворачивание» или «укрупнение», и были предложены различные методы для автоматизации процедуры расширения базового случая[9].
Совместное использование повторяющихся подзадач
Для некоторых задач разветвлённая рекурсия может привести к многократной оценке одной и той же подзадачи. В таких случаях, возможно, стоит определить и сохранить решения этих перекрывающихся подзадач, метод, обычно известный как мемоизация. Следуя до предела, это приводит к восходящим алгоритмам «Разделяй и властвуй», таким как динамическое программирование и разбор диаграмм.
См. также
- Основная теорема о рекуррентных соотношениях
- Шаблон:Iw
- Шаблон:Iw
- Математическая индукция
- MapReduce
- Эвристический алгоритм
Примечания
Литература
- ↑ Шаблон:Книга
- ↑ Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
- ↑ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).
- ↑ 4,0 4,1 4,2 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
- ↑ Heideman, M. T., D. H. Johnson, and C. S. Burrus, «Gauss and the history of the fast Fourier transform Шаблон:Wayback», IEEE ASSP Magazine, 1, (4), 14-21 (1984).
- ↑ Шаблон:Книга
- ↑ Шаблон:Статья
- ↑ Шаблон:Статья
- ↑ 9,0 9,1 Шаблон:Статья
