Оценка асимптотической временной сложности алгоритма поиска с возвращением

Оценка асимптотической временной сложности алгоритма поиска с возвращением

Задание на курсовую работу

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

В качестве задачи на курсовую работу была предложена следующая комбинаторная задача:

Задаются арифметические операции, в которых цифры заменены буквами. В данной операции одна и та же буква всегда заменяет одну и ту же цифру, разные буквы представляют разные цифры. Число разрядов исходных чисел (не результат операции) - не более N. Восстановить все возможные значения букв и операций.

Исследовать асимптотическую временную сложность решения задачи в зависимости от N.

Пример: SEND MORE MONEY соответствует 9567+1085=10652.

При выполнении курсовой работы требуется:

·        Формализовать поставленную задачу (перейти от словесной неформальной постановки к математической формулировке);

·        Приспособить общие методы и алгоритмы решения к решению конкретной задачи;

·        Провести сравнительную оценку различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов обработки;

·        Исследовать и оценить теоретические и экспериментальные методы сокращения перебора в комбинаторных задачах;

·        Оценить аналитически и экспериментально эффективность предложенных в работе алгоритмов (временную и емкостную сложности);

·        Программно реализовать разработанные алгоритмы на одном из алгоритмических языков программирования.

·        Экспериментально исследовать различные способы программной реализации алгоритмов.

Анализ задания. Выводы о методах решения и путях повышения эффективности вычислений

математический алгоритм программирование данные

Рассмотрим индивидуальное задание и проанализируем методы решения. Эта задача имеет логическое ограничение на количество различных букв в строке - количество цифр 10. Поэтому, бесконечно расти, эта задача может только в размерности чисел, но здесь ограничение может быть наложено скорее возможностями программных средств, чем алгоритмом реализации.

Сама идея решения данной задачи заключается в том, что мы последовательно проходим введенную строку и заменяем все вхождения одной буквы на выбранную цифру. После расстановки цифр расставляются знаки операции, и проводится проверка (является решением или нет). Знаков операции всего 4: сложение, вычитание, умножение и деление. Знак ‘=’ ставится вместо последнего не буквенного символа. Так как выбор цифр, которые будут подставлены, выбираются последовательно необходимо запретить выбор тех же цифр. Для этого создадим таблицу размером 10×10, и введем следующие обозначения

0-  символ можно выбрать:

1-      символ выбран в этой строчке в настоящее время;

-        символ был использован в этой строчке раньше (в этой строчке использовать этот символ больше нельзя, но в следующих можно);

-        символ выбран в выше стоящей строчке;

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

I.       Формализация задачи

.1 Структуры данных для представления объектов задачи

Основная работа в алгоритме решения данной задачи происходит с исходной строкой и лишь на конечном этапе производится перевод чисел записанных в строке в числовую форму.

Для алгоритма поиска с возвращением обычно решением является вектор(a₁, a₂,…), но в нашем случае таким решением будет строка с полностью замененными буквами и подставленными знаками, которая и выводится на экран, в том случае если она верна.

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

1.2 Анализ ограничений и усовершенствований. Аналитические и/или экспериментальные оценки

Основное ограничение в этой задаче указано в самом задании. Это ограничение связано в однозначном соответствии букв и цифр.

Второе ограничение накладывается на количество знаков, оно влияет на количество пройденных вершин и соответственно на время работы алгоритма. В данной работе это ограничение равно 4. Максимальное число узлов дерева равно 10!. И рассчитывается по формуле:

, где n - число различных букв в строке.

1.3 Разработка алгоритмов решения задачи

В данном пункте описаны алгоритмы для решения поставленной задачи. Сначала приведем сам алгоритм, а потом разберем его.

Алгоритм 1. Итерационный алгоритм поиска с возвращением.

Алгоритм 1 является модификацией общего итерационного алгоритма поиска с возвращением. Суть самого алгоритма описывать не буду, разберу лишь некоторые процедуры.

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

Процедура Copy позволяет избежать выбора уже выбранных ранее цифр.

Эта процедура выполняет подстановку знаков и проверку верна ли строка. Она представляет собой поиск с возвращением и похожа на основной алгоритм. Эти две процедуры были разделены по той причине, что они подставляют символы вместо различных символов. Основной алгоритм подставляет вместо буквенных символов цифры, а процедура Podstan подставляет вместо не буквенных символов знаки операций.

Процедура Vozvrat делает обратный шаг, она возвращает последние замененные символы на место и отмечает обратный шаг в таблице.

