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

    Федеральное агентство по образованию

    Бийский технологический  институт (филиал)

    государственного  образовательного учреждения

    высшего профессионального  образования

    «Алтайский  государственный  университет имени  И. И. Ползунова»

    (БТИ  АлтГТУ) 
 
 

    Кафедра ИУС 

    Курсовая работа

    по  дисциплине:

    «Основы алгоритмизации и  языки программирования» 
 

    Тема: «Тур шахматного коня» 
 
 
 
 
 
 
 

    г.Бийск  2009 г.

    Содержание: 
 
 

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

1. Методы оптимизации……………………………………………...4
    
0. Определение клеток, обход из которых невозможен………4
    
0. Выявление заблокированных  клеток………………………..5
    
0. Применение  правила Варнсдорфа…………………………....5
    
0. Использование различных массивов хода коня……………6
2. Итеративная программа…………………………………………..7
    
0. Полный  перебор………………………………………………...7
    
0. Результаты  работы программы с оптимизацией…………..9
3. Рекурсивная программа…………………………………………14
4. Автоматная программа………………………………………….15

          Заключение……………………………………………………….17

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

    Введение 

    К одному из наиболее интересных разделов программирования относятся задачи из области искусственного интеллекта, в которых решение ищется методом «проб и ошибок» [1,2]. При этом имеет место перебор при поиске решения, продолжительность которого можно быть сокращена за счет применения тех или иных эвристических правил – методов оптимизации.

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

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

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

    Рассмотрим  следующие методы оптимизации:

