Автор работы: Пользователь скрыл имя, 08 Декабря 2010 в 12:35, курсовая работа
Класс алгоритмов, позволяющий решать подобные задачи, в англоязычной литературе называется «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
Для
некоторых клеток программа работает
чрезвычайно медленно уже при
небольших размерах доски. Например,
для доски 6*6 при старте из клетки
(5,2) поиск пути требует более 290 возвратов.
2.2.
Результаты работы программы
с оптимизацией.
Из работы [5] известно, что для досок размером N*M и M*N:
Переходя к изложению полученных результатов отметим, что они относятся к перечисленным выше методам оптимизации и эвристически выбранным массивам вариантов для хода коня. При применении других методов оптимизации [5] и иных массивов получаемые результаты могут различаться.
Рассмотрим
результаты обхода некоторых досок.
Для них приводятся таблицы, в
которых указывается количество
возвратов, выполненное при нахождении
обхода из соответствующей клетки.
При отсутствии обхода в клетке указывается
символ «N». В случае, если количество возвратов
превысило задаваемую в программе величину
(MAX_RET = 400000), поиск пути прекращается, а
в соответствующей клетке выводится сокращение
«LIM». В таблицах, построенных для метода
оптимизации, использующего различные
массивы вариантов хода коня, в клетке
дополнительно указывается обозначение
массива (от ‘A’ до ‘E’), при применении
которого обход был получен без возвратов
(GOOD_RET = 1). При этом, если результат был
получен для первого массива, то соответствующий
ему символ ‘A’ не выводится. Также в таблицах
приводится один из полученных путей.
Результаты,
полученные для доски размером 5
на 5, приведены в табл. 2.
Таблица 2. Результаты работы программы для доски 5 на 5
| Оптимизации
1
33951 N 212310 N 4543 N 52061 N 123374 N 69216 N 23411 N 32116 N 214142 N LIM N 1300 N 325867 N 30565 |
Оптимизации
1 – 3
0 N 127 N 0 N 0 N 0 N 127 N 0 N 0 N 0 N 0 N 0 N 127 N 0 |
| Оптимизации
1 и 2
950 N 4676 N 256 N 1596 N 3057 N 2102 N 629 N 1417 N 4296 N 7463 N 94 N 4426 N 381 |
Оптимизация
1 – 4
0 N B0 N 0 N 0 N 0 N B0 N 0 N 0 N 0 N 0 N 0 N D0 N 0 |
| Оптимизации
1 и 3
0 N 1709 N 0 N 0 N 0 N 1709 N 0 N 0 N 0 N 0 N 0 N 1709 N 0 |
Путь
из (5,5), возвратов 0:
5 14 19 24 3 20 9 4 13 18 15 6 23 2 25 10 21 8 17 12 7 16 11 22 1 |
Результаты,
полученные для доски размером 7
на 7, приведены в табл. 3.
Таблица 3. Результаты работы программы для доски 7 на 7
| Оптимизации
1
29032 N LIM N LIM N LIM N LIM N LIM N 172170 N 19396 N 19396 N LIM N LIM N 29032 N LIM N LIM N LIM N 39629 N 14807 N LIM N LIM N LIM N LIM N 6415 N 33488 N 386809 N LIM |
Оптимизации 1 – 3 8339 N 0 N 0 N 0 N 0 N 0 N 0 N 0 N 0 N 3 N 0 N 0 N 0 N 5972 N 0 N 14204 N 0 N 0 N 0 N 5972 N 0 N 0 N 0 N 0 N 0 |
| Оптимизации
1 и 2
1426 N 17178 N 293292 N 17178 N LIM N 302303 N 3353 N 966 N 966 N LIM N 133190 N 1426 N LIM N 28390 N 70852 N 2052 N 980 N 30757 N 9903 N LIM N 24272 N 491 N 681 N 5118 N 108858 |
Оптимизации
1 – 4
B0 N 0 N 0 N 0 N 0 N 0 N 0 N 0 N 0 N B0 N 0 N 0 N 0 N B0 N 0 N D0 N 0 N 0 N 0 N B0 N 0 N 0 N 0 N 0 N 0 |
| Оптимизации
1 и 3
291565 N 0 N 0 N 0 N 0 N 0 N 0 N 0 N 0 N 375 N 0 N 0 N 0 N LIM N 0 N LIM N 0 N 0 N 0 N LIM N 0 N 0 N 0 N 0 N 0 |
Путь из (7,7), возвратов 0: 9 6 11 40 29 4 27 12 39 8 5 26 43 30 7 10 35 44 41 28 3 36 13 38 25 48 31 42 19 16 47 34 45 2 23 14 37 18 21 24 49 32 17 20 15 46 33 22 1 |
Для классической шахматной доски размером 8 на 8 получены следующие результаты:
Для доски размером 9 на 9 для клеток, из которых существует обход, он достигает без единого возврата назад для оптимизаций 1-3 (для 1-4, естественно, тоже).
Для доски размером 50 на 50 получены следующие результаты:
Для доски размером 77 на 77, для клеток, из которых существует обход, получены следующие результаты:
Для доски размером 100 на 100 получены следующие результаты:
Как отмечено выше, рассматриваемые методы оптимизации для не квадратных досок не столь эффективны. Результаты, полученные для доски размером 14 на 3, приведены в табл. 4.
Таблица 4. результаты работы программы для доски 14 на 3
| Оптимизации
1 – 4
B0 B0 E997 E45274 B0 E0 0 B0 D0 0 E17 E626 0 0 B0 E390577 E56 0 0 C0 E16 E10378 B0 0 0 E1006 E67 0 B0 B0 E997 E45274 C0 B0 C0 B0 C0 B0 E17 E626 0 0 |
| Путь
из (14, 3), возвратов 0:
20 17 14 11 26 23 32 9 30 7 36 39 2 5 15 12 19 22 33 10 25 28 35 40 3 6 37 42 18 21 16 13 24 27 34 31 8 29 38 41 4 1 |
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
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 клеток, нахождение даже одного пути занимает значительное время и при применении методов оптимизации, позволяющих строить обходы без единого возврата.