Теоретические основы разделяй и властвуй

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

• Динамическое программирование
• Жадная стратегия
• Разделяй и властвуй

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

Во-первых, мне известно о том, что мы (или, скорее, профессор) представили в классе функционального программирования, называемом «алгоритмический скелет», который возник в контексте комбинаторов. В качестве примера мы дали такой скелет для алгоритмов D & C:

Определение : Пусть - непустые множества. Мы называем элементы S- решений , а элементы P : = P ( A ) (то есть подмножества A ) называются задачами . Тогда D & C-скелет представляет собой 4-кортеж ( P β , β , D , C ) , где:$A,S$$S$ $P:=\mathfrak{P}(A)$$A$$(P_\beta, \beta, \mathcal{D}, \mathcal{C})$

• является предикатом для множества задач, и мы говорим, что задача p являетсяосновной,если P β ( p ) имеет место.$P_\beta$$p$$P_\beta(p)$
• является отображением P β → S, которое присваивает решение каждой основной задаче.$\beta$$P_\beta \rightarrow S$
• является отображением P → P ( P ), которое делит каждую задачу на множество подзадач.$\mathcal{D}$$P \rightarrow \mathfrak{P}(P)$
• является отображением P × P ( S ) → S, которое объединяет решения (в зависимости от вида «задачи поворота») подзадач для получения решения.$\mathcal{C}$$P\times \mathfrak{P}(S) \rightarrow S$

Тогда для заданного скелета и задачи p следующая общая функция f s : P → S вычисляет решение (в формальном смысле) для p :$s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$$p$$f_s: P\rightarrow S$$p$

$f_s(p)= \left\{ \begin{array}{l l} \beta(p) & \quad \text{if $p$ is basic}\\ \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise} \end{array} \right.$

где во второй строке мы используем обозначение для подмножеств X кодомена отображения f .$f(X) := \{f(x) : x\in X\}$$X$$f$

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

Во-вторых, для жадной стратегии мы получаем известный результат, что задача корректно решается общим жадным алгоритмом тогда и только тогда, когда его решения составляют взвешенный матроид. Существуют ли похожие результаты для алгоритмов D & C (необязательно основанных на методе, описанной выше)?

Формальная трактовка (чем-то напоминающая модель, предложенную в вопросе) субъекта с использованием так называемых псевдоморфизмов (то есть функций, почти морфизмов с выполнением некоторых до и после вычислений), а также соображений сложности Анализ и параллельная реализация таких алгоритмов приведены в:

Алгебраическая модель «разделяй и властвуй» и ее параллелизм . Авторы: Zhijing G. Mou и Paul Hudak ( «Журнал суперкомпьютеров» , том 2, выпуск 3, с. 257-278, ноябрь 1988 г.)

Я не знаю ничего более конкретного, чем принцип оптимальности Беллмана для алгоритмов «разделяй и властвуй». Тем не менее, основополагающая основа «разделяй и властвуй» кажется мне рекурсивным (или индуктивным) определением вклада проблемы, а затем средством объединения решений проблемы в более крупные решения. Ключевым моментом здесь является рекурсивный анализ проблемных входов и их использование в рекурсивных алгоритмах D & C.

$n$

• $n=0$
• $n=1$
• $n>1$$\lceil{\frac{n}{2}}\rceil$$\lfloor{\frac{n}{2}}\rfloor$

$n\leq1$

Важно отметить, что это не обязательно приводит к тому, что вы ожидаете от алгоритмов D & C. Мы могли бы определить структуру массива следующим образом:

• $n=0$
• $n>0$$n-1$

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

Теперь есть основная теорема для анализа алгоритмов D & C, и это проливает некоторый свет на ожидания эффективности для подкомпонентов алгоритма D & C с определенной общей эффективностью во время выполнения.