• Определение клеток, обход из которых невозможен (оптимизация 1);
• Выявление заблокированных клеток (оптимизация 2);
• Применение правила Варнсдорфа (оптимизация 3);
• Использование различных массивов ходов коня (оптимизация 4).

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

    Если  количество клеток доски нечетно (число  белых и черных клеток отличается на единицу), то обход из некоторых  клеток не существует. Отметим, что  путь коня проходит по клеткам, чередующимся по цвету. Если общее число клеток доски нечетно, то первая и последняя клетка пути, пройденного конем, будут одного и того же цвета. Таким образом, обход будет существовать только тогда, когда он начинается клеткой того цвета, который имеют наибольшее число клеток.

    Выполнение  этого условия проверяется следующей функцией: 

    int solution_impossible ()

    {

         // Если произведение сторон доски нечетно и сумма координат начальной позиции

        // нечетна, то решения не существует.

        return ((size_x*size_y)  % 2 != 0) && ((start_x+start_y)  % 2 != 0); 
 

    Однако  приведенное правило не охватывает всех клеток, для которых обхода не существует. Так, для доски размером 3*7, помимо тех клеток, для которых  выполняется приведенное правило, обход невозможен так же из клетки (2,4).    

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

    Если  прим очередном ходе образуется клетка, куда можно войти, но откуда нельзя выйти, то такой ход недопустим, за исключением предпоследнего в обходе. Данный метод оптимизации позволяет  значительно сократить число  возвратов, в том числе и при совместном использовании с правилом Варнсдорфа.

    Развитие  этого метода является определение  групп заблокированных клеток, связанных  друг с другом, но отрезанных от остальной  части доски. В рассматриваемой  программе определяются группы из двух заблокированных клеток, что значительно уменьшает количество возвратов для небольших досок, а при использовании вместе с правилом Варнсдорфа – и для больших (например, размером 100*100 клеток). 
 

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

    Среди многих эвристических методов [5], используемых для сокращения перебора, правило Варнсдорфа является наиболее простым. В соответствии с ним при обходе доски коня следует каждый раз ставить на то поле, из которого он может сделать наименьшее число ходов по еще не пройденным полям. Если таких полей несколько, то можно выбрать любое из них, что может, однако, завести коня в тупик и потребовать возврата [5]. Отметим, что наилучшим образом правило Варнсдорфа работает для угловых полей. 
 
 
 
 
 

    1.4. Использование различных массивов ходов коня. 

    Ходы  коня могут быть заданы, например, в  виде следующего массива:

    int possible_moves_sh [] [2] = {

    {-1, -2}, {-2, -1}, {-2, 1}, {1, -2},

    {-1, 2}, {2, -1}, {1, 2}, {2, 1}  }; 

    Каждый  его элемент определяет один возможный  ход коня и содержит изменения  его координат на доске при совершении хода. При использовании различных массивов для ходов коня количество возвратов может различаться. В программе применяются пять эвристически выбранных массивов, содержащих возможные ходы коня в различном порядке. Также задается максимальное число возвратов (GOOD_RET), и когда оно будет достигнуто, поиск пути начинается заново с использованием уже другого массива. При поиске обхода с применением последнего массива количество возвратов ограничивается значением MAX_RET. Если при совместном использовании всех предложенных методов оптимизации установить значение GOOD_RET равным единице, то для досок, близких к квадратным, можно строить обходы без единого возврата для всех клеток, из которых существует обход. Обход без единого возврата из каждой клетки не удается получить для «вытянутых» досок (например, 14*3) и для больших досок (например,100*100 клеток). 
 
 
 
 
 
 
 
 
 

    2. Итеративная программа. 

    2.1. Полный перебор. 

    Идея  алгоритма для итеративной программы заключается в следующем:

• На каждом шаге ищется фрагмент пути, начинающийся из текущей клетки и не включающий уже пройденные;
• При совершении хода из массива возможных ходов извлекается очередной элемент, который приводит в незанятую клетку, находящуюся в пределах доски;
• Если ход невозможен, то происходит возврат в предыдущую клетку (отмена хода);
• Поиск пути считается успешным тогда, когда номер текущего хода станет равным количеству клеток на доске. Если из начальной клетки перебраны все возможные ходы, то пути не существует.

    Ниже  приведена структура функции, выполняющей перебор: 

    int possible_moves_sh [] [2] = {

    void find_path ()

    {

         for ( move_num = 1 ; move_num <= max_moves ; ) 

        {

           if( make_move()  )                        // Сделать ход.

             move_num++ ;

           else                                               //Ход невозможен.

               if (move_num > 1 )

              {

                 undo_move() ;                      //Отменить ход.

                 move_num-- ;

              }

             else

             return ;                                 //Обход невозможен.

         }

    } 
 

    Номер использованного варианта хода для  каждого из ходов запоминается в  массиве, размер которого выбирается в  соответствии с размером доски. Описанный  алгоритм осуществляет перебор вариантов  и находит решение, если оно имеется. Отсутствие решения приводит к полному перебору всех вариантов.

    Для иллюстрации выполнения возвратов  в табл. 1 приведен протокол обхода доски  размером 3 на 4 из клетки с координатами (2,4). В конце приведен полученный в результате обхода путь. 

    Таблица 1. Протокол обхода доски размером 3 на 4 из клетки (2,4) 

    Для некоторых клеток программа работает чрезвычайно медленно уже при  небольших размерах доски. Например, для доски 6*6 при старте из клетки (5,2) поиск пути требует более 290 возвратов. 
 
 
 
 
 

    2.2. Результаты работы программы с оптимизацией. 

    Из  работы [5] известно, что для досок  размером N*M и M*N:

• Не существует ни одного обхода при N,M < 3; N = 3, M = 5,6; N = M = 4;
• Имеется как минимум одна клетка, из которой возможен обход доски при N = 3, M = 4; N = 3, M >= 7; N >= 4, M >= 5.

    Переходя  к изложению полученных результатов  отметим, что они относятся к  перечисленным выше методам оптимизации  и эвристически выбранным массивам вариантов для хода коня. При применении других методов оптимизации [5] и иных массивов получаемые результаты могут различаться.

    Рассмотрим  результаты обхода некоторых досок. Для них приводятся таблицы, в  которых указывается количество возвратов, выполненное при нахождении обхода из соответствующей клетки. При отсутствии обхода в клетке указывается  символ «N». В случае, если количество возвратов превысило задаваемую в программе величину (MAX_RET = 400000), поиск пути прекращается, а в соответствующей клетке выводится сокращение «LIM». В таблицах, построенных для метода оптимизации, использующего различные массивы вариантов хода коня, в клетке дополнительно указывается обозначение массива (от ‘A’ до ‘E’), при применении которого обход был получен без возвратов (GOOD_RET = 1). При этом, если результат был получен для первого массива, то соответствующий ему символ ‘A’ не выводится. Также в таблицах приводится один из полученных путей. 

    Результаты, полученные для доски размером 5 на 5, приведены в табл. 2. 
 
 

    Таблица 2. Результаты работы программы для  доски 5 на 5

    Результаты, полученные для доски размером 7 на 7, приведены в табл. 3. 

    Таблица 3. Результаты работы программы для  доски 7 на 7

    Для классической шахматной доски размером 8 на 8 получены следующие результаты:

• Для оптимизаций 1 и 2 в большинстве клеток превышено предельное значение числа возвратов (MAX_RET). Минимальное количество возвратов в клетке (5, 5) – 2502;
• Для оптимизаций 1 и 3 во всех клетках, кроме (4, 1) и (6, 4), ноль возвратов. В указанных клетках 9 и 79 возвратов, соответственно;
• Для оптимизаций 1-3 в клетке (6, 4) три возврата. В остальных клетках ноль возвратов;
• Для оптимизаций 1-4 во всех клетках ноль возвратов. При этом в клетке (6, 4) был использован второй массив возможных ходов.

    Для доски размером 9 на 9 для клеток, из которых существует обход, он достигает без единого возврата назад для оптимизаций 1-3 (для 1-4, естественно, тоже).

      Для доски размером 50 на 50 получены следующие результаты:

• Для оптимизаций 1-3 в большинстве клеток ноль возвратов, а количество возвратов в остальных клетках варьируется от единиц до значений, превышающих предельное значение;
• Для оптимизаций 1-4 во всех клетках ноль возвратов.

    Для доски размером 77 на 77, для клеток, из которых существует обход, получены следующие результаты:

• Для оптимизаций 1-3 в большинстве клеток ноль возвратов, а количество возвратов в остальных клетках варьируется от единиц до значений, превышающих предельное значение;
• Для оптимизаций 1-4 во всех клетках ноль возвратов.

    Для доски размером 100 на 100 получены следующие  результаты:

• Для оптимизаций 1-3 в большинстве клеток ноль возвратов, а количество возвратов в остальных клетках варьируется от единиц до значений, превышающих предельное значение;
• Для оптимизаций 1-4 во всех клетках, за исключением клеток (94, 24) и (94, 79), ноль возвратов.

    Как отмечено выше, рассматриваемые методы оптимизации для не квадратных досок  не столь эффективны. Результаты, полученные для доски размером 14 на 3, приведены  в табл. 4.

    Таблица 4. результаты работы программы для  доски 14 на 3

    3. Рекурсивная программа 

    Наиболее  известное решение для задачи обхода конем – рекурсивное [2]. При  этом структура функции, выполняющей перебор, имеет следующий вид:

    int find_path ( int cur_x, int cur_y, int move_num )

    {

        desk_state [cur_x] [cur_y] = nove_num ; //   Запомнить ход.

         if ( move_num > max_moves ) return 1 ; //  Проверим завершение обхода.

         // Проверить каждый возможный ход из текущей клетки.

         for ( int I = 0 ; I < 8 ; i++ )

        {

            int next_x = cur_x + possible_moves [i] [0] ; // Определить следующее поле.

            int next_y = cur_y + possible_moves [i] [1] 

             if (            move_possible (next_x, next_y  )

                      && find_path (next_x, next_y, move_num+1 ))  return 1 ;

        }

          // Возврат.

         desk_state [cur_x] [cur_y] = 0 ;

         back_ret++ ;

         return 0 ;

    }

    В этой программе могут быть использованы все виды оптимизаций, описанные выше. 
 
 
 
 
 
 
 
 
 
 
 
 
 

    4. Автоматная программа. 

    Если  первые две программы для решения  этой задачи вполне традиционны, то автоматные программы к таковым не относятся [2].

    Отметим, что автоматная программа может  быть формально построена по описанной  выше итеративной программы с помощью метода, изложенного в работе [7]. Автоматная программа может быть также формально построена и по приведенной рекурсивной программе с использование метода, предложенного в работе [8].

    Кроме того, можно создать автоматную программу путем непосредственного построения автомата по условиям задачи. На рис. 1, 2 для этого автомата приведены соответствующие схема связи и граф переходов автомата Мили. 
 

    Рис. 1. Схема связей автомата для задачи о ходе коня

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

    Рис. 2. граф переходов автомата для задачи о ходе коня

    Упрощенный  текст функции, реализующей этот автомат, приведен ниже:

    void find_path_switch ( int limit )

    {

                y = 0 ; 

                do

                   switch ( y )

                  {

                       case 0 :

                            if ( x4 () )                             y = 3 ;

                            else

                           { z1_0 () ;                             y = 1 ;}

                       break ;

                       case 1:

                            if ( x1() )                              y = 4 ;

                            else

                            if ( x3() ) { z1_1()  ; }

                            else

                            if ( x2() ){ z2 () ; z1_2() ;   y = 2 ; }

                            else                                       y = 3 ;

                       break ;

                       case 2 :

                           if ( x5 (limit) )                       y = 5 ;

                           else

                                                                        y = 1 ;

                        break ;

                        case 3 :                                     y = 0 ; break ;

                        case 4 :                                    y = 0 ; break ;

                        case 5 :                                     y = 0 ; break ;

         }

    while ( y < 3 ) ;

    } 

    Заключение 

    Совместное  применение достаточно простых и известных методов оптимизации позволило резко сократить перебор, благодаря чему удается относительно быстро находить пути в досках с весьма большой размерности. Так, на компьютере, оснащенном процессором Pentium II 400 МГц, поиск обхода из каждой клетки доски размером 200 на 200 занял около 20 минут (на поиск одного обхода – около 0,03 с). При этом для большинства клеток обход выполняется без единого возврата назад. В программе, наряду с рассмотренными, могли бы использоваться и другие методы оптимизации [5]. Однако на досках очень большого размера, например 2000 на 2000 клеток, нахождение даже одного пути занимает значительное время и при применении методов оптимизации, позволяющих строить обходы без единого возврата.