7.7 Эффективность алгоритмов
7.7 Эффективность алгоритмов Эффективность рекурсивных алгоритмов
Рекурсия и эффективность алгоритмов. Рекурсивное программирование дает нам общий подход к решению задач – разбиению их на аналогичные подзадачи меньшей размерности, либо на задачи, представляющие собой шаги в возможных направлениях ее решения. Так или иначе, рекурсивные вызовы образуют древовидную структуру, количество вершин в которой определяет эффективность алгоритма (выражаемую обычно через трудоемкость). Разница между различными типами алгоритмов состоит в способе получения подзадач, их размерности, способе соединения полученных результатов.
- TEXT
рекурсивное или обычное разделение. Идея разделения восходит к технологическому приему - модульному программированию (3.6). В своем первоначальном варианте она предполагает разбиение на задачи различной природы. Нерекурсивное разделение позволяет достичь определенного эффекта за счет разбиения задачи на множество идентичных задач меньшей размерности с последующим объединением результата. Типичным примером здесь является сортировка однократным слиянием (4.6). Применение того же самого алгоритма рекурсивно к полученным подзадачам дает следующий класс алгоритмов – рекурсивное разделение. Как правило, независимость полученных подзадач подразумевает соответствующее разделение исходных данных задачи на непересекающиеся подмножества – этому и соответствует сам термин разделение. Эффективность (и трудоемкость) таких алгоритмов, зависит от затрат на само разделение и от пропорций разделяемых частей: лучшему случаю соответствует деление на равные части (логарифмические зависимость), худшему – выделение единственного элемента (линейные зависимости). - TEXT
жадные алгоритмы. Идеальным случаем можно считать алгоритм, способный «выбрать из нескольких зол» единственно правильное. В основе его так же лежит принцип разделения, но в каждой точке он имеет основание выбрать одну из подзадач. Обычно это делается на основании особенностей организации обрабатываемых данных или их избыточности. Типичный пример: двоичный поиск в упорядоченных данных (4.6). Основой жадных алгоритмов является всегда довольно спорное утверждение: движение «по линии наименьшего сопротивления» в каждой точке приведет к желаемому результату. - TEXT
полный перебор (исчерпывающий, комбинаторный перебор). Перечисленные выше подходы основаны на всевозможных «ухищрениях», основанных на особенностях предметной области алгоритма. Если же ничего не помогает, то остается полный перебор всех возможных вариантов решения задачи (8.4). - TEXT
динамическое программирование. В процессе порождения дерева рекурсивных вызовов возможно повторение подзадач с одними и теми же данными. Если запоминать результат их выполнения, то эффективность алгоритма может быть значительно увеличена.
Тип алгоритма
Идея алгоритма и «природа» его эффективности
Диапазон трудоемкостей
Рекурсивное или обычное разделение
«Разделяй и властвуй»: задача разбивается на идентичные подзадачи, результаты которых объединяются в общее решение
N …N logN…N2
Полный перебор
«Хуже не бывает» (без комментариев)
2N … NN…N!
Динамическое программирование
«Де жа вю»: запоминание результатов повторяющихся подзадач, увеличение производительности за счет дополнительной памяти.
Жадный алгоритм
«Рыцарь на распутье»: локальный выбор единственной из подзадач на каждом шаге дает глобальное оптимальное решение
logN…N
Динамическое программирование Итак, основная идея динамического программирования – запоминание результатов решения повторяющихся подзадач, возникающих при поиске методом полного рекурсивного перебора с получением задач меньшей размерности. Рассмотрим, как это выглядит на сравнительно простой задаче. Требуется в двух строках найти общую (одинаковую) подпоследовательность максимальной длины. Подпоследовательность получается путем вычеркивания из строки некоторых символов, саму подпоследовательность запоминать не нужно. Основные принципы рекурсивного решения:
- TEXT
рекурсивная функция решает задачу для двух оставшихся частей строк с длинами k1 и k2, возвращая в виде результата максимальную длину найденной подпоследовательности; - TEXT
шаг рекурсии заключается в проверке пары очередных символов и получении аналогичных подзадач меньшей размерности за счет отбрасывания этих символов; - TEXT
если пара очередных символов совпадает, то они оба отбрасываются, а длина подпоследовательности увеличивается на 1. При этом производится рекурсивный вызов с сокращением длин обеих строк v=F(k1-1,k2-1)+1; - TEXT
если пара очередных символов не совпадает, то возникают две подзадачи, в которых одна строка укорачивается, а другая остается неизменной. Из результатов двух рекурсивных вызовов выбирается максимальный и возвращается в неизменном виде, т.к. текущий шаг не удлиняет цепочку совпадений; - TEXT
рекурсивный алгоритм завершается, когда заканчивается хотя бы одна строка, в этом случае функция возвращает 0 совпадений.
Внедрение идеи динамического программирования заключается в запоминании результатов выполнения алгоритма для каждой пары значений оставшихся длин строк k1 и k2, что потребует прямоугольной матрицы результатов с размерностями, соответствующими длинам строк. Однако количество повторных просмотров «хвостов» строки уменьшается по мере роста их длины, поэтому сохранять результаты можно только для длины строки не более N. Для этого потребуется чисто техническая модификация написанной программы:
- TEXT
создать квадратную матрицу размерности N в виде динамического массива указателей на строки, в которой значение -1 будет обозначать отсутствие просчитанного решения, а неотрицательное значение – его наличие; - TEXT
при очередном рекурсивном вызове проверяется наличие в матрице решения для заданной размерности, и, если оно там есть, то оно просто повторно оттуда извлекается; - TEXT
в противном случае выполняется вышеописанный алгоритм и полученное решение запоминается.
//----------------------------------------------------------77-00.cpp
// Динамическое программирование - общая подпоследовательность
int **D,N,s1,s2,cnt=0, cnt2=0;
char A[]="ababaaaababababaaabababaaaaaaa";
char B[]="abbbbabaaabaaabababaaabaabaaaaaabaaababa";
int F(int k1, int k2){ // k1,k2 – длины непросмотренных частей строк
int v=0;
cnt++; // счетчик рекурсивных вызовов
if (k1==0 || k2==0) return 0; // одна из строк кончилась - общая длина =0
if (k1<N && k2<N && D[k1][k2]!=-1){
cnt2++; return D[k1][k2]; // повторный выбор уже найденного решения
} // если пара совпадает - отбросить оба
if (A[s1-k1]==B[s2-k2]) v=F(k1-1,k2-1)+1;
else{ // не совпадает - два варианта отбрасывания
int v1=F(k1,k2-1); // с выбором лучшего
int v2=F(k1-1,k2);
v=(v1>v2 ? v1 : v2);
}
if (k1<N && k2<N) D[k1][k2]=v; // запомнить новое решение
return v;
}void main(){…F(s1=strlen(A),s2=strlen(B));…}
Динамическое программирование. Преобразование строки. Требуется преобразовать исходную строку в заданную, используя минимальное количество операций удаления, добавления и замены очередного символа. Задача имеет естественное рекурсивное решение методом полного перебора. Сам процесс преобразования представляет собой сравнение пар очередных символов из исходной и результирующей строки с выполнением одного из четырех возможных действий, связанных с удалением символа из исходной или результирующей строки, в результате чего размерность подзадачи уменьшается на единицу:
- TEXT
удаление символов из исходной и результирующей строки при их совпадении (взаимное уничтожение); - TEXT
замена символа входной строки на символ выходной (при их несовпадении) с последующим взаимным уничтожением; - TEXT
удаление символа из входной строки; - TEXT
добавление символа результирующей строки в исходную. С учетом их последующего взаимного уничтожения это можно рассматривать как удаление символа из результирующей строки.
Вариант с прямым накоплением результата сохраняет в глобальном массиве последовательность выполняемых операций. Сам накапливаемый результат – количество операций (вставка, удаление, обмен) передается в качестве формального параметра (k), по завершении последовательности рекурсивных вызовов (обе строки пустые) запоминается минимальное значение k и связанная с ним строка s – последовательность операций.
//--------------------------------------------------------------------77-01.cpp
// Преобразование строки - прямое накопление результата
char s[100],min[100]=""; // текущая и оптимальная строка операций
int kmin=-1; // минимальное количество операций
// A,B - указатели на текущие символы строк
// n - номер шага (глубина рекурсии)
// k - накопленное количество операций
// m - счетчик вариантов
void F(char A, char B,int n,int k,int &m){
s[n]=0; m++; // Обе строки закончились
if (A==0 && B==0) { // Проверить очередной вариант на минимум
if (kmin==-1 || k < kmin) strcpy(min,s),kmin=k;
return; } // и завершить рекурсию// Одна из строк закончилась - удалять из противоположной
if (*A==0) { s[n]='+'; F(A,B+1,n+1,k+1,m); return; }
if (*B==0) { s[n]='-'; F(A+1,B,n+1,k+1,m); return; }
// Три варианта решения задачи
if (A==B) // Подзадача 1: Символы одинаковые - взаимное уничтожение
{ s[n]='x'; F(A+1,B+1,n+1,k,m); }else // Не одинаковые - замена
{ s[n]='c'; F(A+1,B+1,n+1,k+1,m); }s[n]='-'; F(A+1,B,n+1,k+1,m); // Подзадача 2: Удалить символ из исходной
s[n]='+'; F(A,B+1,n+1,k+1,m); // Подзадача 3: Добавить символ в исходную
} // (удалить из результирующей)
Для решения задачи методом динамического программирования необходимо для начала реализовать в программе обратное накопление результата. Для этого рекурсивная функция будет возвращать количество операций над символами строки, накопленное в последовательности возвратов из рекурсивных функций.
//----------------------------------------------------------------------77-02.cpp
// Преобразование строки - обратное накопление результата
int F(char A, char B){
int k1,k2,k3; // Результат функции - количество операций
if (A==0 && B==0) return 0; // Завершение рекурсии (первоначальный возврат 0)
if (*A==0) return strlen(B); // Одна из строк закончилась
if (*B==0) return strlen(A); // - удаление из противоположной
if (A==B) // Символы совпадают
k1=F(A+1,B+1); // - взаимное уничтожение (+0 операций)else
k1=F(A+1,B+1)+1; // Иначе - замена (+1 операция)k2=F(A+1,B)+1; // Удаление из исходной (+1 операция)
k3=F(A,B+1)+1; // Вставка в исходную (+1 операция)
if (k2<k1) k1=k2; // Выбор минимального числа
if (k3<k1) k1=k3; // операций, полученное от трех подзадач
return k1; }
Для накопления последовательности действий в качестве результата следует возвращать объект (структурированный тип), в котором хранится как количество операций, так и их последовательность.
//----------------------------------------------------------------------77-03.cpp
// Преобразование строки - обратное накопление результата
// в структурированной переменной (объекте)
struct REZ{ // Структурированный тип - результат
int k; // Количество операций
char s[100]; // Последовательность операций
};REZ F(char A, char B,int n,int &m){
REZ V1,V2,V3;
m++;
if (A==0 && B==0) { V1.k=0; V1.s[n]=0; return V1; }
if (*A==0)
{ V1=F(A,B+1,n+1,m); V1.s[n]='+'; V1.k++; return V1; }if (*B==0)
{ V1=F(A+1,B,n+1,m); V1.s[n]='-'; V1.k++; return V1; }if (A==B)
{ V1=F(A+1,B+1,n+1,m); V1.s[n]='x'; }else
{ V1=F(A+1,B+1,n+1,m); V1.s[n]='c'; V1.k++; }V2=F(A+1,B,n+1,m); V2.s[n]='-'; V2.k++;
V3=F(A,B+1,n+1,m); V3.s[n]='+'; V3.k++;
if (V2.k<V1.k) V1=V2;
if (V3.k<V1.k) V1=V3;
return V1; }
Поскольку в каждой последующей подзадаче мы имеем укорочение одной или обеих строк, а содержимое этих строк не меняется, то очевидно, что подзадачи с одним и тем же сочетанием «остатков» строк будут повторяться при проверке различных вариантов вставки, удаления и замены предыдущих символов. Результаты решения подзадач размерности не выше N можно сохранить в квадратной матрице, рабочими индексами в которой будут текущие размерности «остатков» исходной и результирующей строки. В обоих вариантах программы вносятся незначительные изменения:
- TEXT
рекурсивная функция получает два дополнительных параметра s1,s2 – размерности строк, дабы не перевычислять их в каждом вызове; - TEXT
в начале рекурсивного вызова проверяется наличие в матрице уже сохраненного решения подзадачи текущей размерности (s1,s2), и если оно обнаружено, то повторно возвращается; - TEXT
перед завершением рекурсивной функции текущее решение помещается в матрицу, если размерность задачи не превышает размерности матрицы.
//-----------------------------------------------------------------------77-04.cpp
// Преобразование строки - динамическое программирование
#define N 4
int D[N][N];
int F(char A, char B,int s1, int s2){
int k1,k2,k3;
// Есть уже сохраненное решение для строк размерности s1,s2
if (s1<N && s2<N && D[s1][s2]!=-1) return D[s1][s2];
… предыдущий алгоритм (87-02.cpp)
// Найдено решение для строк размерности s1,s2 - сохранить
if (s1<N && s2<N) D[s1][s2]=k1;
return k1;
}//----------------------------------------------------------------------77-05.cpp
// Преобразование строки - обратное накопление результата
// в структурированном типе (объекте). Динамическое программирование
struct REZ{ // Структурированный тип - результат
int k; // Количество операиций
char s[100]; // Последовательность операций
REZ(){ k=-1; } // Конструктор – подзадач не решалась
};#define N 6 // Массив промежуточных результатов
REZ D[N][N]; // для остатков строк размерности i,j
REZ F(char A, char B,int n, int &m, int s1, int s2){
REZ V1,V2,V3;
// Есть уже сохраненное решение для строк размерности s1,s2
if (s1<N && s2<N && D[s1][s2].k!=-1) return D[s1][s2];
… предыдущий алгоритм (77-04.cpp)
// Найдено решение для строк размерности s1,s2 - сохранить
if (s1<N && s2<N) D[s1][s2]=V1;
return V1; }Использование дополнительной памяти Динамическое программирование сохраняет результаты повторяющихся шагов в памяти. В этом смысле оно отражает общий принцип повышения эффективности алгоритмов (не обязательно рекурсивных) за счет использования дополнительной памяти. Цитата из военной стратегии – проигрываем в пространстве, выигрываем во времени – здесь совершенно к месту. Еще один принцип: для адресации данных в такой памяти хорошо использовать в качестве индексов (адресов расположения) сами значения данных или их частей (распределение, размещение).
В качестве примера рассмотрим лексикографическую сортировку. Ее название следует из того, что при сортировке строк для распределения используются значения отдельных символов слова. Хотя можно использовать и любые другие части сортируемых элементов данных, например, цифры числа (разряды).
Идея заключается в том, что исходные данные распределяются по последовательностям (карманам) в соответствии со значением младшей цифры. Она играет роль индекса выходной последовательности. Затем данные сливаются. Далее распределение и слияние повторяются по следующим цифрам вплоть до старшей. В доказательство правильности такой сортировки можно привести такой факт, что инвариантом цикла распределения слияния является упорядоченность по i разрядам. Действительно, если полученная на i-1 шаге последовательность упорядочена по младшим i-1 разрядам (это значит, что любые два соседних числа расположены в порядке возрастания, если рассматривать только младшие i-1 разрядов). Например, при i=3 - 1311,711,312,613,2215,223,333,133. При распределении переписывание идет линейно (т.е. более «поздние» значения не могут следовать вперед более «ранних», т.е. в каждом кармане свойство частичной упорядоченности сохраняется. Слияние же добавляет эту упорядоченность по следующей цифре.
Эффективность такой сортировки легко подсчитать. Она зависит от разрядности сортируемых данных (m), количество перемещений данных равно m2N. За линейную зависимость от N (напомним, что трудоемкость сортировок лежит в диапазоне от Nlog2N до N2 ) приходится платить дополнительной памятью, ее объем равен kN, где k – количество возможных значений символа (цифры). Кстати, в сравнении с лучшим случаем Nlog2N лексикографическая сортировка имеет преимущества при m << log2N.
//----------------------------------------------77-06
// Лексикографическая сортировка массива. Разряд - десятичная цифра
// Определение кол-ва цифр в чиcле
int dig_len(int dig,int k){
int i;
for( i=0;(dig/=k)!=0;i++);
return i+1;}// Выделение цифры на позиции num
int get_dig(int v,int num,int k){
while(num--!=0) v/=k;
return v%k;}int cnt=0;
void sort(int A[], int n, int k){
for (int i=0,max_len=0;i<n;i++){ // определение максимальной разрядности
int l=dig_len(A[i],k);
if (l>max_len) max_len=l;
}int *B=new int[k],*I=new int[k]; // создание "карманов" - ДМУ
for (i=0;i<k; i++) B[i]=new int[n];
for(int raz=0;raz < max_len; raz++)
{
int i,j,m;
for (m=0,i=0;i<k;i++) I[i]=0; // Обнуление счетчиков
for(i=0;i<n;i++)
{
cnt++;
int v=get_dig(A[i],raz,k); // Распределение по карманам
B[v][I[v]++]=A[i]; // по очередному разряду
}
for (i=0;i<k;i++)
for (j=0;j<I[i];j++,cnt++,m++)
A[m]=B[i][j]; // Слияние карманов
}}Тем не менее, при лексикографической сортировке можно обойтись и без дополнительной памяти (по отношению к исходной структуре данных), если воспользоваться списками. Общая размерность «карманов» при использовании массивов равна k*N, поскольку заранее неизвестно, как разместятся элементы. При использовании списков «карманы» не требуют дополнительной памяти, поскольку представляют собой те же самые элементы, но связанные в другие последовательности. Исходный список и списки – «карманы» можно реализовать в виде односвязных списков с указателями на первый и на последний элементы. Это позволить легко извлекать, добавлять данные и склеивать списки.
//-------------------------------------------------------------77-07
// Лексикографическая сортировка списка
struct elem { // Элемент списка
int v;
elem *next;
elem(int v0){ v=v0; next=NULL; }
};struct queue { // Заголовок списка содержит
elem *fst,*lst; // два указателя на начало и конец
queue(){ fst=lst=NULL; }
};void sort(queue &Q, int sz){ // Q – заголовок списка, sz – размерность цифры
elem *q;
int max_len=0,l;
queue *A=new queue[sz]; // Очереди - карманы по значениям цифр
for (q=Q.fst;q!=NULL;q=q->next)
if ((l=dig_len(q->v,sz))>max_len) max_len=l;for(int raz=0;raz < max_len; raz++){ // По всем цифрам, начиная с младшей
while(Q.fst!=NULL){ // Читать входной список
q=Q.fst; Q.fst=q->next; // и разбрасывать по "карманам"
if (Q.fst==NULL) Q.lst=NULL; // в соответствии с очередной цифрой
int m=get_dig(q->v,raz,sz);
q->next=NULL;
if (A[m].fst==NULL) A[m].fst=A[m].lst=q;
else { A[m].lst->next=q; A[m].lst=q;}
}
for (int i=0;i<sz;i++){ // Склеить списки в карманах
if (A[i].fst==NULL) continue;
if (Q.fst==NULL){ // Выходная пустая -
Q.fst=A[i].fst; // копировать начало и конец очереди
Q.lst=A[i].lst;}
else{
Q.lst->next=A[i].fst; // не пустая - присоединить к концу
Q.lst=A[i].lst; }
A[i].fst=A[i].lst=NULL; // Очистить карман
}}}С помощью дополнительной памяти можно кардинально улучшить качество алгоритма. Зададимся вопросом: «Можно ли упорядочить данные за один просмотр массива (цикл)». До сих пор нам требовался либо вложенный (двойной) цикл, либо цикл в сочетании с рекурсией. В 4.6. мы рассматривали одну из самых неэффективных сортировок – сортировку подсчетом. Применим эту же самую идею – количество элементов, меньших данного, определяет его местоположение в выходном массиве. Только теперь будем накапливать все счетчики одновременно. Для этого заведем массив счетчиков, размерность которого равна диапазону изменения сортируемых данных. В первом варианте элемент массива счетчиков cnt[i] будет содержать число повторений значения i. Затем каждое значение i последовательно копируется в выходной массив столько раз, сколько оно накопилось в счетчике. Во втором варианте к каждому счетчику добавляется сумма предыдущих, и мы получаем абсолютно ту же реализацию, как в сортировке подсчетом: счетчик cnt[i] содержит очередную позицию значения i в выходном массиве. Трудоемкость с учетом диапазона значений D в обоих случаях равна T=2D+2N. Сортировка так и называется – распределяющий подсчет.
//-------------------------------------------------------------------------77-08
// Распределяющий подсчет - сортировка за один цикл
void sort(int A[], int n){
int i,j,max;
for (i=0,max=0; i<n; i++) if (A[i]>max) max=A[i];
int *cnt=new int[max+2]; // массив счетчиков по всему
int *out=new int[n]; // диапазону значений
for (i=0; i<=max+1; i++) cnt[i]=0;
// вариант 1 -------------------------------------------------------
// for (i=0; i<n; i++) cnt[A[i]]++; // накопление счетчиков значений
// for (i=0,j=0; i<=max; i++)
// while(cnt[i]--!=0) out[j++]=i; // копирование каждого значения
// вариант 2 -------------------------------------------------------
for (i=0; i<n; i++) cnt[A[i]+1]++; // накопление счетчиков значений
for (i=1; i<=max;i++) // добавление к каждому счетчику
cnt[i]+=cnt[i-1]; // суммы предыдущих
for (i=0;i<n;i++) // перенос в выходную позицию
out[cnt[A[i]]++]=A[i]; // в соответствии со счетчиком предыдущих
//------------------------------------------------------------------
for (i=0; i<n; i++) A[i]=out[i]; // Возвратить данные
delete cnt;
delete out;}
Резюме: чтобы превратить самую плохую сортировку в самую хорошую нужна всего лишь неограниченная память.
