Решения комбинаторной задачи, их анализ и исследование

 

Оглавление

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

Расширенная постановка задачи

Виды выполняемых работ

Анализ задания

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

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

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

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

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

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

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

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

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

Выводы по всей работе в целом

Список использованной литературы

Приложение A

Приложение B

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

Расширенная постановка задачи

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

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

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

-формализация поставленной задачи;

-приспособление общих методов и алгоритмов решения классов задач к решению конкретной задачи;

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

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

-оценка эффективности предложенных в работе алгоритмов;

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

Виды выполняемых работ

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

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

-Формализация поставленной задачи, приспособление и модификация общего алгоритма поиска с возвращением под конкретную задачу, разработка алгоритмов решения задачи;

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

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

Анализ задания

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

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

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

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

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

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

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

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

Введем на доске систему координат такую, что начальные координаты коня будут (1,1) а конечные (n,n). Очевидно, что ходы коня записываются координатами вида (x,y).

Для алгоритма поиска с возвращением, в общем случае предполагается, что решение задачи представляет собой вектор (a1, a2, …) конечной, но неопределённой длины. В нашем случае, этот вектор будет содержать координаты ходов рассматриваемого в данный момент пути коня. Также введем два вектора dx и dy, содержащие возможные 8 ходов с текущей клетки. В связи с тем, что модель имеет древовидную структуру, текущий путь коня лучше записывать в стек.

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

Основными видами ограничений, применимых в данной задаче, как было сказано выше, являются ограничения на глубину исследования дерева поиска и запрет повторения поля в пути (которое реализуется сохранением состояния доски в массиве b).

Ограничение на глубину исследования дерева поиска напрямую и радикально действует на число исследованных вершин и как следствие - на время работы алгоритма. Данное ограничение принято как мера, принятая для уменьшения размеров поиска. Путь коня не длиннее n*n полей, дерево поиска содержит не более 8n*n узлов. Ниже приведена таблица исследования временной сложности алгоритма без введения ограничений:

Таблица 1

Работа алгоритма без ограничений

Размер доски (n)Узлов в дереве перебора (шт)Затраченное время (с)81206540,279717432916,1810395553789892,25

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

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

Таблица 2

Работа алгоритма с ограничением

Размер доски (n)Узлов в дереве перебора (шт)Затраченное время (с)Быстрее, чем без ограничений (раз)8455980,102,65926183685,912,7410138305521311,972,86

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

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

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

Алгоритм 1. Поиск кратчайшего пути рекурсивным методом

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

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

Алгоритм 2 является модификацией итерационного алгоритма поиска с возвращением.

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

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

Алгоритм Монте-Карло для исследования деревьев имеет следующий вид:

Алгоритм 3. Метод Монте-Карло для исследования дерева

Одной из важных частей данной работы является исследование временной сложности алгоритмов. Результаты исследований сведены в нижеприведённой таблице 3.

Таблица 3

Работа алгоритма с ограничением

Метод Монте-КарлоФактическиNЧисло узловПорядок ростаЧисло узловВремя, ч:м:сПорядок роста31-100:00:00-444,0400:00:004,05235,82500:00:005,861416,114000:00:006,17295721,0305900:00:0021,085357018,15056900:00:0018,19318593559,5318689100:00:0759,51017563161355,117585987500:06:3655,11123300786658132,7~ 14:36:00

Из приведённых выше таблиц видно, что при увеличении размера задачи, время поиска увеличивается в некоторое количество раз. Этот факт говорит об экспоненциальном характере алгоритмов. Для интереса приведём тот факт, что по предварительным оценкам время перебора при N=11 будет примерено равно 14,5 часам. Отсюда вытекают следующие соображения: очень важно находить методы сокращения перебора!

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

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

Для реализации данных использовались следующие структуры:

var b:array [1..nmax,1..nmax] of shortint; {содержимое доски },optimal:tStack; {текущий и оптимальный путь },y,n,p:integer; {счетчики цикла и т.п. },found:boolean; {флаг первого и найденного решения}

u:longint; {количество узлов }

асимптотический сложность комбинаторный алгоритм

