18
v Введение
Широкое распространение идей структурного программирования в последние 20-30 лет оказало большое влияние на теорию и практику программирования и привело к пересмотру роли типа и структуры данных при разработке соответствующих алгоритмов и программ. В связи с этим в последние десятилетия при производстве сложных программных систем требуется подго-товка высококвалифицированных специалистов, в совершенстве владеющих современной теорией построения систем обработки данных. В этой теории важное место занимают методы органи-зации и обработки данных. Решение любой задачи сводится к обработке множества данных, которые представляют собой аб-стракцию некоторого фрагмента реального мира.
Для решения конкретной задачи, с одной стороны, необходи-мо выбрать подходящий уровень абстрагирования, т.е. опреде-лить множество данных, представляющих реальную ситуацию, относящуюся к задаче. С другой стороны, надлежит выбрать спо-соб представления этих данных с учетом возможностей компью-тера и языка программирования.
Таким образом, для создания программного продукта, реализующего алгоритм решения задачи данной курсовой работы, нам необходимо обладать знаниями теории структур, методов представле-ния данных на логическом (абстрактном) и физическом (машинном) уровнях, а также эффективных алгоритмов обработки различных структур данных.
Также для того, что бы создать действительно эффективно работающую программу, которая даёт нужный результат за нужное время следует провести анализ сложности алгоритма по одному из известных методов. Это позволит избежать создания программного продукта, не отвечающего обязательным требованиям по эффективности программ.
Целью этой курсовой работы является создание программной реализации алгоритма, который находит решения геометрической головоломки: Y-пентамино. Игра "Пентамино" - это очень увлекательное и полезное занятие, развивающее множество способностей. Фигурки представляют собой все односвязные комбинации из пяти квадратиков. Всего в одном наборе 12 фигур. Фигурки можно изготовить из бумаги, картона, пластилина, дерева, глины, или из пластмассы, в общем, из чего угодно. Дальше, берём эти фигурки и начинаем собирать прямоугольную область, размером 6х10 квадратиков. Эта задача достаточно сложна для вычислений вручную, но ЭВМ справляется с ней гораздо быстрее. Основные этапы создания программы, включая процесс разработки алгоритма, выбора языка программирования, анализ сложности алгоритма и программы, приведены ниже.
Главной сложностью, возникающей при разработке алгоритма решения, является применение рекурсии, точнее рекурсивного метода проб и ошибок, с использованием алгоритма с возвратами. Теоретические сведения об этих методах приведены в следующем разделе.
Программный продукт, и сама курсовая работа в целом могут быть применены как в научных целях, при анализе быстродействия систем искусственного интеллекта , так и в более широких целях, например, как программа-помощник, встроенная в основную среду-игру «пентамино». Программы такого рода помогают найти решения головоломок, если пользователь не может сделать этого самостоятельно.
v Теоретические сведения, касающиеся метода
При решении задачи, поставленной в курсовой работе, следует применить два основных алгоритмов перебора: алгоритм с возвратами назад(backtracking) и метод проб и ошибок.
§ Алгоритм с возвратами назад:
Метод перебора с возвратами позволяет решать практически бесчисленное множество задач, для многих из которых не известны другие алгоритмы. Несмотря на такое большое многообразие переборных задач, в основе их решения есть нечто общее, позволяющее применить данный метод. Таким образом перебор можно считать практически универсальным методом переборных решения задач. Приведём общую схему этого метода:
Решение задачи методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его расширить продолжаются.
{ поиск одного решения }
procedure backtracking(k: integer); { k - номер хода }
begin
{ инициализация выбора варианта }
repeat
{ выбор варинта }
if { вариант подходит } then
begin
{ запись варианта }
if { решение не найдено } then
begin
backtracking(k+1); { рекурсивный вызов }
if { решение не найдено } then
{ стирание варианта }
end
else
{ вывод решения }
end;
until { вариантов нет } or { решение найдено }
end;
begin
{ запись первого варианта }
backtracking(1);
end.
К достоинствам схемы следует отнести общность, простоту и логичность. Но она имеет и недостатки. Во-первых, надо самому делать запись первого варианта, неплохо бы, чтобы это делала сама процедура. Также в ней использует цикл repeat: можно допустить ошибку в формировании условия выхода из цикла, особенно, если не знаешь законы де Моргана, к тому же иногда проще использовать цикл for, а если вариантов мало, можно обойтись вообще без циклов. Попытаемся устранить выше приведенные недостатки. Для разработки общей схемы перебора с возвратами воспользуемся процедурой из задачи о лабиринте, просто следует ее обобщить:
{ поиск одного решения }
procedure backtracking(k: integer); { k - номер хода }
begin
{ запись варианта }
if { решение найдено } then
{ вывод решения }
else
{ перебор всех вариантов }
if { вариант подходит } then
backtracking(k+1); { рекурсивный вызов }
{ стирание варианта }
end;
begin
backtracking(1);
end.
Разумеется данная схема также не идеальная, но она устраняет указанные выше недостатки. Также можно соответственно сделать схемы для других классов переборных задач. Сначала схема для поиска всех решений:
{ поиск всех решений }
procedure backtracking(k: integer); { k - номер хода }
begin
{ запись варианта }
if { решение найдено } then
{ запись решения }
else
{ перебор всех вариантов }
if { вариант подходит } then
backtracking(k+1); { рекурсивный вызов }
{ стирание варианта }
end;
Вместо записи решения его можно выводить в выходной файл, либо обрабатывать иным образом в зависимости от условия задачи. Эту схему можно изменить, что находились не все решения, а только одно оптимальное. Под оптимальностью решения обычно понимают, что для данного решения некоторая функция принимает либо максимальное, либо минимальное значение.
Рассмотрим подробнее алгоритм перебора с возвратом на примере известной задачи о восьми ферзях.
Сколькими способами можно расставить 8 ферзей на шахматной доске так, чтобы они не били друг друга? Легенда приписывает формулировку и решение этой задачи "королю математиков" Гауссу. Он первый сумел отыскать все 92 решения.
Решение. В соответствии с описанной ранее общей схемой алгоритма перебора с возвратом предложенную задачу можно было бы решать по приведенному ниже алгоритму “Все расстановки”. По нему ферзи расставляются последовательно на вертикалях с номерами от нуля и далее. В процессе выполнения предписания возможны снятия ферзей с доски (возвраты).
Алгоритм “Все расстановки”
1. Полагаем D = Ж, j = 0 (D - множество решений, j - текущий столбец для очередного ферзя).
2. Пытаемся в столбце j продвинуть вниз по вертикали или новый (если столбец j пустой), или уже имеющийся там ферзь на ближайшую допустимую строку. Если это сделать не удалось, то переходим к пункту 4.
3. j ¬ j+1. Если j < n-1, то переходим к пункту 2. В противном случае j = n-1, то есть все вертикали уже заняты. Найденное частичное решение запоминаем в множестве D и переходим к пункту 2.
4. j ¬ j-1, то есть снимаем ферзь со столбца j и переходим к предыдущему столбцу. Если j і 0, то выполняем пункт 2. Иначе вычисления прекращаем. Решения задачи находятся в множестве D, которое, вообще говоря, может быть и пустым.
§ Метод проб и ошибок:
Рассмотрим этот метод также на примере задачи о восьми ферзях..
Процесс расстановки ферзей может выглядеть так. Поставим первого ферзя на какую-нибудь клетку. Затем поставим второго ферзя на первую клетку и проверим, что ему не угрожает первый. Если угрожает, то передвинем второго ферзя и снова проверим и так до тех пор, пока второй ферзь не окажется на допустимой клетке. Затем будем двигать третьего ферзя и т.д.
В рассматриваемой задаче номером хода i будет порядковый номер ферзя, а номером варианта j -- порядковый номер попытки установить этого ферзя после того, как предыдущие ферзи установлены. Может оказаться, что в ходе расстановки 1-го ферзя все варианты будут неудачными, т.е. мы не сумеем поставить его на доску. В таком случае мы должны будем вернуться на ход назад и установить предыдущего (i - 1)-го ферзя по-другому, т.е. перейти к следующему варианту его расстановки. Очевидно, что для этого надо знать последний рассмотренный вариант установки (i - 1)-го ферзя. Затем увеличиваем номер варианта и продолжаем просмотр вариантов установки этого ферзя.
Итак, процесс расстановки ферзей выглядит следующим образом. Мы движемся вперед, увеличивая номер хода. Для каждого хода движемся вбок, подбирая допустимый вариант, и идем вперед к следующему ходу, если вариант подобран. Если невозможно подобрать вариант, то возвращаемся на ход назад и продолжаем движение вбок, начиная со следующего варианта. После установки последнего ферзя записываем полученное решение. В этих движениях вперед и назад по номерам ходов и состоит особенность схемы перебора.
Рассмотрим пример. Пусть шесть ферзей расставлены на доске, как показано на рис. 4.3, а). Для седьмого ферзя (i = 7) при Просмотре вариантов по клеткам в порядке (1,1), (1,2), ...,(1,8), (2,1), (2,2),... первым подходящим вариантом является клетка (4,7 Установим ферзя на эту клетку. Теперь для восьмого ферзя не окажется подходящего варианта: 7-я горизонталь и 8-я вертикали свободны, но диагональ (8---2) занята клеткой (2--3). Вернемся на ход назад, уберем 7-го ферзя с доски и приступим к его установке на другую допустимую клетку. Просмотр вариантов, начинается с клетки (4,8) и она оказывается допустимой. Установим туда 7-го ферзя и перейдем к следующему ходу -- установке 8-го ферзя. Просмотр вариантов приводит к допустимой клетке (7,7). Все ферзи расставлены, окончательная расстановка показана на рис. 4.3, б).
Как же реализовать рассмотренный алгоритм? Самый простой и самый трудоемкий по времени исполнения -- это метод прямого перебора. Первым ходом поставим ферзя на какую-нибудь клетку, затратив на это единицу времени. Затем в следующем ходе просматриваем 64 возможных вариантов постановки очередного ферзя. Для каждого варианта (i,j), i -- номер горизонтали, j -- номер вертикали, необходимо проверить по 8 клеток i-й горизонтали и j-й вертикали, от 1 до 8 клеток для каждой диагонали, проходящей через клетку (i,j).
Таким образом, число переборов оказывается непомерно великим.Учтем то обстоятельство, что на каждой горизонтали может быть установлен только один ферзь. Поэтому первый ферзь установим на первой горизонтали, второй -- на второй и т.д. Тогда для каждого /-го хода останется всего лишь восемь вариантов постановки ферзя, а проверяться будут клетки только на j-й вертикали и двух диагоналях. Несмотря на это, число проверок остается большим.
Если теперь принять во внимание то, что не только на каждой горизонтали, но на каждой вертикали и каждой диагонали может находиться только один ферзь, число проверок можно существенно сократить. Для этого необходимо иметь информацию о состоянии («занято» -- «свободно») 8 вертикалей, 15 восходящих (слева снизу -- направо вверх) и 15 нисходящих (слева сверху -- направо вниз) диагоналей. С этой целью используем три одномерных массива: а[8] -- состояние вертикалей, Ь[5] --¦ состояние восходящих диагоналей, с[5] -- состояние нисходящих диагоналей. Тогда для каждого варианта (i,j) необходимы только три проверки. Встает вопрос: Как для варианта (i,j) выбирать для проверки элементы массивов а,Ь,с? Последовательный номер элемента а совпадает с номером варианта у. Обратим внимание на то, что для каждой восходящей диагонали сумма (i +J) постоянна: (1 + 1) = 2; (2 + 1) = = (1 + 1) = (1 + 2) = 3 и т.д. (8 + 8) = 16, эти суммы меняются от 2 до 16 (2,3,4,...,15,16), а для каждой нисходящей диагонали постоянна разность (i -j): (8 - 1) = 7; (7 - 1) = (8 - 2) = 6; ...;(1 - 8) = - 7, они меняются от 7 до - 7 (7,6,..., - 6, - 7). Это позволяет для каждого варианта (i,j) однозначно вычислять индексы соответствующих массивов с учетом границ изменения индексов.
Возможны два условия задачи расстановки ферзей: найти одну или все возможные расстановки. Всего имеются 92 различные расстановки, но только 12 из них являются независимыми, остальные можно получить поворотами и зеркальными отражениями доски.
v Алгоритм решения задачи
Словесный (содержательный) алгоритм решения задачи:
Начало
1. Выполнить пункты 2-8; (v1)
2. Если не достигли пределов доски, то выполняем пункт 3,иначе пункт 9; (z1)
3. Если сумма каждого элемента i-ой фигуры пентамино и каждого поля доски, начиная с исходной позиции j, не больше единицы, то пункт 4, иначе пункт 2; (z2)
4. Присваиваем соответствующим элементам доски значение i (т.е. устанавливаем фигуру пентамино на доску); (v2)
5. Если i<12, то пункт 6, иначе 7; (z3)
6. Увеличиваем i на единицу и переход к пункту 2; (v3)
7. Вывод на экран одного решения; (v4)
8. Обнуляем значения i-ой фигуры на доске; (v5)
9. Если j<n, то пункт 1; (z4)
Конец
Словесный алгоритм даёт краткое описание программной реализации решения задачи, и предназначен с общей схемой алгоритма. В частности в нём не рассматривается процесс представления формы каждой фигуры в памяти ЭВМ, так как этот вопрос описывается далее. Также существует неточность по поводу количества циклов, так ка в программе их значительно больше, по причине работы с трёхмерными массивами. Однако для удобства и наглядности, я полагаю, этим можно пренебречь.
v Обоснование выбора структур данных
Прежде чем приступить к разработке алгоритма и созданию программы, нам необходимо иметь представление о способе представления данных в ЭВМ. Поэтому первым вопросом, при разработке программ, является выбор структур данных. В своей программе мне пришлось применить последовательно две структуры для представления в памяти фигур пентамино. Изначально каждая фигура была описана как строка массива geometry. Количество столбцов в этом массиве-25. Именно столько необходимо для представления двумерного массива 5х5. А количество строк соответственно равно 12, так как мы знаем, что всего фигурок двенадцать.
Возможно, возникнет вопрос: «Почему для представления каждой фигуры нужно 25 чисел?» Действительно, это довольно много, но если для каждой фигуры создать отдельный массив со своей “собственной” размерностью, то в памяти необходимо хранить этот массив размерностей для каждой фигуры пентамино и обращаться к ним исключительно по индексам массива. А это помимо того, что неудобно в процессе отладки, к тому же достаточно громоздко и ничуть не экономит память. Вследствие этого, я предпочла иметь константный массив geometry [12][25].
Однако, как уже было сказано, такое представление данных имеется только на начальном этапе работы программы. Если при выполнении рекурсии, в обращение к подпрограмме, в качестве фактических параметров выступает массив, размерностью 12х25, то это чрезвычайно снижает эффективность программы, экономию памяти, а также быстродействие. Несмотря на то, что современная вычислительная система справится даже с наихудшим программным вариантом алгоритма, этот факт стоит учитывать. По этой причине, мне пришлось перевести массив geometry в структуры типа массив записей. Каждая запись массива имеет два поля: массив shape(5x5), в котором представлена форма каждой фигуры и переменная located. Она служит чем-то вроде метки на каждую фигуру, предоставляющей информацию о том стоит ли фигура на доске или нет. С такой структурой данных работать гораздо удобнее так как при рекурсивном вызове процедуры, мы передаём всего лишь текущий элемент массива записей, то есть одну запись.
Опять-таки, вновь возникает вопрос: «Почему нельзя было представить фигуры пентамино в таком виде, не затрачивая лишней памяти на массив geometry?» Это возможно лишь в том случае, если данные вводят с устройства ввода, но это слишком утомительно, так как их объём достаточно велик. Также можно было считывать с файла, но эти способы идентичны по объёму занимаемой памяти. Описывать же каждое поле каждой записи в виде константы не позволяют средства языков программирования, как Turbo Pascal, так и Visual C++.
Говоря о выборе языка программирования, то это вопрос, возникающий сразу после разработки алгоритма. При выборе языка, я руководствовалась выбранным представлением данных, свойствами алгоритма и особенностями задачи. Мой выбор пал на язык С++ в среде Microsoft Visual C++, так как по моим представлениям именно в ней содержится наиболее гибкие средства для обработки различных данных, сколь угодно большого объёма. Описание подпрограмм, написанных на этом языке, даны ниже и содержит три подпрограммы, используемые в программе:
1. Подпрограмма из массива geometry формирует структуру типа массив записей, используемую далее в главной подпрограмме placing:
void forming();
2. Подпрограмма непосредственно реализует метод проб и ошибок с использованием метода backtracking. Осуществляет рекурсивное покрытие прямоугольной области nxm фигурами пентамино и при нахождении каждого решения обращается к функции print:
void placing(int i);
3. Подпрограмма осуществляет вывод на экран различных данных, используемых и полученных в программе:
void print();
Вызов функций forming() осуществляется непосредственно из основной функции main(), функция placing(int i) изначально вызывается в функции main, а затем происходит рекурсивный вызов подпрограммы.
v Программа
Далее приводится непосредственно сам текст исходного кода программы, реализующей алгоритм решения задачи Y-пентамино.
#include<iostream.h>
#include<cmath>
#include"pent.h"
void forming(int geo[12][25]);
void placing(int);
void print(int geo[12][25]);
int main()
{ //массив,в котором каждая строка,реализует представление 1 фигуры
int geometry[12][25]={1,1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,
1,1,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
//структура 1 фигуры
//прямоугольная область размещения фигур
//(в дальнейшем поле расстановки) 6х10
//clrscr(); //очистка экрана
cout<<"beginning dates:"<<endl; //вывод начальных данных
getch(); // ожидание нажатия клавишы
//подпрограмма формирования массива фигур,
//из начального массива geometry
forming(geometry);
// int kol=10; int kol2=0;short b=1;
// int g=-33, h=48;
//основная функция, выполняющая всевозможные расстановки фигур
//на поле расстановки
placing(1);
//вывод данных(поле расстановки) на экран
print(geometry);
getch();
// b ? Print(kol,kol2) : Print(kol,pow(kol,2)+g);
// b ? Prrint(kol,kol2) : Prrint(kol,pow(kol,2)-h);
return 0;
}
//подпрограмма формирования массива фигур,
//из начального массива geometry
void forming(int geo[12][25])
{ struct pents
{ int shape[5][5];//форма фигуры
char located; //находится на доске/не находится
} image[12]; //массив из 12 фигур
int h;
for(int i=1;i<=12;i++) //кол-во фигур
{ h=1;
for(int j=1;j<=5;j++) //размерность каждой фигуры
for(int k=1;k<=5;k++)
//присвоение массиву форматов каждой фигуры,
//значений из нгчальных данных
{ image[i].shape[j][k]=geo[i][h];
h++;
}
}
for(i=1;i<=12;i++)
//пока ни одна фигура не ледит на поле расстановки,
//поэтому значение "N"
image[i].located=N;
}
//основная функция, выполняющая всевозможные расстановки фигур
//на поле расстановки
void placing(int i) //i-номер фигуры
{ const static int n=6,m=10;
struct pents
{ int shape[5][5];//форма фигуры
char located; //находится на доске/не находится
} image[12]; int field[n][m];
//вспомогательные счётчики и
//признак нахождения подходящего варианта
int j1,h1,b;
//цикл нахождения всевозможных вариантов для i-ой фигуры
for(int j=1;j<=n;j++)
{ j1=j;
//просматриваем каждый столбец j-ой строки
for(int h=1;h<=m;h++)
{ h1=h;b=1;
//циклы доступа к элементам массива формата каждой фигуры
for(int k=1;k<=5;k++)
{ for(int l=1;l<=5;l++)
//если сумма элементов массива формы i-ой фигуры
//и элементов массива поля расстановки больше 1
//т.е. происходит наложение фигур друг на друга, то b присвоить значение 0
{ if (image[i].shape[k][l]+field[j1][h1]>1) b=0;
h1++;
}
j1++;h1=h;
}
//если не разу не произошло наложение фигур, т.е. фигура подходит,
//то выход из цикла поиска
//т.е. из цикла возможных исходных позиции фигуры по столбцам
if (b==1) break;
j1=j;
}
if (b==1)
//присваиваем полю расстановки подошедшую нам фигуру
{ for(int k=1;k<=5;k++)
for(int l=1;l<=5;l++)
if (image[i].shape[k][l]==1) field[-j+k][-l+h]=i;
//поменяли признак находится на доске/не находится
image[i].located=Y;
//если это не случай с последней фигурой,
//то рекурсией осуществляем установку след.фигуры
if (i<12) placing(++i);
// else //иначе, т.е. если дошли до посл.фигуры(нашли 1 вариант), вывод на экран
// print();
//обнуляем значения последней поставленной фигуры
//на поле расстановеи и ищем след.подходящий вариант
for(k=j;k<=6;k++)
for(int l=h;l<=10;l++) field[k][l]=0;
//поменяли признак находится на доске/не находится
image[i].located=N;
}
} //выполняем всё вышесказанное для каждой фигуры,
//устонавливая её,находя подходящий вариант и
//удаления для последущего поиска других вариантов
}
//вывод данных(поле расстановки) на экран
void print(int geo[12][25])
{
for(int i=1;i<12;i++){
for(int j=1;j<25;j++) //координаты поля расстановки
cout<<geo[i][j];
cout<<endl;} //непосредственный вывод
//сохранение формата вывода
}
Несмотря на гибкость встроенных средств языка С++ и его неоспоримое удобство при создании программ, он имеет ряд особенностей, часто ведущих к путанице и ошибкам. Добавленные комментарии позволяют избежать этого. По этой причине текст программы богато ими снабжён.
v Тестирование программы
В процессе тестирования программы необходимо следует провести анализ сложности алгоритма и оценку эффективности её работы.
Проведём этот анализ с помощью алгоритмической меры Колмогорова. Для оценки логической сложности алгоритмов предлагается использовать количественную меру в виде полной энтропии (алгоритмической меры количества информации по Колмогорову) двоичной последовательности
Ia(k, s)=n*H(k,s),
где H(k,s) = -((k/n)log(k/n)+(s1/n)log(s1/n)+(s0/n)log(s0/n))
или Н(к,s)= -( (k/n)log(k/n)+2(s/n)log(s/n));
n - общее число выходов безусловных и условных операторов содержательного алгоритма (граф-схемы),
к - число выходов безусловных операторов,
s1, - число «единичных» выходов условных операторов,
S0 - число «нулевых» выходов условных операторов,
s -- число условных операторов (s=s1= s0).
Ia(k, s)=-n((k/n)log(k/n)) бит -- доля логической сложности1 алгоритма по безусловным операторам;
Ij(k,s) = -n(2(s/n)log(s/n))бит-доля логической сложности алгоритма по условным операторам.
Эта формула представляет собой абсолютную логическую сложность алгоритма, измеренную в двоичных единицах (битах).
Вычислим эти значения для нашего алгоритма:
n=13; k=5; s=s1=s0=4;
k/n=0.39; s/n=0.31;
(k/n)log(k/n)=-0.53; (s/n)log(s/n)=-0.52;
Н(к,s)= -(-0.53+2(-0.52))=1.57; I(k, s)=13*1.57=20.41 бит.
Учитывая тот факт, что количество информации, затрачиваемое при реализации алгоритма решения по методу полного перебора, составляет около 28.6, мы можем смело утверждать, что данный алгоритм достаточно эффективен. Несомненно, это не означает, что реализованная по этому алгоритму программа идеальна. Например, её можно было оптимизировать, сократив количество столбцов в массиве geometry на 8, так как последние восемь элементов нигде не используются. Однако, это алгоритмическая мера и многое ещё зависит от реализации алгоритма в программном продукте.
В моей задаче требуется вывести все возможные решения, но несмотря на то, что их не так много, как ожидалось(видимо из-за того, что в условии задачи повороты фигур не предусмотрены), всё-таки это займёт много места. Так как тест программы заключается в выводе меньшего количества результатов, то я приведу несколько примеров вывода для области 6х10 и5х12.
6х10:
1)
1 1 1 2 2 3 4 4 5 5
6 6 1 2 3 3 3 4 4 5
7 6 1 2 2 3 8 8 4 5
7 6 6 9 9 9 10 8 8 5
7 7 9 9 10 10 10 8 11 11
7 12 12 12 12 12 10 11 11 11
2)
9 4 4 7 7 7 7 11 11 11
9 9 4 4 7 2 2 2 11 11
5 9 10 4 3 2 8 2 6 6
5 9 10 3 3 3 8 8 6 1
5 10 10 10 3 8 8 6 6 1
5 5 12 12 12 12 12 1 1 1
3)
11 11 12 10 9 9 9 1 1 1
11 11 12 10 10 10 9 9 6 1
7 11 12 10 4 4 6 6 6 1
7 7 12 4 4 8 6 3 2 2
7 5 12 4 8 8 3 3 3 2
7 5 5 5 5 8 8 3 2 2
5х12:
1)
7 7 7 7 8 8 10 9 9 9 5 5
2 7 2 8 8 1 10 10 10 9 9 5
2 2 2 3 8 1 10 4 4 6 6 5
11 11 3 3 3 1 1 1 4 4 6 5
11 11 11 3 12 12 12 12 12 4 6 6
2)
9 5 5 10 10 10 4 4 6 6 8 8
9 9 5 7 10 4 4 3 2 2 6 8
1 9 5 7 10 4 3 3 3 2 6 8
1 9 5 7 7 11 11 3 2 2 6 8
1 1 1 7 11 11 11 12 12 12 12 12
3)
7 7 7 7 9 10 10 10 8 1 1 1
5 7 4 4 9 9 10 8 8 2 2 1
5 4 4 11 11 9 10 3 8 8 2 1
5 4 11 11 11 9 3 3 3 2 2 6
5 5 12 12 12 12 12 3 6 6 6 6
Как можно заметить, каждая цифра в области означает номер фигуры, которая поставлена на эту клетку. Т. е. если индекс i фигуры в массиве =7, то клетки, занятые этой фигурой отмечаются этой цифрой.
v Заключение
Итак, мы завершили разработку курсовой работы, а именно её главной цели - создание программного продукта, находящего решения головоломки «Y-пентамино». Подводя итоги, можем сделать несколько важных выводов.
1. Применение метода проб и ошибок, вместо обычного полного перебора, позволяет существенно сократить время выполнения программы, а также объём затрачиваемой памяти. Это было выяснено при анализе сложности алгоритма по алгоритмической мере А.Колмогорова. Вычисления показали, что количество информации алгоритма по методу проб и ошибок, значительно меньше, чем у алгоритма прямого перебора.
2. Важной характеристической особенностью разработки программы для решения головоломок является то, что практически невозможно сократить число переборов за счёт рассмотрения отдельных случаев, не имеющих места быть в том или ином случае. В задаче пентамино была только возможность предотвратить рассмотрение замкнутых областей доски, площадь которых меньше или больше пяти(в такие области фигуру уже ставить нельзя, поэтому просматривать её в программе нет смысла - нужно искать другое решение). Однако даже в этом случае существуют такие варианты, при которых ограничение процесса расстановки этим условием ведёт к появлению ошибок. В остальных же случаях, это сделать крайне сложно, так как далеко не все могут не только выявлять закономерности при решении головоломок, но и даже просто решить их.
3. Основная сложность в программе принадлежит представлению данных и непосредственной работе с ними. Все остальные вопросы возникают именно вследствие специфичности исходных данных и результата. Действительно, каждая фигура пентамино есть двумерный массив, а массив фигур представляет собой уже трёхмерный. Это довольно громоздко. И особенно это видно при проверке возможности вставки фигуры в прямоугольную область, когда приходится оперировать с большим числом циклов, чтобы проверить каждый элемент пентамино. В остальном же, а именно в алгоритме нахождения покрытия доски с фигурками пентамино, эта задача мало, чем отличается от той же известной задаче о расстановке восьми ферзей на шахматной доске.
v Список литературы
1. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. - СПб.: БХВ-Петербург, 2003.
2. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си: Учеб. пособие. - Финансы и статистика, 2004.
3. Х.М. Дейтел, П. Дж. Дейтел. Как программировать на С++: Четвёртое издание. Пер. с англ.-- М.: ООО «Бином--Пресс», 2005г.
4. Дж. Макконнелл. Основы современных алгоритмов. 2-е дополненное издание. Москва: Техносфера, 2004.
5. Морозов М. Большая книга загадок и головоломок № 5. Эгмонт Россия Лтд, 2004.
|
