Программа 7.

Merge(out1, out2, size1, sorted);

Sorting(array, min2, max2, out2, size1);

Sorting(array, min1, max1, out1, size1);

Sorting(array, in_min, in_max, ptr_sorted, NUM);

Randomize();

Программа 6.

// Программа сортирует элементы массива array в неубывающем порядке с помощью

// рекурсивной процедуры разбиения массива на две равные части и последующим

// слиянием отсортированных подмассивов

// NUM – размер исходного массива

#include <stdlib.h>

#include <stdio.h>

#include <io.h>

#include <alloc.h>

#include <time.h>

#define Mem_error {printf("Недостаточно памяти. \n"); exit(2);}

#define NUM 1024

int array[NUM], sorted[NUM];

void Sorting(int array[], int *in_min, int *in_max, int *sorted, unsigned size);

void Merge(int *out1, int *out2, unsigned size, int *sorted);

void main()

{

int *in_max, *in_min, *ptr_sorted;

unsigned index;

// В этом месте должна стоять функция ввода массива array

// Задание границ массива

in_max=&array[NUM-1]; in_min=&array[0];

// Процедура сортировки

ptr_sorted=sorted;

} // Конец main

void Sorting(int array[], int *in_min, int *in_max, int *sorted, unsigned size)

// Функция сортировки массива с помощью техники рекурсии и слияния

