-Введение
Широкое распространение идей структурного программирования в последние 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, б).