Реферат: Задача Y- пентамино
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:
voidplacing(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<<«beginningdates:»<<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);
return0;
}
//подпрограмма формирования массива фигур,
//из начального массива 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(intj=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 1210 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 1212 1 1 1
3)
11 11 12 10 9 9 9 1 1 1
11 11 12 10 10 109 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 1010 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.
/>/>/>