{

unsigned size1;

int *max1, *min1, *max2, *min2, *out1, *out2;

if (size==1) *sorted=*in_min;

else

void Merge(int *out1, int *out2, unsigned size, int *sorted)

// Слияние двух отсортированных в неубывающем порядке подмассивов в один

{

unsigned ind1=0, ind2=0;

while ((ind1<size)&&(ind2<size))

{

if (out1[ind1] < out2[ind2]) *sorted++=out1[ind1++];

else *sorted++=out2[ind2++];

if (ind1==size)

while (ind2<size) *sorted++=out2[ind2++];

if (ind2==size)

while (ind1<size) *sorted++=out1[ind1++];

}

} // Конец Merge

Работа функции Merge состоит в выборе наименьшего из наименьших элементов сливаемых массивов и занесении его в выходной массив. После этого выбранный элемент удаляется из рассматриваемых массивов, и происходит сравнение следующих двух наименьших чисел. Поскольку сливаемые множества S и T сами уже упорядочены, то подобная процедура не требует числа сравнений, большего, чем сумма длин S и T без единицы.

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

, (1.10)

решением которых по теореме 1 является C(n)=O(n×logn). Для больших n сбалансированность размеров подзадач дала значительную выгоду.

Ещё один важный момент данной программы заключается в том, что функция Sorting использует динамическую память для сливаемых подмассивов, которая выделяется и освобождается по мере надобности. Данный приём используется очень часто для представления структур, связанных со списками и деревьями.

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

Рекурсивная техника полезна, если задачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим. Из теоремы 1 следует, что если сумма размеров подзадач равна a×n для некоторой постоянной a>1, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность. Однако если очевидное разбиение задачи размера n сводит её к n подзадачам размера n-1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность. В этом случае часто можно получить более эффективные алгоритмы с помощью техники, называемой динамическим программированием (dynamic programming).

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

Пусть требуется вычислить произведение n матриц

M = M₁´M₂´…´M_n,

где M_i - матрица с числом строк r_i-1 и числом столбцов r_i (размера r_i-1´r_i). Порядок, в котором перемножаются данные матрицы, может существенно сказаться на общем числе операций, требуемых для вычисления M, независимо от алгоритма, используемого для умножения матриц.

Пример 1.7. Предположим, что для умножения матрицы размера (p´q) на матрицу (q´r) требуется p´q´r операций, как это бывает в «обычном» алгоритме, и рассмотрим произведение:

M = M₁ ´ M₂ ´ M₃,

(10´20) (20´1) (1´50)

где внизу указаны размеры матриц. Если теперь вычислить M в порядке M₁´(M₂´M₃), то потребуется 11000 операций. Когда же произведение M будет вычислено в порядке (M₁´M₂)´ M₃, то потребуется всего 700 операций.ð

Доказано, что процесс перебора всех возможных порядков, в которых можно вычислить рассматриваемое произведение n матриц, с целью минимизировать число операций имеет экспоненциальную сложность O(2ⁿ), что для больших n практически неприемлемо. Однако динамическое программирование приводит к алгоритму сложности O(n³). Пусть m_ij - минимальная сложность вычисления M_i´M_i+1´…´M_j (1£ i£ j£ n). Очевидно, что

(1.11)

Здесь m_ik - минимальная сложность вычисления M′=M_i+1´M_i+2´…´M_k, а m_k+1,j - минимальная сложность вычисления M″=M_k+1´M_k+2´…´M_j. Третье слагаемое равно сложности умножения M′ на M″. Поскольку матрица M′ имеет размер r_i-1´ r_k, а матрица M″ - размер r_k´ r_j. В (1.11) утверждается, что m_ij (j > i) - наименьшая из сумм этих трёх членов по всем возможным значениям k, лежащим между i и j-1.

При динамическом программировании m_ij вычисляются в порядке возрастания разнос­тей нижних индексов. Начинают с вычисления m_ii для всех i, затем m_i,i+1 для всех i, потом m_i,i+2 и т.д. При этом m_ik и m_k+1,j в (1.11) будут уже вычислены, до того, как приступают к вычислению m_ij. Это следует из того, что при i £ k < j разность j-i должна быть больше k-i, а также и j-(k+1).

Алгоритм 7. Динамического программирования для вычисления порядка, минимизирующего сложность умножения цепочки из n матриц M₁´M₂´…´M_n

Вход. r₀, r₁, …, r_n, где r_i-1 и r_i - числа строк и столбцов матрицы M_i.

Выход. Минимальная сложность умножения матриц M_i в предположении, что для умножения (p´q)-матрицы на (q´r)-матрицу требуется p×q×r операций.

Метод. Алгоритм заполняет последовательно «верхнетреугольную» матрицу минимальных сложностей умножения двух, трех, четырех, … и т.д. матриц из предлагаемой последовательности. На первом шаге заполняется строка, соответствующая сложности умножения двух матриц, взятых последовательно из предлагаемого произведения. На втором шаге рассчитываются минимальные сложности умножения трёх последовательных матриц, основываясь на известных минимальных сложностях умножения двух матриц. Заполняется соответствующая строка, и т.д.

// Программа рассчитывает матрицу минимальных сложностей умножения NUM матриц,

// размеры которых r₀, r₁, …, r_n заданы в массиве Sizes

#include <stdlib.h>

#include <stdio.h>

#include <io.h>

#define NUM 6 // Число перемножаемых матриц

#define NUM1 NUM+1 // Размер массива Sizes

unsigned Sizes[NUM1]; // Массив, содержащий размеры перемножаемых матриц

unsigned long Time_comp[(NUM1*NUM)>>1]; // Матрица минимальных сложностей умножения

void main()

{

unsigned long value, temp, *ptr, *current[NUM<<1];

unsigned ind, index, count, curr, max, min;

// Здесь должна стоять функция ввода массива Sizes

// Процедура заполнения матрицы Time_copm с помощью метода

// динамического программирования

ptr=Time_comp;

for(index=0; index<NUM; *ptr++=0, index++); // Первая строка заполняется нулями

for (ind=1; ind<NUM; ind++)

{

max=(ind<<1)-1;

// Предварительный расчёт указателей на элементы матрицы Time_copm, которые

// используются в дальнейшем при выборе минимальной сложности умножения.

// Указатели хранятся в массиве current.

for(index=0; index<ind; index++)

{

count=(index*((NUM<<1)-index+1))>>1;

curr=count+ind-index;

current[index<<1]=&Time_comp[count];

current[(index<<1)+1]=&Time_comp[curr];

}

for (index=1; index<NUM; index++)

{

count=ind+index;

if(count>NUM) break;

// Выбор минимальной сложности умножения заданного количества матриц

value=4294967294; // максимальное число типа long int

for(curr=index; curr<count; curr++)

{

min=(curr-index)<<1;

temp=*current[min]++ + *current[max-min]++ + Sizes[index-1]*Sizes[curr]*Sizes[count];

if (value > temp) value=temp;

}

*ptr++=value; // Заполнение текущего элемента матрицы Time_comp

}

}

} // Конец main

Рассмотрим характерный пример умножения некоторого количества матриц.

Пример 1.8. Предположим, что требуется найти произведение шести матриц

M = M₁ ´ M₂ ´ M₃´ M₄ ´ M₅ ´ M₆,

(15´7) (7´8) (8´46) (46´2) (2´39) (39´38)

соответствующие размеры которых указаны под матрицами. Здесь величины r₀, r₁, r₂, r₃, r₄, r₅, r₆ соответственно равны 15, 7, 8, 46, 2, 39, 38. В результате работы алгоритма 7 получается матрица минимальных сложностей умножения, показанная в таблице 4. Из матрицы видно, что минимальная сложность умножения данных шести матриц равна 5162. Из этой же таблицы несложно получить и порядок умножения матриц. Для этого надо приписать к каждой клетке таблицы то значение k, на котором достигается минимум (1.11). Для удобства полученные значения k показаны в маленьких левых нижних клетках, а в верхних маленьких клетках показаны индексы i и j из (1.11).

Таблица 4. Сложности вычисления произведений M_i´M_i+1´…´M_j

Теперь рассмотрим последнюю клетку таблицы

Цифры в левом верхнем углу i=1, j=6 показывают, что данная клетка показывает минимальную сложность умножения матриц с первой по шестую. Эта сложность равна 5162. Цифра k=4 показывает оптимальную расстановку скобок, а именно - нужно умножить сначала матрицы (M₁´M₂´…´M₄), далее матрицы (M₅´M₆), после чего найти произведение полученных сомножителей. Чтобы найти оптимальный способ умножения (M₁´M₂´…´M₄) необходимо найти в таблице ячейку с параметрами i=1, j=4. Число k=1 в этой ячейке указывает на то, что сначала необходимо найти произведение матриц (M₂´M₃´M₄), а далее умножить его на M₁. И так далее. В результате получается следующий способ оптимального умножения матриц с точки зрения сложности вычислений (и далеко не очевидный при самостоятельном поиске варианта расстановки скобок):

M_опт = (M₁ ´ (M₂ ´ (M₃´ M₄))) ´ (M₅ ´ M₆).

(15´7) (7´8) (8´46) (46´2) (2´39) (39´38)

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

M = M₁ ´ M₂ ´ M₃´ M₄ ´ M₅ ´ M₆,

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