 |
Анализ ограничений и усовершенствований. Аналитические и /или экспериментальные оценки
|
|
|
|
Оглавление
Задание на курсовую работу
Расширенная постановка задачи
Виды выполняемых работ
Анализ задания
1. Формализация задачи
Структуры данных для представления объектов задачи
Анализ ограничений и усовершенствований. Аналитические и /или экспериментальные оценки
Разработка алгоритмов решения задачи
2. Оценка асимптотической временной сложности алгоритма
3. Программная реализация алгоритмов
Реализация данных
Реализация алгоритмов
Исследование способов программирования
Выводы по всей работе в целом
Список использованной литературы
Приложение A
Приложение B
Задание на курсовую работу
Расширенная постановка задачи
В работе требуется формализовать поставленную задачу, разработать наиболее эффективные алгоритмы и структуры данных для решения поставленной задачи, реализовать алгоритмы в виде программ для ПЭВМ, исследовать и оценить теоретически (аналитически) и экспериментально временную и емкостную сложность алгоритмов.
В качестве индивидуального задания на курсовое проектирование была предложена следующая задача: “Дана шахматная доска и шахматный конь, стоящий в углу доски. Некоторые поля (примерно половина) не пригодны для передвижения, то есть помещать коня на них нельзя. Требуется найти кратчайший путь (количество ходов и сами ходы) коня в противоположный угол доски, либо установить, что пути не существует. Также требуется исследовать асимптотическую временную сложность решения задачи в зависимости от n”.
Выполнение курсовой работы требует:
- формализация поставленной задачи;
- приспособление общих методов и алгоритмов решения классов задач к решению конкретной задачи;
|
|
|
- проведение сравнительной оценки различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов их обработки;
- исследование и оценка аналитически и экспериментально методов сокращения перебора в комбинаторных задачах;
- оценка эффективности предложенных в работе алгоритмов;
- экспериментальное исследование различных способов программной реализации алгоритмов.
Виды выполняемых работ
В ходе решения задач курсовой работы должны быть выполнены следующие виды работ:
- Анализ поставленной задачи, выводы о методах решения и путях повышения эффективности вычислений;
- Формализация поставленной задачи, приспособление и модификация общего алгоритма поиска с возвращением под конкретную задачу, разработка алгоритмов решения задачи;
- Оценка асимптотической временной сложности алгоритмов;
- Программная реализация алгоритмов.
Анализ задания
Выводы о методах решения и путях повышения эффективности вычислений:
Итак, рассмотрим подробнее индивидуальное задание и попытаемся найти и проанализировать способы решения поставленной задачи.
Для данной задачи наиболее эффективным будет рассматривать доску как дерево с вершиной в углу, где стоит конь; причем каждая ветвь дерева является корректным путем коня по доске, не содержащим одинаковых полей (в противном случае путь коня не был бы минимальным, так как он содержал бы петлю и его можно было бы сократить). Необходимо найти такую ветвь дерева, которая содержала бы узел противоположного угла доски, и число узлов от вершины до этого узла было бы минимальным.
Для перебора дерева такого вида можно использовать алгоритм бэктрекинга (перебора с возвратом), причем по ветви дерева следует идти либо до достижения узла противоположного угла доски, при этом путь проверяется на оптимальность и происходит возврат в родительскую вершину узла, либо до достижения листа дерева (то есть узла, не содержащего потомков) при этом происходит просто возврат в родительскую вершину узла. Когда произойдет возврат в вершину дерева, перебор будет закончен.
|
|
|
Из постановки задачи о том, что надо найти кратчайший путь легко увидеть следующее оптимизирующее соображение: если найден кратчайший путь длины L, то перебирать дерево глубже уровня L узлов не имеет смысла.
В связи с тем, что выбранная модель имеет древовидную структуру, наиболее целесообразным будет использование рекурсивного алгоритма.
1. Формализация задачи
Структуры данных для представления объектов задачи
Введем на доске систему координат такую, что начальные координаты коня будут (1,1) а конечные (n,n). Очевидно, что ходы коня записываются координатами вида (x,y).
Для алгоритма поиска с возвращением, в общем случае предполагается, что решение задачи представляет собой вектор (a1, a2, …) конечной, но неопределённой длины. В нашем случае, этот вектор будет содержать координаты ходов рассматриваемого в данный момент пути коня. Также введем два вектора dx и dy, содержащие возможные 8 ходов с текущей клетки. В связи с тем, что модель имеет древовидную структуру, текущий путь коня лучше записывать в стек.
Анализ ограничений и усовершенствований. Аналитические и /или экспериментальные оценки
Основными видами ограничений, применимых в данной задаче, как было сказано выше, являются ограничения на глубину исследования дерева поиска и запрет повторения поля в пути (которое реализуется сохранением состояния доски в массиве b).
Ограничение на глубину исследования дерева поиска напрямую и радикально действует на число исследованных вершин и как следствие - на время работы алгоритма. Данное ограничение принято как мера, принятая для уменьшения размеров поиска. Путь коня не длиннее n*n полей, дерево поиска содержит не более 8n*n узлов. Ниже приведена таблица исследования временной сложности алгоритма без введения ограничений:
Таблица 1
Работа алгоритма без ограничений
| Размер доски (n) | Узлов в дереве перебора (шт) | Затраченное время (с) |
| 8 | 120654 | 0,27 |
| 9 | 7174329 | 16,18 |
| 10 | 395553789 | 892,25 |
|
|
|
Из таблицы видно, насколько сильно чувствителен алгоритм к увеличению размеров задачи, поэтому при решении задач комбинаторики необходимо уделять большое внимание, усовершенствованиям и нахождениям способов сокращения перебора.
В нашем случае, как оговаривалось выше, наиболее очевиден следующий подход к сокращению перебора: Приведём результаты ввода в действие этого ограничения (Табл. 2):
Таблица 2
Работа алгоритма с ограничением
| Размер доски (n) | Узлов в дереве перебора (шт) | Затраченное время (с) | Быстрее, чем без ограничений (раз) |
| 8 | 45598 | 0,10 | 2,65 |
| 9 | 2618368 | 5,91 | 2,74 |
| 10 | 138305521 | 311,97 | 2,86 |
Как видно из таблицы 2, по сравнению с результатами, приведёнными в таблице 1, выше оговорённый способ сокращения перебора уменьшил время перебора почти в три раза.
|
|
|
