Комбинаторные алгоритмы. Исследование решение задачи построения магических квадратов

ФГБОУ ВПО «Московский государственный университет экономики, статистики и информатики (МЭСИ)»

 

 

 

 

Кафедра математического  обеспечения и администрирование  информационных систем

Дисциплина СиАКОД

 

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

«Комбинаторные алгоритмы. Исследование решение задачи построения магических квадратов»

 

 

 

 

 

 

 

 

Студент: Наразин И.В.

Группа: ДКО-201

Проверила: Комлева Н.В.

 

 

 

 

Москва, 2011 г.

Содержание

Обход конем	3
Генерация перестановок	8
Гамильтонов цикл	11
Магические квадраты Литература	15 27

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Обход  шахматного поля конем

 

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

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

Итеративный

Идея: методом полного перебора выбираем любую клетку, где мы еще не были и т.д. Если на каком-то этапе таких клеток не остается, возвращаемся назад до первой возможности поменять ход.

Упрощенно, такой алгоритм можно  записать так:

For (int i=1;i<=n*n;) {

If (make_move()) i++  // [1]

else if (i>1) {

undo_move(); i--; // [2]

} else cout<< “решений нет”;

}

 

 

 

 

 

 

 

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

 

 

#include "stdafx.h"

#include <vector>

#include <iostream>

using namespace std;

 

const int N=6;

const int M=6;

 

int moves[N*M+1]={-1};

int movesp[][2]={{-1,-2},{-2,-1},{-2,1},{1,-2},{-1,2},{2,-1},{2,1},{1,2}};

 

bool make_move(int &i,int &j,int matrix[N][M],int movenum,int x,int y) {

for (int k=moves[movenum]+1;k<8;k++) {

if(matrix[i+movesp[k][0]][j+movesp[k][1]]==0&&

j+movesp[k][1]>0&&i+movesp[k][0]>0&&

j+movesp[k][1]<=y&&i+movesp[k][0]<=x) { 

i=i+movesp[k][0]; j=j+movesp[k][1];

matrix[i][j]=movenum+1;

moves[movenum]=k;

  return true;

}

}

return false;

}

 

bool undo_move(int &i,int &j, int movenum,int matrix[N][M],int x,int y) {

matrix[i][j]=0;

i=i-movesp[moves[movenum]][0];

j=j-movesp[moves[movenum]][1];

moves[movenum+1] = -1 ;

return true;

}

 

 

void findpath(int y,int x, int i,int j) {

memset( moves, -1, sizeof(moves)) ;

int matrix[N][M]={{0,0}};

 

int maxmove=y*x;

int movenum=1;

matrix[i][j]=1;

for (;movenum<maxmove;) {

  if (make_move(i,j,matrix,movenum,x,y)) {

movenum++;

cout<<"Step "<<movenum<< "in ("<<i<<", "<<j<<")";cout<<endl;

}

else

if (movenum>1) {

cout<<"Undo "<<movenum<< "in ("<<i<<", "<<j<<")";cout<<endl;

undo_move(i,j,movenum-1,matrix,x,y);

movenum--;

}

else {

cout << "Not solutions";

return;

}

 

}

cout<<movenum<<endl<<endl;

printm(matrix,x,y);

};

 

int _tmain(int argc, _TCHAR* argv[])

{

int x,y,j,i;

cout<<"rows=";cin>>x;cout<<endl;

cout<<"cols=";cin>>y;cout<<endl;

cout<<"i=";cin>>i;cout<<endl;

cout<<"j=";cin>>j;cout<<endl;

findpath(y,x,i,j);

system("pause");

return 0;

}

 

 

В массиве  movesp содержаться все возможные ходы конем.

 

С помощью  массива moves[] каждый раз достигается новый путь, который не использовался ранее. Количество элементов этого массива равно количеству возможных ходов (т.е. N*N). В цикле функции make_move()  переменной I присваивается значение moves[movenum], где movenum – номер текущего хода. Т.к. изначально все элементы массива раны -1, то цикл пройдется по всем значеням массива movesp. Как только возможный ход будет найден, в массив moves запишется индекс хода в массиве movesp. Таким образом, для каждого хода movenum через массив moves можно всегда получить предыдущий ход (чтобы отменить текущий).

 

