Курсовая работа: Задача Y пентамино

Широкое распространение идей структурного программирования в последние 20-30 лет оказало большое влияние на теорию и практику программирования и привело к пересмотру роли типа и структуры данных при разработке соответствующих алгоритмов и программ. В связи с этим в последние десятилетия при производстве сложных программных систем требуется подго­товка высококвалифицированных специалистов, в совершенстве владеющих современной теорией построения систем обработки данных. В этой теории важное место занимают методы органи­зации и обработки данных. Решение любой задачи сводится к обработке множества данных, которые представляют собой аб­стракцию некоторого фрагмента реального мира.

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

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

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

Целью этой курсовой работы является создание программной реализации алгоритма, который находит решения геометрической головоломки: Y-пентамино. Игра "Пентамино" - это очень увлекательное и полезное занятие, развивающее множество способностей. Фигурки представляют собой все односвязные комбинации из пяти квадратиков. Всего в одном наборе 12 фигур. Фигурки можно изготовить из бумаги, картона, пластилина, дерева, глины, или из пластмассы, в общем, из чего угодно. Дальше, берём эти фигурки и начинаем собирать прямоугольную область, размером 6х10 квадратиков. Эта задача достаточно сложна для вычислений вручную, но ЭВМ справляется с ней гораздо быстрее. Основные этапы создания программы, включая процесс разработки алгоритма, выбора языка программирования, анализ сложности алгоритма и программы, приведены ниже.

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

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

-Теоретические сведения, касающиеся метода

При решении задачи, поставленной в курсовой работе, следует применить два основных алгоритмов перебора: алгоритм с возвратами назад(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 из них являются независимыми, остальные можно получить поворотами и зеркальными отражениями доски.

-Алгоритм решения задачи

--> ЧИТАТЬ ПОЛНОСТЬЮ <--