II.      Оценка асимптотической временной сложности алгоритма (Метод Монте-Карло)

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

В данной работе этот метод используется для исследования асимптотической временной сложности решения задачи в зависимости от количества различных букв в строке и количества знаков операций.

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

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

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

III. Программная реализация алгоритма

3.1 Реализация данных

При реализации данных использовались следующие структуры:      Byval[11][10] - Таблица хранения уже пройденного путиsstr[27] = "abcdefghijklmnopqrstuvwxyz"; - массив элементов распознаваемых как букваZnak[4][4] - Таблица хранения пройденного пути для операций

char* isch_str - исходная строка с которой проводятся все операции

Так же для удобства работы был создан стек под эту программу

struct stac

{nom;sym;

};

В которую записываются все символы заменяемые в строке.

Следующая подставляемая цифра выбирается следующим образом:

Берется первый элемент, помеченный 0 в данной строке (зависит от Glub) и помечается 1.

3.2 Реализация алгоритмов

Рассмотрим подробнее программную реализацию алгоритма.

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

- не должно быть два подряд идущих не буквенных символов, и всего не буквенных символов не должно быть не более 4.(procedure Proverka и Prover)

Procedure Rabota - основная процедура в которой и происходит основная работа.

Procedure Pystot - процедура просматривающая таблицу Byval и определяющая есть ли еще цифру доступные к вставке.

Procedure Sled - процедура выбирающая еще не использованную цифру.

Procedure NextPo - выбор следующей не заменненой буквы. Проходя по строке и сравнивая каждый символ со строкой sstr первый символ который есть в sstr выбирается на замену.

Procedure Podstano - процедура подставляет знаки и выполняет окончательную проверку строки. Если строка верна то она выводится на экран.

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

3.3 Исследование способов программирования

Программа была реализована на языке высокого уровня Microsoft Visual C++ 6.0 d в виде одного модуля

Размеры исходного файла: 6кбайт

Размеры исполняемого файла: 208 кбайт

Приведу пример работы данной задачи

asd fgh sderg

*184=67528

*028=14392

Выводы по работе

В данной курсовой работе в соответствие с заданием были разработаны и исследованы алгоритмы решения поставленной комбинаторной задачи. Как основа алгоритма решения были взят общий итерационный алгоритм поиска с возвращением. Отличительной чертой задачи предложенной на курсовой проект является то, что она имеет логические ограничения, и поэтому не способна расти до бесконечности, так же в этой задаче не удалось найти способов сокращения перебора, но нужно заметить, что для данной задачи они не очень важны, так как наибольшее время работы программы 2 минуты (при изменение разрядности это время будет не значительно увеличиваться). Но время работы порядка 1 часа получить не получится.

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

Приложение

#include <iostream.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#include <Windows.h>

#include <conio.h>isch_str[30];sstr[27] = "abcdefghijklmnopqrstuvwxyz";chisla[10]= {1,1,1,1,1,1,1,1,1,1};Chisl[11] = "1234567890";cfstr[27];Znaki[5]="+-*/";     Byval[11][10]= {{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0},

{0,0,0,0,0,0,0,0,0,0}};Znak[4][4]={{0,0,0,0},

{0,0,0,0},

{0,0,0,0},

{0,0,0,0}

};Ukaz;Zna;Chis;Pustota=0;Prisn=1;okr;Ver=0;start,end;stac

{nom;sym;

};STAC[15];POPS()

{-;(STAC[Ukaz]);

}PUSHS(stac Elm)

{[Ukaz]=Elm;++;(0);

}Proverka(char* str)

{(cfstr,0,27);(int i=0, j = 0; i < (int)strlen(str); i++) ((strchr(sstr,str[i])) && !cfstr[str[i]-97])

{++;[str[i]-97] = 1;

};(int a=0; a<(int)strlen(str);a++)(!(strchr(sstr,str[a]))) Zna++;j;

}Prover(char* str)

{        Pre=0,kod;(int i=0; i<(int)strlen(str)-1;i++)

{=str[i];((!((kod>96)&&(kod<123)))&&(Pre)) return(0);if (!((kod>96)&&(kod<123)))Pre=1;Pre=0;

}(int j=(int)strlen(str)-2;j>=0;j--)      (!strchr(sstr,str[j])) {str[j]='=';return(1);}(0);

}Podstan(char* str, char chr,char chrz)