// отмена хода

i=i-movesp[moves[movenum]][0];

j=j-movesp[moves[movenum]][1];

 

 

Т.к. он запоминает индекс хода из массива movesp, то отменив, например ходы 10 и 9, мы запишем в moves[10] и moves[9] по -1, что означает, что ходить с 9 и далее можно в любую доступную клетку. А в movies[8] остался индекс предыдущих координат хода в 9. Предположим moves[8] = 3. Значит в функции make_move мы сразу начнем проверять ход с индекса 4, пропустив уже проверенные 1,2 и 3. Так и достигается уникальность каждого пути в процессе перебора.

 

 

Рекурсивный

 

Рекурсивный алгоритм для данной задачи является наиболее подходящим. Рекурсивная функция выглядит так:

 

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

{

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

if( move_num == maxmove) return 1 ; // Проверить завершение обхода.

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

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

{

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

int next_y = cur_y + movesp[i][1] ;

 

if( next_x>0&&next_y>0&&next_x<=N&&next_y<=M&&matrix[next_x][next_y]==0

&& find_path( next_x, next_y, move_num+1 )) //[1]

return 1; 

}

matrix[cur_x][cur_y]=0;

 

return 0 ;

}

 

 

Рекурсивная функция(псевдокод):

 

Function find_path() {

-записываем номер хода  в матрицу(доска)

if (количество сделанных ходов не равно максимально возможному) {

for (для всех возможных ходов из текущей клетки) {

if (новый ход возможен и find_path(координаты нового хода)) {

решение найдено

}

}

} else {решение не найдено}

}

 

 

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

В месте [1] выполняется самовызов функции, и если все функции, которые будут вызваны из нее вернут истину, то и сама функция [1] вернет истину.

Сравним время работы этих двух алгоритмов для доски 5х5, где конь стоит на клетке 3,3.

Рекурсивный – 1 секунда

Итеративный – 2 минуты

 

Уже очевидно, что рекурсивный намного эффективнее итеративного.

 

Возможные усовершенствования

 

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

 

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

 

2. Проверка возможности решений до запуска функций

 

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

 

3. Использование несколько массивов смещений (movesp)

 

Позволяет эмпирически сократить количество возвратов. Для этого нужно завести  несколько массивов, состоящих из элементов массива movesp, но с другим порядком расположения элементов. При обходе, количество возвратов подсчитывать и, как только их количество превысит заранее установленное, то переходить к другому массиву. Нужно заранее завести две константы, например MAXNEXT и MAXEND. Где первый содержит количество возвратов, нужное для перехода к следующему массиву. А второй – количество возвратов, когда уже все массивы были использованы (т.е. используется последний).

 

 

Привожу листинг  усовершенствованного алгоритма рекурсии с правилом Варнсдорфа

 

int find_pathw( int cur_x, int cur_y, int move_num)

{

 

int minsteps=9; int mini;

int maysteps;

 

matrix[cur_x][cur_y] = move_num ; // Записываем ход в массив

if( move_num == maxmove) return 1 ; // Проверить завершение обхода.

 

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

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

{

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

int next_y = cur_y + movesp[i][1] ;

 

//***Варнсдорф

// Находим ход  с мин количество дальнейших  возможных ходов

if( next_x>0&&next_y>0&&next_x<=N&&next_y<=M&&matrix[next_x][next_y]==0) {

maysteps=0;

for (int j=0;j<8;j++) // Считаем количество ходов из следующей клетки

{

if( next_x+movesp[j][0]>0&&next_y+movesp[j][1]>0&&next_x+movesp[j][0]<=N&&next_y+movesp[j][1]<=M&&matrix[next_x+movesp[j][0]][next_y+movesp[j][1]]==0)

maysteps++;

 

}

if (maysteps<minsteps) {

minsteps=maysteps; mini=i;

}

}

}

/////////

 

if (find_pathw( cur_x+movesp[mini][0], cur_y+movesp[mini][1], move_num+1 )) // И ставим на клетку с мин. кол. дальнейших ходов

return 1;

 

// Иначе откат

matrix[cur_x][cur_y]=0;

return 0 ;

}

 

 

