5.7 Метод декомпозиции ( «Разделяй и властвуй»)

Этот метод, называемый также методом «разделяй и властвуй» или методом разбиения, возможно, является самым важным и наиболее широко применимым методом проектирования эффективных алгоритмов. Он предполагает такую декомпозицию (разбиение) задачи размера n на более мелкие задачи, что на основе решений этих более мелких задач можно легко получить решение исходной задачи. В качестве примеров применений этого метода можно назвать сортировку слиянием или применение деревьев двоичного поиска, которые рассматриваются дальше. Иногда в литературе алгоритмами с возвратом (backtracking algo- rithms) называют все алгоритмы полного перебора вглубь, а класс более интеллектуальных, уменьшающих рост дерева поиска, выде- ляют в подкласс алгоритмов вет- вей и границ (branch and bound algorithms). При использовании метода декомпозиции обычно применяется следующая последовательность действий:

1. Декомпозиция: разделяем задачу на k задач, меньших по раз- меру (размером приблизительно 1 / k от исходной);

2. «Властвование»: процесс деле- ния продолжаем рекурсивно до тех пор, пока полученные подза- дачи не будут достаточно мало- го размера для их тривиального решения. Далее решаем полу- чившиеся задачи.

3. Соединение: комбинируем решения подзадач в одно решение.

Важное условие: подзадачи, полу- чившиеся в процессе разбиения, не должны повторяться или частич- но перекрывать друг друга. Если условие не выполняется, то прин- цип «разделяй и властвуй» к таким задачам явно неприменим, и целе- сообразнее использовать другие методы.