{(int i=0; i<(int)strlen(str); i++)(str[i]==chr) str[i]=chrz;(0);

}Vozvrat(char* str,int Glub)

{Pr;ch,cho;pos;=POPS();=Pr.sym;=Pr.nom;=str[pos];(int j=pos; j<=(int)strlen(str);j++)        

{if(str[j]==cho) str[j]=ch;}(int i=0; i<10; i++)[Glub][i]=0;

{for (int b=0; b<10; b++)(Byval[Glub-1][b]==1) Byval[Glub-1][b]=2;

}(0);

}Proverca(char* str,int Glub)

{(1);

}NextPo(char* str, int po)

{        for(int i=0; i<(int)strlen(str);i++ )(strchr(sstr,str[i])) return(i);(-1);

}Pystot(char* str, int Glub)

{        (int j=10,a=0; a<10; a++)(Byval[Glub][a]) j--;(j);

}Copy(int Glub, char ch1)

{(Glub==0) Byval[Glub][ch1-48]=1;{for(int i=0;i<=10;i++)((Byval[Glub-1][i]==1)||(Byval[Glub-1][i]==3)) Byval[Glub][i]=3;}(0);

}Sled(int Glub)

}Pys(int zn)

{(int j=4,i=0; i<=4;i++)=Znak[zn][i];(j);

}Vyb(char* str, int p)

{(int i=p+1; i<(int)strlen(str);i++)(!(strchr(Chisl,str[i]))) return(i);(-1);

}V(int zn)

{(int i=0; i<4; i++)(!Znak[zn][i])

{Znak[zn][i]=1;(i){(0):return('+'); break;(1):return('-'); break;(2):return('*'); break;(3):return('/'); break;

}

}(0);

}Voz(char* str)

{        stac pred;=POPS();[pred.nom]=pred.sym;(0);

}PROVERKA(char* str,int zn)

{        int pos=0;ch;dw1=atof(str),dw2;i=0;(zn<Zna) return(0);(pos<(int)strlen(str))

{(isdigit(str[pos])) pos++;=str[pos];+=1;=atoi(str+pos);(ch)

{('='):if (dw1==dw2) cout<<str<<endl; Pustota=1;return(1);('+'):dw1+=dw2; break;('-'):dw1-=dw2; break;('*'):dw1*=dw2; break;('/'):if (!(dw2==0))dw1/=dw2; break;

}

}(0);

}Podstano(char* str, int Glub)

{zn=0,p=0,Pri=1;Per;ch;++;(Chis>Glub)return(0);(zn>=0)

{((Pri)&&(Pys(zn)))

{p=Vyb(str,p);.nom=p;.sym=str[p];(Per);=V(zn);++;(str[p]!='=')

{str[p]=ch;++;(zn==1)

{ for(int a=3;a>=0;a--)(Znak[0][a]==1){ Znak[1][a]=1; ;}}(!(zn==1)) {for(int i=0;i<4;i++)[zn][i]=Znak[zn-1][i];}

}(PROVERKA(str,zn)) Pri=0;

}(zn!=0) Voz(str);(int b=0; b<4;b++)[zn][b]=0;-;=1;=0;

}=0;(0);

}Rabota(char* str)

{        int Nomerchis=0; //Íîìåð ïîñëåäíåãî çàìåííåíîãî ñèìâîëà

memset(chisla,1,10);* isch=str;ch,ch1;                        

int po=0,k=1,Nu=0,Glub=0;            //Ex-ïðèçíàê âûõîäà

stac Per;(Glub>=0)

{((Prisn)&&(Pystot(str,Glub)))

{(po!=-1)

{=str[po];.nom=po;.sym=ch;(Per);=Sled(Glub);(ch1!=0)Podstan(str,ch,ch1);++;(Glub,ch1);(str,Glub);}=NextPo(str,po);

}(str,Glub);-;=1;

}        (0);

}main()

{<<”Введите строку”<< endl;(isch_str,30,stdin);=Proverka(isch_str);(Chis>10) {cout<<”Неправильная строка"<<endl; getch();exit(0);}(!(Prover(isch_str))) {cout<<"Неправильная строка"<<endl; ();exit(0);}=GetTickCount();=2;(isch_str);=GetTickCount();=start;(!Pustota) cout<<"Нет вариантов";<<"Перебор закончен"<<endl;<<"Время "<<end<<endl;<<"Вершин "<<Ver<<endl;<<"Press any key"<< endl;();(0);

}