Исследование асимптотической временной сложности решения шахматной задачи; разработка наиболее эффективных алгоритмов и структуры данных; аналитическая и экспериментальная оценка методов сокращения перебора в комбинаторных задачах; программная реализация.
В работе требуется формализовать поставленную задачу, разработать наиболее эффективные алгоритмы и структуры данных для решения поставленной задачи, реализовать алгоритмы в виде программ для ПЭВМ, исследовать и оценить теоретически (аналитически) и экспериментально временную и емкостную сложность алгоритмов. В качестве индивидуального задания на курсовое проектирование была предложена следующая задача: “Дана шахматная доска и шахматный конь, стоящий в углу доски. Требуется найти кратчайший путь (количество ходов и сами ходы) коня в противоположный угол доски, либо установить, что пути не существует. Также требуется исследовать асимптотическую временную сложность решения задачи в зависимости от n”. Для данной задачи наиболее эффективным будет рассматривать доску как дерево с вершиной в углу, где стоит конь; причем каждая ветвь дерева является корректным путем коня по доске, не содержащим одинаковых полей (в противном случае путь коня не был бы минимальным, так как он содержал бы петлю и его можно было бы сократить).Введем на доске систему координат такую, что начальные координаты коня будут (1,1) а конечные (n,n). Для алгоритма поиска с возвращением, в общем случае предполагается, что решение задачи представляет собой вектор (a1, a2, …) конечной, но неопределенной длины.Основными видами ограничений, применимых в данной задаче, как было сказано выше, являются ограничения на глубину исследования дерева поиска и запрет повторения поля в пути (которое реализуется сохранением состояния доски в массиве b). Ограничение на глубину исследования дерева поиска напрямую и радикально действует на число исследованных вершин и как следствие - на время работы алгоритма. Данное ограничение принято как мера, принятая для уменьшения размеров поиска. Из таблицы видно, насколько сильно чувствителен алгоритм к увеличению размеров задачи, поэтому при решении задач комбинаторики необходимо уделять большое внимание, усовершенствованиям и нахождениям способов сокращения перебора.В данном пункте описаны алгоритмы для решения поставленной задачи. Этот алгоритм представляет модификацию общего рекурсивного алгоритма поиска с возвращением для решения данной задачи. Вычисление по методу Монте-Карло можно использовать для оценки эффективности алгоритма поиска с возвращением путем сравнения его с эталоном, полученным для задачи с меньшей размерностью. В данной работе этот метод будет использован для исследования асимптотической временной сложности решения задачи в зависимости от размеров доски (N). Алгоритм Монте-Карло для исследования деревьев имеет следующий вид: Алгоритм 3.Для реализации данных использовались следующие структуры: var b:array [1..nmax,1..nmax] of shortint; {содержимое доски } stack,optimal:TSTACK; {текущий и оптимальный путь } x,y,n,p:integer; {счетчики цикла и т.п.В ней происходит очистка экрана, запрашиваются у пользователя размеры задачи, происходит инициализация всех массивов и переменных начальными значениями. Конь устанавливается на поле (1,1), вызываются процедуры генерации препятствий, решения и вывода результата. Данная процедура помещает в стек ходов (Stack) ход с координатами (x,y), увеличивая при этом его размер(Stack.hodov) на единицу. Данная процедура извлекает из стека ходов (Stack) последний ход (лежащий на вершине стека), уменьшая при этом его размер(Stack.hodov) на единицу. Как оговаривалось выше процедуры и функции для рекурсивного и итерационного варианта алгоритма абсолютно идентичны.
План
Оглавление
Задание на курсовую работу
Расширенная постановка задачи
Виды выполняемых работ
Анализ задания
1. Формализация задачи
1.1 Структуры данных для представления объектов задачи
1.2 Анализ ограничений и усовершенствований. Аналитические и /или экспериментальные оценки
1.3 Разработка алгоритмов решения задачи
2. Оценка асимптотической временной сложности алгоритма
3. Программная реализация алгоритмов
3.1 Реализация данных
3.2 Реализация алгоритмов
3.3 Исследование способов программирования
Выводы по всей работе в целом
Список использованной литературы
Приложение A Приложение B
Задание на курсовую работу
Расширенная постановка задачи
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
