Комбинаторные алгоритмы. Исследование решение задачи построения магических квадратов
ФГБОУ ВПО «Московский государственный университет экономики, статистики и информатики (МЭСИ)»
Кафедра математического
обеспечения и
Дисциплина СиАКОД
Курсовой проект
«Комбинаторные алгоритмы. Исследование решение задачи построения магических квадратов»
Студент: Наразин И.В.
Группа: ДКО-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},{
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+
j+movesp[k][1]>0&&i+movesp[k][
j+movesp[k][1]<=y&&i+movesp[k]
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,
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,
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<<
cout<<"cols=";cin>>y;cout<<
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&
&& 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 минуты
Уже очевидно, что рекурсивный намного эффективнее итеративного.
Возможные усовершенствования
- Правила Варнсдорфа
Согласно этому правилу, следующую клетку для хода нужно выбирать так, чтобы из нее было наименьшее количество возможных путей. Если таких клеток несколько, выбрать можно любую
- Проверка возможности решений д
о запуска функций
Т.к. конь ходит по клеткам, чередуя цвета, то первая и последняя клетка его пути будут одного цвета. Поэтому, если клеток нечетное количество, то нужно убедиться, что конь стоит на клетке такого цвета, которого больше.
- Использование несколько массивов смещений (movesp)
Позволяет
эмпирически сократить
Привожу листинг усовершенствованного алгоритма рекурсии с правилом Варнсдорфа
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&
maysteps=0;
for (int j=0;j<8;j++) // Считаем количество ходов из следующей клетки
{
if( next_x+movesp[j][0]>0&&next_y+
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.
Эти действия
нужно повторять до тех пор, пока
не получим самую большую
Программа, реализующая этот алгоритм:
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 |
Результат работы программы:
Для разбора работы алгоритма возьмем более простой граф:
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
height: 12pt; z-index: 0;">
2
5
3
Подбор будет происходить так:
Листинг
алгоритма:
void
gamilt(int k)
{
for
(int y = 1; y < N; y++) //идем по всем вершинам
{
if
(graph[x[k - 1]][y] != 0) // если соединены
{
if
((k==N-1)&&(y == v0)) // если текущая вершина - замыкающая маршрута
{
for
(int i=0;i<N-1;i++) cout<<x[i]<<" ";
cout
<<endl;
}
else
{
if
(dop[y] == 1) //если y еще не включена в маршрут
{
x
[k] = y;
dop
[y] = 0; //включаем y в маршрут
gamilt
(k + 1);
dop
[y] = 1;
}
}
}
}
}
void
gamiltCycle()
{
for
(int i = 0; i < N; i++) dop[i] = 1; //все вершины изначально не включены в маршрут
v0 = 1;
//начало
x
[0] = v0;
dop
[v0] = 0;
gamilt
(1);
}
Магические квадраты
Магический квадрат – квадрат, заполненный натуральными числами таким образом, что сумма всех столбцов, строк и диагоналей одна и та же.
Я рассмотрю алгоритмы построения трех типов таких квадратов:
- квадрат с нечетной стороной
- квадрат с четной стороной
- дважды четный квадрат
Нечетный квадрат
Метод диагоналей
Изначально ставим единицу по центру в первой строке
. Дальше начинаем подряд
- Дойдя до верхнего края квадрата, следующую цифру ставить в след
ующем столбце в последней стро ке и продолжать уже с этого места. - Дойдя до правого края квадрата следующую цифру ставить в начале предыдущей строки и продолжать с этого места
- Дойдя до угла или до какой-либо цифры, следующую цифру ставить под текущей и продолжать с этого места.
Псевдокод процедуры заполнения квадрата:
-изначальные координаты
i и j : середина первой строки
do
{
if
(если дошли до правого верхнего угла) {
-меняем координаты (
i,j) на клетку под предыдущим числом
}
if
(если дошли до верхней границы) -переходим на последнюю строку
if (если дошли до правой границы) - переходим на первый столбец
if
(выбранная клетка пустая) {
-ставим цифру
-увеличиваем цифру
-устанавливаем координаты на следующую клетку вверх по диагонали
}
else {
-ставим цифру под предыдущей цифрой
-увеличиваем цифру
-устанавливаем координаты на следующую клетку вверх по диагонали
}
}
while (цифра не равна максимально возможной)
Реализация на С++
:
void
generate() {
int
i=1;
int
j=(N-1) / 2 +1;
int
b=1;
matrix[
i][j]=0;
do
{
if
(i<1&&j>=N) {i=i+2;j--;}
if
(i<=0) i=N-1;
if
(j>N-1) j=1;
if
(matrix[i][j]==0) {
matrix[
i][j]=b;
i
--;
j
++;
b
++;
}
else {
matrix[
i+2][j-1]=b;
b
++;
i
++;
}
}
while
(b<=(N-1)*(N-1));
}
Сгенерированный программой квадрат 5х5:
Метод террас
Для примера создадим магический квадрат размерности 5х5. Для этого к каждой стороне квадрата нужно присоединить так называемые
“террасы”.
После этого все
“длинные” диагонали снизу вверх заполняются подряд идущими цифрами
5 | |||||||||||||||||||||
4 |
10 | ||||||||||||||||||||
3 |
9 |
15 | |||||||||||||||||||
2 |
8 |
14 |
20 | ||||||||||||||||||
1 |
7 |
13 |
19 |
25 | |||||||||||||||||
6 |
12 |
18 |
24 | ||||||||||||||||||
11 |
17 |
23 | |||||||||||||||||||
16 |
22 | ||||||||||||||||||||
21 | |||||||||||||||||||||
После этого цифры с террас переносятся в квадрат таким образом: новое место цифры будет
n-ой клеткой, считая от текущей клетки террасы. n- порядок квадраты. Выполнив эти перемещения мы получим магический квадрат.
5 | |||||||||||||||||||||
4 |
10 | ||||||||||||||||||||
3 |
16 |
9 |
22 |
15 | |||||||||||||||||
2 |
20 |
8 |
21 |
14 |
2 |
20 | |||||||||||||||
1 |
7 |
25 |
13 |
1 |
19 |
25 | |||||||||||||||
6 |
24 |
12 |
5 |
18 |
6 |
24 | |||||||||||||||
11 |
4 |
17 |
10 |
23 | |||||||||||||||||
16 |
22 | ||||||||||||||||||||
21 | |||||||||||||||||||||
Четный квадрат
Метод разбиения на квадраты
Чет
ный квадрат – квадрат со стороной n=2m, где m=2r+1.
Разобьем основной квадрат на 4 квадрата со сторонами
m и заполним весь квадрат подряд идущими цифрами от 1 до n2.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
36 |
Затем первые
r(в данном примере r=1) цифр в первом квадрате пометим знаком *. Следующую цифру знаком - . Следующую: |. И циклически сдвинем их по всему квадрату
1* |
2- |
3| |
4 |
5 |
6 |
7| |
8* |
9- |
10 |
11 |
12 |
13- |
14| |
15* |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
36 |
Знаком * пометим и цифры, которые симметричны относительно вертикали уже помеченным цифрам.
1* |
2- |
3| |
4 |
5 |
6* |
7| |
8* |
9- |
10 |
11* |
12 |
13- |
14| |
15* |
16* |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
36 |
Затем меняем цифры местами таким образом:
цифры со знаком * меняем местами с симметричной относительно центра цифрой. Со знаком – относительно серединной горизонтали, а | относительно серединной вертикали. В итоге получится магический квадрат:
36 |
32 |
4 |
3 |
5 |
31 |
12 |
29 |
27 |
10 |
26 |
7 |
19 |
17 |
22 |
21 |
14 |
18 |
13 |
20 |
16 |
15 |
23 |
24 |
25 |
11 |
9 |
28 |
8 |
30 |
6 |
2 |
33 |
34 |
35 |
1 |
Листинг функции генерации квадрата:
void
generate() {
int
k=1; // заполняем матрицу числами
for
(int i=1; i<=N; i++)
{
for
(int j=1; j<=N; j++)
{
a[
i][j]=k; k++;
}
}
int
r = ((N)/2 -1) /2; int m=(N) / 2;
for
(int i= 1;i<= m; i++) // инвертируем диагонали
{
int
j = i;
for
(int k = 1; k<= r ;k++)
{
if
(j > m) j = 1;
int
s= N- i +1;
int
b = N - j + 1;
swap(
a[i][j], a[s][b]);
swap(
a[i][b], a[s][j]);
j++
;
}
}
int
i=1; int j=r+1; // обмениваем относительно горизонтали
for
(int k=1; k<=m; k++) {
if
(j > m) j = 1;
int
s = N - i + 1;
swap(
a[i][j], a[s][j]);
i++
; j++;
}
i
= 1; j = r + 2;// обмениваем относительно вертикали
for
(int k = 1; k<= m;k++) {
if
(j > m) j = 1;
int
b = N - j + 1;
swap(
a[i][j], a[i][b]);
i++
; j++;
}}
Псевдокод:
-заполняем матрицу подряд идущими числами
r
= количество диагоналей для обмена
m
= количество элементов в малом квадрате
for
(по всем элементам малого квадрата(i)) {
j=i
for
(по всем дигоналям(r) для обмена(k)) {
if
(столбец вышел за пределы малого квадрата) -снова переходим на первый столбец
-меняем местами текущие элементы каждой из диагоналей
}
}
j=
следующая клетка, после диагоналей
for
(по всем элементам малого квадрата) {
if
(столбец вышел за пределы малого квадрата) -снова переходим на первый столбец
- обмениваем текущий элемент с
симметричным ему относительно горизонтали
}
j=
следующая клетка, после диагоналей +1
for
(по всем элементам малого квадрата) {
if
(столбец вышел за пределы малого квадрата) -снова переходим на первый столбец
- обмениваем текущий элемент с
симметричным ему относительно вертикали
}
Результат работы:
Дважды четные квадраты
Дважды ч
етный квадрат – квадрат со стороной n=2m, где m=2r.
“
Шахматный” способ
Выпишем в квадрат все числа от 1 до
n2.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |
50 |
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
59 |
60 |
61 |
62 |
63 |
64 |
Разделим квадрат на 4 квадрата порядка
- Комбинаторные задачи на уроках математики как средство развития младших школьников
- Комбинационная группировка и корреляционный анализ
- Комбинационные устройства
- Комбинирование в промышленности
- Комбинирование и концентрация в производстве
- Комбинирование производста
- Комбинирование производства ОАО «Балашовслюда»
- Командообразование как эффективный фактор работы организации
- Командообразование на предприятии
- Командообразованние
- Комбайн очисний ГШ200Б
- Комбинаторика
- Комбинаторика в начально школе
- Комбинаторика в нашей жизни
