Методы разработки алгоритмов. Метод декомпозиции.

Самым важным и наиболее широко применимым методом проектирования эффективных алгоритмов является метод, называемый методом декомпозиции (или метод "разделяй и властвуй", или метод разбиения). Этот метод предполагает такую декомпозицию (разбиение) задачи размера n на более мелкие задачи, что на основе решений этих более мелких задач можно легко получить решение исходной задачи. Чтобы проиллюстрировать этот метод, рассмотрим хорошо известную головоломку "Ханойские башни". Имеются три стержня А, В и С. Вначале на стержень А нанизаны несколько дисков: диск наибольшего диаметра находится внизу, а выше — диски последовательно уменьшающегося диаметра, как показано на рис.. Цель головоломки — перемещать диски (по одному) со стержня на стержень так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы в конце концов все диски оказались нанизанными на стержень В. Стержень С можно использовать для временного хранения дисков.

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

Задачу перемещения n наименьших дисков со стержня A на стержень B можно

представить себе состоящей из двух подзадач размера n – 1.Сначала нужно

переместить n – 1 наименьших дисков со стержня A на стержень C, оставив на

стержне A n-й наибольший диск. Затем этот диск нужно переместить с A на B.

Потом следует переместить n – 1 дисков со стержня C на стержень B. Это

перемещение n – 1 дисков выполняется путем рекурсивного применения указанного
метода. Поменьше тех, которые в перемещении не участвуют, не нужно

задумываться над тем, что находится под перемещаемыми дисками на стержнях A,

B или C.

Хотя фактическое перемещение отдельных дисков не столь очевидно, а

моделирование вручную выполнить непросто из-за образования стеков рекурсивных

вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост

для понимания и доказательства его правильности (а если говорить о быстроте

разработки, то ему вообще нет равных). Именно легкость разработки алгоритмов

по методу декомпозиции обусловила огромную популярность этого метода; к тому

же во многих случаях эти алгоритмы оказываются более эффективными, чем

алгоритмы, разработанные традиционными методами.

Расписание проведения турнира, таким образом, представляет собой таблицу, состоящую из л строк и п — 1 столбцов; элементом на пересечении строки i и столбца j является номер игрока, с которым игрок i должен провести матч в у'-й день. Метод декомпозиции позволяет составить расписание для половины игроков. Это расписание составляется на основе рекурсивного применения данного алгоритма для половины этой половины игроков и т.д. Когда количество игроков будет сокращено до двух, возникнет "базовая ситуация", в которой мы просто устанавливаем порядок проведения встреч между ними. Допустим, в турнире участвуют восемь игроков. Расписание для игроков 1 - 4 заполняет верхний левый угол (4 строки х З столбца) составляемого расписания. Нижний левый угол (4 строки х З столбца) этого расписания должен свести между собой игроков с более высокими номерами (5 - 8). Эта часть расписания получается путем прибавления числа 4 к каждому элементу в верхнем левом углу.

Итак, нам удалось упростить задачу. Теперь остается свести между собой игроков с низкими и более высокими номерами. Сделать это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 - 4, с игроками 5-8 соответственно, а в последующие дни просто циклически переставлять номера 5 - 8. Этот процесс показан на рис. 10.3. Надеемся, теперь читатель сможет обобщить описанный алгоритм и составить расписание для 2* игроков при любом значении k.