По той причине, что Pascal не поддерживает массивы неизвестного размера и была необходимость обеспечить ввод пользователем желаемого размера задачи, возникла потребность в предварительном резервировании места под массивы. Было зарезервировано место под доску 15x15, это вполне приемлемо, так как даже при размере доски 12x12 задача решается в среднем за 14,5 часов, то есть за большое время.

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

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

1.Процедура Main

Главная процедура программы. В ней происходит очистка экрана, запрашиваются у пользователя размеры задачи, происходит инициализация всех массивов и переменных начальными значениями. Конь устанавливается на поле (1,1), вызываются процедуры генерации препятствий, решения и вывода результата.

.Процедура In Stack(x,y)

Данная процедура помещает в стек ходов (Stack) ход с координатами (x,y), увеличивая при этом его размер(Stack.hodov) на единицу.

.Процедура Out Stack

Данная процедура извлекает из стека ходов (Stack) последний ход (лежащий на вершине стека), уменьшая при этом его размер(Stack.hodov) на единицу.

.Функция In Doska (x,y)

Данная функция определяет принадлежит ли поле (x,y) доске.

.Процедура Choose

Осуществляется проверка оптимальности полученного решения - не является ли оно оптимальнее ранее найденного оптимального решения.

.Процедура Back Tracking (x,y)

Головная рекурсивная процедура - перебор узлов дерева, передается текущая позиция коня.

.Процедура Print Optimal Way.

Производит вывод результата в удобочитаемой форме.

.Процедура Randomly Generate P.

Заполняет случайно выбранные поля (половину от всех полей доски) препятствиями.

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

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

Программа была реализована на языке высокого уровня Borland Pascal 7.0. Размеры поставленной задачи позволяют реализовать её в виде одного главного модуля.

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

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

Приведём пример работы программы:

Входные данные: n=8

Выходные данные:

количество ходов: 7

символическое изображение

. # . # # # .

# # # . # . . .

# 2 . # . # . .

. . . 3 . # # .

. # . # # . # #

# . 4 # # # # #

# # # # . 6 # .

. # . 5 . # # 7

число узлов 615

Выводы по всей работе в целом

В данной курсовой работе в соответствии с заданием были разработаны и тщательно исследованы алгоритмы решения поставленной комбинаторной задачи. Прежде всего, это рекурсивные алгоритмы поиска с возвращением. Подводя итоги проделанной работе, хочется отметить особую важность методов сокращения перебора, которые, вообще говоря, в комбинаторных задачах имеют весомую роль. От разработчика алгоритмов по сокращению перебора требуется большая изобретательность, умение видеть пространственно. Во время написания программ автор работы не стремился к разработке «красивых» интерфейсов, т. к. по мнению автора задачи по перебору решаются внутри других больших программах, которые имеют свой интерфейс. Основное внимание уделялось разработке и отладке алгоритмов программы. Это было вызвано тем, что при постановке задачи был сделан акцент не на сам факт решения поставленной задачи, а на исследование и разработку алгоритмов. О результатах исследований говорилось в пунктах 1.2 и 2 данной пояснительной записки, подведём небольшие итоги: ввод ограничения на перестановку пары ячеек переставленных на предыдущем шаге позволило сократить время перебора более чем в два раза, тем не менее алгоритм всё равно остаётся асимптотически сложным (O(cn)). Для примера повторюсь, что для решения задачи размером (10*10) необходимо затратить 6 минут времени, а для решения задачи размером (11*11) по приблизительным оценкам необходимо около 14,5 часов. В пункте 1.2 данной работы приведена формула диапазона, которому принадлежит количество вершин дерева поиска, в зависимости от размеров задачи.

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

Приложение A

В данном приложении приводится листинг программы с комментариями по решению поставленной задачи рекурсивным методом

{$M 65520,0,655360}nmax=15; {максимально возможный размер доски }

type mas=array [1..8] of shortint; {тип массива на 8

однобайтовыхэлементов}=record {тип записи на координату хода },y:integer; {однобайтовые координаты x и y }

end;=record {тип стека }:array [1..nmax*nmax] of tHod;{текущий путь c максимальной

длиной n*n}

hodov:integer; {количество элементов в стеке };dx:mas=(2,1,-1,-2,-2,-1,1,2); {возможные 8 ходов, коодрдинаты x }:mas=(1,2,2,1,-1,-2,-2,-1); {возможные 8 ходов, коодрдинаты y }

