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

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

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

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

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

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

    (БТИ  АлтГТУ) 
 
 

    Кафедра ИУС 

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

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

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

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

    г.Бийск  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)