 |
Разработка алгоритмов решения задачи
|
|
|
|
В данном пункте описаны алгоритмы для решения поставленной задачи. Был применен вышеописанный алгоритм поиска с возвращением и примененными ограничениями.
Алгоритм 1. Поиск кратчайшего пути рекурсивным методом
Этот алгоритм представляет модификацию общего рекурсивного алгоритма поиска с возвращением для решения данной задачи.
Алгоритм 2. Итерационный алгоритм поиска с возвращением.
Алгоритм 2 является модификацией итерационного алгоритма поиска с возвращением.
Оценка асимптотической временной сложности алгоритма (Метод Монте-Карло)
Вычисление по методу Монте-Карло можно использовать для оценки эффективности алгоритма поиска с возвращением путём сравнения его с эталоном, полученным для задачи с меньшей размерностью. В данной работе этот метод будет использован для исследования асимптотической временной сложности решения задачи в зависимости от размеров доски (N).
Алгоритм Монте-Карло для исследования деревьев имеет следующий вид:
Алгоритм 3. Метод Монте-Карло для исследования дерева
Одной из важных частей данной работы является исследование временной сложности алгоритмов. Результаты исследований сведены в нижеприведённой таблице 3.
Таблица 3
Работа алгоритма с ограничением
| Метод Монте-Карло | Фактически | ||||
| N | Число узлов | Порядок роста | Число узлов | Время, ч:м:с | Порядок роста |
| 3 | 1 | - | 1 | 00:00:00 | - |
| 4 | 4 | 4,0 | 4 | 00:00:00 | 4,0 |
| 5 | 23 | 5,8 | 25 | 00:00:00 | 5,8 |
| 6 | 141 | 6,1 | 140 | 00:00:00 | 6,1 |
| 7 | 2957 | 21,0 | 3059 | 00:00:00 | 21,0 |
| 8 | 53570 | 18,1 | 50569 | 00:00:00 | 18,1 |
| 9 | 3185935 | 59,5 | 3186891 | 00:00:07 | 59,5 |
| 10 | 175631613 | 55,1 | 175859875 | 00:06:36 | 55,1 |
| 11 | 23300786658 | 132,7 | ~ 14:36:00 | ||
Из приведённых выше таблиц видно, что при увеличении размера задачи, время поиска увеличивается в некоторое количество раз. Этот факт говорит об экспоненциальном характере алгоритмов. Для интереса приведём тот факт, что по предварительным оценкам время перебора при N=11 будет примерено равно 14,5 часам. Отсюда вытекают следующие соображения: очень важно находить методы сокращения перебора!
|
|
|
Программная реализация алгоритмов
Реализация данных
Для реализации данных использовались следующие структуры:
var b:array [1..nmax,1..nmax] of shortint; {содержимое доски },optimal:tStack; {текущий и оптимальный путь },y,n,p:integer; {счетчики цикла и т.п. },found:boolean; {флаг первого и найденного решения}
u:longint; {количество узлов }
асимптотический сложность комбинаторный алгоритм
По той причине, что Pascal не поддерживает массивы неизвестного размера и была необходимость обеспечить ввод пользователем желаемого размера задачи, возникла потребность в предварительном резервировании места под массивы. Было зарезервировано место под доску 15x15, это вполне приемлемо, так как даже при размере доски 12x12 задача решается в среднем за 14,5 часов, то есть за большое время.
Реализация алгоритмов
Рассмотрим все пункты программной реализации алгоритма. Определимся, что конкретно нам необходимо реализовать и каким образом это будет реализовано:
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.
Заполняет случайно выбранные поля (половину от всех полей доски) препятствиями.
Как оговаривалось выше процедуры и функции для рекурсивного и итерационного варианта алгоритма абсолютно идентичны. Автор работы не видит смысла дублирования в данной работе их описания. Кроме того быстродействие этих алгоритмов не сильно различается. Для описания выбрана программа написана с использованием рекурсивного алгоритма.
|
|
|