var b:array [1..nmax,1..nmax] of shortint;{содержимое доски },optimal:tStack; {текущий и оптимальный путь },y,n,p:integer; {счетчики цикла и т.п. },found:boolean; {флаг первого и найденного решения }

u:longint; {количество узлов }

{записать в стек ход}

procedure InStack(x,y:integer);stack do begin(hodov);[hodov].x:=x;[hodov].y:=y;

end;;

{удалить ход из стека}

procedure OutStack;Stack do dec(hodov);;

{координата принадлежит доске?}InDoska(x,y:integer):boolean;:=(x>=1) and (x<=n) and (y>=1) and (y<=n);;

{выбор оптимального пути}Choose;:=true;first then begin:=stack;:=false;if optimal.hodov>stack.hodov then optimal:=stack;;

{головная рекурсивная процедура}BackTracking(x,y:integer);i:integer;(stack.hodov>=optimal.hodov) and found then exit;(x=n) and (y=n) then Choosefor i:=1 to 8 do if (InDoska(x+dx[i],y+dy[i])) and

(b[x+dx[i],y+dy[i]]=0) then begin:=u+1;[x+dx[i],y+dy[i]]:=1;(x+dx[i],y+dy[i]);(x+dx[i],y+dy[i]);;[x+dx[i],y+dy[i]]:=0;

end;;

{наглядное изображение оптимального пути}

procedure PrintOptimalWay;x,y:integer;

ch:char;

writeln('символическое изображение');

if found then with optimal do for x:=1 to hodov do [way[x].x,way[x].y]:=x+1;y:=1 to n do beginx:=1 to n do if b[x,y]=0 then write('. ')if b[x,y]=-1 then write('# ')write(b[x,y],' ');

writeln;;;

{случайная расстановка препятствий}

procedure RandomlyGenerateP;i,x,y:integer;;i:=1 to p do begin:=random(n)+1;:=random(n)+1;(b[x,y]=0) and ((x<>n) or (y<>n));

b[x,y]:=-1;;;

{главная процедура}

procedure Main;:=0;;('введите n ');(n);:=n*n div 2;:=true;:=false;y:=1 to n dox:=1 to n do[x,y]:=0;[1,1]:=1;;(1,1);;not found then writeln('пути не существует');

writeln('число узлов ',u);

end;;

Приложение Б

Решение поставленной задачи с использованием итерационного алгоритма

const nmax=15;tmove=record,y:integer;;=record:array [1..nmax*nmax] of tmove;:integer;;=array [1..8] of integer;dx:mas=(1,2,2,1,-1,-2,-2,-1);:mas=(2,1,-1,-2,-2,-1,1,2);b:array [1..nmax,1..nmax] of integer;,j,n:integer;:tstack;,cy:integer;Push(nx,ny:integer);(cway.length);cway do with move[length] do begin:=nx;:=ny;;;Pop;cway.length=0 then halt;(cway.length);;InDoska(x,y:integer):boolean;:=(x>=1) and (y>=1) and (x<=n) and (y<=n);;PrintDoska;i,j:integer;j:=1 to n do begini:=1 to n do write(b[i,j]:5);;;;;DoAvailMove;i:integer;:boolean;:=false;i:=1 to 8 do if (b[cx+dx[i],cy+dy[i]]=0) and

(InDoska(cx+dx[i],cy+dy[i])) then begin:=true;[cx+dx[i],cy+dy[i]]:=b[cx,cy]+1;:=cx+dx[i];:=cy+dy[i];(cx,cy);;;not z then begin;cway do with move[length] do begin:=x;:=y;;;;('n=');(n);j:=1 to n do for i:=1 to n do b[i,j]:=0;[1,1]:=1;:=1;:=1;(cx,cy);(cx=n) and (cy=n) then begin('Оптимальный путь ');cway do for i:=1 to length do with move[i] do writeln(x,' ',y);;;;false;

Оглавление Задание на курсовую работу Расширенная постановка задачи Виды выполняемых работ Анализ задания 1. Формализация задачи .1 Структ

Больше работ по теме: