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

22

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

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

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

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

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

  • является предикатом для множества задач, и мы говорим, что задача p являетсяосновной,если P β ( p ) имеет место.PβpPβ(p)
  • является отображением P βS, которое присваивает решение каждой основной задаче.βPβS
  • является отображением P P ( P ), которое делит каждую задачу на множество подзадач.DPP(P)
  • является отображением P × P ( S ) S, которое объединяет решения (в зависимости от вида «задачи поворота») подзадач для получения решения.CP×P(S)S

Тогда для заданного скелета и задачи p следующая общая функция f s : P S вычисляет решение (в формальном смысле) для p :s=(Pβ,β,D,C)pfs:PSp

fs(p)={β(p)if p is basicC(p,f(D(p)))otherwise

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

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

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

Корнелиус Бранд
источник

Ответы:

5

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

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

Корнелиус Бранд
источник
1

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

n

  • n=0
  • n=1
  • n>1n2n2

n1

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

  • n=0
  • n>0n1

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

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

Логан Мэйфилд
источник
Примеры, которые вы приводите, вписываются в общий контекст, который я даю в своем вопросе (и на самом деле, вам может быть полезно дать конкретное заявление). Однако мой вопрос заключался в том, существует ли критерий (например, BOP или структура матроида) для решения задач алгоритмами, которые соответствуют этому шаблону.
Корнелиус Бренд