Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.
Краткое сожержание материала:

Размещено на http:///

ФГБОУ ВПО МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ, СТАТИСТИКИ И ИНФОРМАТИКИ

Курсовой проект

«Комбинаторные алгоритмы. Поиск кратчайшего пути на графе.»

Дисциплина: «Структуры и алгоритмы компьютерной обработки данных »

Москва 2013



Содержание

Задача о ходе коня

Методы решения

Описание алгоритмов

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

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

Генерация перестановок из n элементов

Постановка задачи

Методы решения и описание алгоритмов

Построение эйлерова цикла на графе

Постановка задачи

Методы решения и описания алгоритма

Поиск кратчайшего пути на графе

Постановка задачи

Описание задачи

Программная реализация

Используемая литература

Приложение



Задача о ходе коня

Постановка задачи. Дана доска nxn. Конь, который ходит согласно шахматным правилам, помещается на поле с начальными координатами x0, y0. Нужно покрыть всю доску ходами коня, т.е. вычислить обход доски, если он существует, такой, что каждое поле посещается ровно один раз.

Методы решения

Метод Эйлера

Метод Эйлера состоит в том, что сначала конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся не пройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов.

Метод Вандермонда

Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей x/y , где x и y -- координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8.

Его метод нахождения подходящей последовательности аналогичен методу Эйлера, но позволяет находить маршруты коня только для досок чётной размерности.

Правило Варнсдорфа

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

Со времен Эйлера известен так называемый "раздельный ход коня"; который заключается в нахождении пути по одной половине доски, его симметричном дублировании и соединении обеих путей вместе(рис.1) .

Многие решения опираются на создание симметричного маршрута, пример одного из них на рисунке 2.

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



Описание алгоритмов

Данная задача из области «искусственного интеллекта». Здесь нужно строить алгоритмы, которые находят решение задачи не по фиксированным правилам вычисления, а методом проб и ошибок. Процесс проб и ошибок можно рассматривать в общем виде как поисковый процесс, который постепенно строит и просматривает (а так же обрезает) дерево подазадач. Во многих случаях такие деревья поиска растут очень быстро, обычно экспоненциально, в зависимости от заданного параметра. Так как мы хотим сохранять историю последовательного «захвата» доски, то мы будем представлять каждое поле доски целым числом, по которому можно судить посещалось ли поле и на каком ходу.

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

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

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

· на каждом шаге ищется фрагмент пути, начинающийся из текущей клетки и не включающий уже пройденные;

· при совершении хода из массива возможных ходов извлекается очередной элемент, который приводит в незанятую клетку, находящуюся в пределах доски;

· если ход невозможен, то происходит возврат в предыдущую клетку (отмена хода);

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

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

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 ; // Обход невозможен.

}

}

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

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

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

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

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

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

{

desk_state[cur_x][cur_y] = move_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 ;

}

Оптимизированный алгоритм

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

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

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

int solution_impossible()

{

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

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

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

}

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

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

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

Развитием этого метода...