Алгоритм 4.4. Сортировка слиянием

ВХОД. Последовательность чисел х₁, x_{2 ,}..., х_n, где n - степень числа 2.

ВЫХОД. Последовательность чисел у₁, y₂,..., у_n, которая является перестановкой входа и удовлетворяет неравенствам y₁ £ y₂ £...£ y_n.

МЕТОД. Применим процедуру MERGE(S, Т) (merge - слияние), входом которой служат две упорядоченные последовательности S и Т, а выходом - последовательность Q элементов из S и Т, расположенных в порядке неубывания. Поскольку S и Т упорядочены, MERGE требует сравнений не больше, чем сумма длин S и Т без единицы (|S| + |T| -1). Работа этой процедуры состоит в выборе большего из наибольших элементов, остающихся в S и Т, и в последующем удалении выбранного элемента и перезаписи его в Q. В случае совпадения можно отдавать предпочтение последовательности S. Кроме того, применяется процедура SORT(i, j) (см. ниже), сортирующая подпоследовательность x_i, x_i+1,..., x_j в предположении, что она имеет длину 2^k для некоторого k ³ 0. Для сортировки исходной последовательности вызывается процедура SORT(1, n).

procedure SORT(i, j)

if i=j then return x_i

Else

Begin

m(i+j-1)/2;

return MERGE(SORT(i, m), SORT(m+ 1, j))

End.

Подсчёт числа сравнений в алгоритме 4.4 приводит к рекуррентным уравнениям

решением которых по теореме 4.1 является Т (n)= О (nlog₂n). Для больших n сбалансированность размеров подзадач даёт значительную выгоду. Аналогичный анализ показывает, что общее время работы процедуры SORT, затрачиваемое не только на сравнение, также есть О (nlog₂n).

4.3.4. Динамическое программирование

Рекурсивная техника полезна, если задачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим. Из теоремы 4.1вытекает, что если сумма размеров подзадач равна an для некоторой постоянной а >0, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность. Но если очевидное разбиение задачи размера n сводит её к n задачам размера n-1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность.

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

В сущности, при динамическом программировании вычисляется решение для всех подзадач. Вычисление идет от малых подзадач к большим, и ответы запоминаются в таблице. Преимущество этого метода состоит в том, что раз уж задача решена, её ответ где-то хранится и никогда не вычисляется заново.

Рассмотрим эту технику на примере вычисления произведения k матриц М=М₁ x М₂ x...x М_k, где M_i - матрица с r_i-1 строками и r_i столбцами. Порядок, в котором эти матрицы перемножаются, может существенно сказаться на общем числе операций, требуемых для вычисления М, независимо от алгоритма, применяемого для умножения матриц.

Пример 4.1. Будем считать, что умножение (р x q)-матрицы на (q x r)-матрицу требует pqr операций, и рассмотрим произведение (в квадратных скобках указаны размерности матриц).

М= М₁ x М₂ x М₃ x М₄

[10 x 20] [20 x 50] [50 x 1] [1 x 100]

Если вычислять М в порядке М₁x(М₂x(М₃xМ₄)), то потребуется 125000 операций, тогда как вычисления в порядке (М₁x(М₂xМ₃))xМ₄ занимают лишь 2200 операций.

Процесс перебора всех порядков, в которых можно вычислить рассматриваемое произведение n матриц с целью минимизации числа операций, имеет экспоненциальную сложность, что при больших n практически неприемлемо. Однако динамическое программирование приводит к алгоритму сложности О(n ³).

Алгоритмы с возвратом

Особенно интересный раздел программирования - это задачи из области “искусственного интеллекта”. Здесь нужно строить алгоритмы, которые находят решение определённой задачи не по фиксированным правилам вычисления, а методом проб и ошибок. Обычно процесс проб и ошибок разделяется на отдельные подзадачи. Часто эти подзадачи наиболее естественно описываются с помощью рекурсии. Процесс проб и ошибок можно рассматривать в общем виде как процесс поиска, который постепенно строит и просматривает (а также обрезает) дерево подзадач. Во многих случаях такие деревья поиска растут очень быстро, обычно экспоненциально, в зависимости от заданного параметра. Соответственно увеличивается стоимость поиска. Часто дерево поиска можно обрезать, используя только эвристические соображения, и тем самым сводить количество вычислений к разумным пределам.

Далее на примере задачи о ходе коня рассматривается общий принцип разбиения таких задач на подзадачи и использование в них рекурсии.

Задача “Обход конем шахматной доски n x n ”. Конь помещается на поле с начальными координатами Х₀, У₀. Нужно покрыть ходами коня всю доску (осуществить обход доски) за n ²-1 ход, при том, что каждое поле посещается ровно один раз.

Эта задача покрытия n ² полей сводится к более простой: или выполнить очередной ход, или установить, что никакой ход невозможен.

Характерная черта этого алгоритма состоит в том, что он предпринимает какие-то шаги по направлению к общему решению, эти шаги фиксируются (записываются), но можно возвращаться обратно и стирать записи, если оказывается, что шаг не приводит к решению, а заводит в “тупик”. Такое действие называется возвратом.

Пусть число возможных дальнейших путей на каждом шаге конечно и фиксировано (например, равно m); пусть используется явный параметр уровня, обозначающий глубину рекурсии и допускающий простое условие окончания. Тогда схема, типичная для задач подобного рода, может быть представлена так:

procedure try (i)

begin k:= 0; (*инициировать выборку возможных шагов*)

repeat k:= k +1; выбрать k-й возможный путь;

if приемлемо then

begin записать его;

if i < n then (*решение неполно*)

begin try (I +1); (*попробовать очередной шаг*)

if неудачно then стереть запись

End

End

until удачно & (k=m)

End.

4.4. Построение и анализ алгоритма

4.4.1. Как разрабатывать алгоритм?