Для сравнения: поле 10х10, конь на 1,1

 

Простой рекурсивный: более 30 минут

Усовершенствованный рекурсивный: 1 секунда, 0 возвратов

 

Таким образом, этот вариант является самым лучшим.

 

 

 

Генерация перестановок

 

В данной задаче на входе подается некая строка. Нужно сгенерировать все возможные  уникальные перестановки из символов этой строки.

 

Генерация перестановок в лексикографическом порядке (итеративный)

 

Разберем  данный алгоритм на примере. Пусть на входе дана строка 1234

 

Первым циклом мы идем по строке с конца и ищем первый символ, который не удовлетворяет  условию: a[i]<a[i-1]. В данном примере это 3. Т.к. 4 > 3.

 

Вторым циклом мы опять идем по строке с конца  и ищем символ, который больше a[i]. В данном примере искомый символ будет 4.

 

И меняем их местами. Дальше инвертируем все символы, стоящие после a[i]. В данном примере там будет стоять только одна 4.

 

В итоге получится  новая строка – 1243.

 

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

 

Программа, реализующая этот алгоритм:

 

cout<<"Enter your string"<<endl<<endl;

char *str=new char[255];

cin>>str;

bsort(str); // сотритруем строку по возрастанию

int n=strlen(str)-1;

 

cout<<"---"<<endl;

cout<<str<<endl;

while (1)

{

int i=n;

while (i>0&&str[i]<str[i-1]) i--; // 1 цикл, ищем следующий символ, не удовл. условию

int j=n;

while (str[j]<str[i-1]) j--; //2 цикл, ищем символ больший найденного

 

swap(str[i-1],str[j]); // меняем местами

 

for (int j=0;j<=(n-i+1)/2-1;j++) { // инвертируем конец

swap(str[i+j],str[n-j]);

}

cout<<str<<endl;

 

bool f=false; // проверяем, найдены ли все решения

for(int i=n;i>0;i--) {

if (str[i]>str[i-1]) f=true;

}

if (!f) break;

}

system("pause");

return 0;

 

Результат работы:

 

 

 

 

 

 

 

 

Рекурсивный алгоритм поиска перестановок (антилексикографический)

 

Псевдокод:

 

If (цифра последняя) {выводим очередную перестановку}

For (от позиции текущей цифры до конца строки(i))

{

-меняем местами текущую  цифру с i

-рекурсивная функция для  новой строки 

- меняем обратно

}

 

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

 

Например, для 1234 запустятся рекурсивные функции  для следующих строк: 1234,2134,3214,4231.

 

Вместе со строками передается и число-номер  символа для перестановок. Очевидно, что чем глубже уходит рекурсии (т.е. чем больше это число), тем меньше вариантов перестановок, т.к мы перебираем варианты от этого числа и до длины строки.

 

Таким образом, когда мы дойдем до последнего числа  нам нужно просто вывести строку.

 

Рекурсивная функция:

 

 

 

 

 

void generate (int l,int r) {

if (l==r-1) { // достигли последнего, выводим

cout<<str<<endl;

return;

} else {

for (int i=l;i<r;i++) { //перебираем символы

swap(str[l],str[i]);

generate(l+1,r);

swap(str[l],str[i]);

}

}

}

 

 

 

Ее вызов: generate(0,strlen(str));

 

Результат работы:

 

 

 

Гамильтонов цикл

 

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

 

Алгоритм его поиска – это полный перебор всех возможных путей.

Изначально  задается матрица смежности графа  и начальная позиция.

 

Псевдокод:

 

for (от 1 до количества вершин) {

if (текущая вершина соединена с данной) {

if (если данная вершина последняя и равна начальной) { выводим путь }

else {

if (данная вершина еще не включена в маршрут) {

-добавляем в маршрут

-запускаем рекурсивную функцию начиная с этой вершины

}

}

}

}

 

 

 

 

 

 

 

Например, рассмотрим такой граф:

 

 

 

 

 

 

 

 

 

Его матрица смежности:

0	1	1	1	0	0	0
1	0	0	1	0	0	1
1	0	0	0	1	0	0
1	1	0	0	1	0	0
0	0	1	1	0	1	0
1	0	0	0	1	0	1
0	1	0	0	0	1	0