Тур шахмотного коня

Класс алгоритмов, позволяющий решать подобные задачи, в англоязычной литературе называется «backtracking algorithms» («алгоритмы с возвратом»). Такие алгоритмы применяются в тех случаях, когда не подходят более «направленные» методы [3].

Исследуем одну из наиболее известных задач этого класса – задачу о ходе коня [3-5]. Она состоит в том, чтобы найти обход доски размером N на M конем, перемещающимся по правилам шахматной игры. Если такой обход существует, то каждое поле посещается только один раз (выполняется N*M-1 шагов). Проанализируем методы оптимизации и исследуем работу итеративной, рекурсивной и автоматной программ.

Введение……………………………………………………………..3

1.Методы оптимизации……………………………………………...4

2.Определение клеток, обход из которых невозможен………4

3.Выявление заблокированных клеток………………………..5

4.Применение правила Варнсдорфа…………………………....5

5.Использование различных массивов хода коня……………6
2.Итеративная программа…………………………………………..7

3.Полный перебор………………………………………………...7

4.Результаты работы программы с оптимизацией…………..9
3.Рекурсивная программа…………………………………………14
4.Автоматная программа………………………………………….15
Заключение……………………………………………………….17

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