Интеллектуальные информационные системы. Задача о ходе коня

Август 22, 2022

Главная
Информатика
Интеллектуальные информационные системы. Задача о ходе коня

Содержание

2. Заданное выражение Реализовать алгоритм решения задачи о поиске последовательности перемещений коня на шахматной доске размера m
3. Алгоритм Заданное выражение является разновидностью задачи о ходе коня (Knight's tour), однако мы не связаны с
4. Алгоритм Мы можем выстроить алгоритм, основанный на обходе в глубину с некоторыми оптимизациями К примеру, не
5. Алгоритм При очередном выборе следующей клетки мы базируемся на информации о уже посещенных из возможных
6. Алгоритм Поскольку фигура коня может передвигаться по определенному правилу, будем вычислять доступные шаги посредством следующего списка
7. Реализация Для начала определим несколько вспомогательных функций Первой идет numlist, возвращающая список целых числе от 1
8. Реализация Функция concat. Принимает на вход список l и возвращает соединение всех его внутренних элементов Функция
9. Реализация Наконец начинаем описывать целевую функцию knight, принимающую размер поля в качестве аргументов Имея размеры поля
10. Реализация В локальной области видимости определим несколько контекстно-зависимых функций. Функция is-visited возвращает t если искомая клетка
11. Реализация Функция next-step принимает на вход текущую ветку перемещений Возвращает все не посещенные точки, в которые
12. Реализация Далее идет функция next-branches, возвращающая слияние доступной ветки перемещения с текущей Функция is-branch-full позволяет закончить
13. Реализация Своеобразной точкой входа и последней локальной функцией является функция move. Она проводит рекурсивный проход по
15. Скачать презентацию

Слайд 2

Заданное выражение
Реализовать алгоритм решения задачи о поиске последовательности перемещений коня на

шахматной доске размера m × n (например, 4 × 4 или 4 × 5) из заданной начальной клетки (нижняя левая клетка) в нее же, при этом надо побывать хотя бы по одному разу на всех остальных клетках доски

Слайд 3

Алгоритм
Заданное выражение является разновидностью задачи о ходе коня (Knight's tour), однако

мы не связаны с ограничением один шаг на клетку Простейшее решение нашей задачи сводится к представлению шахматного поля в качестве графа и поиск пути на нем
Так клетки – это вершины, а ребра – возможные пути

Слайд 4

Алгоритм
Мы можем выстроить алгоритм, основанный на обходе в глубину с некоторыми

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

Слайд 5

Алгоритм
При очередном выборе следующей клетки мы базируемся на информации о уже

посещенных из возможных

Слайд 6

Алгоритм
Поскольку фигура коня может передвигаться по определенному правилу, будем вычислять доступные

шаги посредством следующего списка разности:
((2 1) (1 2) (-1 2) (-2 1) (-2 -1) (-1 -2) (1 -2) (2 -1))
Координаты клеток в свою очередь будем хранить в формате (x y)

Слайд 7

Реализация
Для начала определим несколько вспомогательных функций
Первой идет numlist, возвращающая список целых

числе от 1 до size
Далее по списку функция is-contains, определяющая является ли x элементом верхнего уровня списка l

Слайд 8

Реализация
Функция concat. Принимает на вход список l и возвращает соединение всех

его внутренних элементов
Функция foldr. Поведение соответствует аналогичной функции в я.п. Haskell. Рекурсивна со строки 5

Слайд 9

Реализация
Наконец начинаем описывать целевую функцию knight, принимающую размер поля в качестве

аргументов
Имея размеры поля мы можем инициализировать список board, содержащий координаты всех клеток на поле. В этом нам поможет ранее описанная функция numlist

Слайд 10

Реализация
В локальной области видимости определим несколько контекстно-зависимых функций.
Функция is-visited возвращает t

если искомая клетка x уже посещена из p

Слайд 11

Реализация
Функция next-step принимает на вход текущую ветку перемещений
Возвращает все не посещенные

точки, в которые возможно переместиться

Слайд 12

Реализация
Далее идет функция next-branches, возвращающая слияние доступной ветки перемещения с текущей
Функция

is-branch-full позволяет закончить обход шахматной доски, если все клетки из board находятся в текущей ветке cb

Слайд 13

Реализация
Своеобразной точкой входа и последней локальной функцией является функция move. Она

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

Интеллектуальные информационные системы. Задача о ходе коня

Содержание

Заданное выражениеРеализовать алгоритм решения задачи о поиске последовательности перемещений коня на

АлгоритмЗаданное выражение является разновидностью задачи о ходе коня (Knight's tour), однако

АлгоритмМы можем выстроить алгоритм, основанный на обходе в глубину с некоторыми

АлгоритмПри очередном выборе следующей клетки мы базируемся на информации о уже

АлгоритмПоскольку фигура коня может передвигаться по определенному правилу, будем вычислять доступные

РеализацияДля начала определим несколько вспомогательных функцийПервой идет numlist, возвращающая список целых

РеализацияФункция concat. Принимает на вход список l и возвращает соединение всех

РеализацияНаконец начинаем описывать целевую функцию knight, принимающую размер поля в качестве

РеализацияВ локальной области видимости определим несколько контекстно-зависимых функций.Функция is-visited возвращает t

РеализацияФункция next-step принимает на вход текущую ветку перемещенийВозвращает все не посещенные

РеализацияДалее идет функция next-branches, возвращающая слияние доступной ветки перемещения с текущейФункция

РеализацияСвоеобразной точкой входа и последней локальной функцией является функция move. Она

Похожие презентации