Реализация головоломки “Пятнашки” с алгоритмом сбора

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ МОСКОВСКОЙ ОБЛАСТИ

«Университет «Дубна»

ИНСТИТУТ СИСТЕМНОГО АНАЛИЗА И УПРАВЛЕНИЯ

Кафедра распределенных информационно-вычислительных систем

КУРСОВАЯ РАБОТА

по дисциплине

«Объектно-ориентированное программирование»

[pic 1]

ТЕМА: _________________________________________________________________[pic 2]

                       (наименование темы)

[pic 3]

Выполнил: студент группы _________ [pic 4]

____________________________________

(Ф.И.О.)

Руководитель:

____________________________________[pic 5]

(ученая степень, ученое звание, занимаемая должность, ФИО)

Дата защиты:_________________________

Оценка:_____________________________

Подпись:____________________________

Дубна, 2022

Содержание

Введение        3

Задание на работу        6

Теоретическая часть        7

Практическая часть        11

Заключение        13

Список литературы        14

Введение

В качестве проекта для курсовой работы была выбрана реализация головоломки “Пятнашки” с алгоритмом сбора. Написать приложение – головоломку, в котором будет предусмотрен алгоритм для её решения. Данный алгоритм будет просчитывать решение и выводить последовательность шагов, которые нужно сделать, чтобы прийти к решению головоломки, пользователю на экран. Пользователю останется только передвигать определенные числа, чтобы привести головоломку к собранному состоянию. Изначально, задачей было создание игры с возможностью выбора поля (квадратного), с реализацией алгоритма, который сможет искать решение на полях разных размеров. Реализовать головоломку было не сложно, необходимо представить массив чисел (одномерный или двумерный, отличия будут только в способах работы с числами, перемещениями, обращением к конкретному числу) и “связать” его с визуальным представлением на экране, чтобы пользователь мог взаимодействовать с ними – передвигать числа. Решать головоломку задача сложней. Изначально были попытки “создать” алгоритм, из тех действий, которые совершаются, если решать головоломку. В качестве примера рассмотрим головоломку размера 3x3. Имеется произвольная, решаемая конфигурация поля. Решаемая – означает, что допустимыми перестановками её можно привести к упорядоченному виду расположения чисел слева-направо сверху-вниз в порядке возрастания с пустой клеткой в правом нижнем углу. Для того, чтобы решить, необходимо последовательно приводить числа на свои места начиная с верхнего ряда. Самым первым действием, находится число “1” и сверяется его положение, если данное число не стоит на своем месте (левый верхний угол), то допустимыми перестановками данное число передвигается на свое место. После числа “1”, совершаются те же действия с числом “2”. Установка последнего числа в ряду, в данном примере числа “3”, будет сложней. Для этого, необходимо отодвинуть предпоследнее число, то есть “2” и держать его рядом с “3”. И по порядку устанавливать числа. Необходимо поставить на свое место “3” и сразу после этого вернуть на место число “2”. После данных действий верхний ряд будет собран. Для сбора других рядов верхний ряд уже не понадобится. Данные шаги необходимо совершать до тех пор, пока не останется последние 2 рада. В данном примере после первого, сразу идут последние два ряда – ряд 2 и рад 3. Их собирать сложней. Необходимо устанавливать парами числа на свои места слева-направо. Устанавливая сразу и на последний и на предпоследний ряд. Например, сначала нужно установить 7 и 4, далее 8 и 5. Но продолжать до тех пор, пока не останется 4 ячейки (две ячейки на предпоследним ряду и две на последним). В тех ячейках останется 3 числа, которые устанавливаются на свои места прокруткой по/против часовой стрелке. Данным способом решается головоломка разных размеров. Смотря на данный способ, даже в последовательном виде, очень сложно представить, как его конкретно реализовать с четко расставленными шагами. Может быть это и возможно, но скорей всего он получится не универсальный и придется для каждого размера поля переписывать алгоритм с корректировкой размера поля. Скорей всего данный алгоритм будет не эффективный и вряд ли получится реализовать. Поэтому было принято решение искать готовые алгоритмы или способы решения данной задачи. Позже способ был найден. Он заключается в представлении задачи (решения головоломки) в виде поиска пути на графе. По данному способу, чтобы решить задачу необходимо свести её к графу и найти решение. Потребовалось довольно много времени, чтобы понять, как данную задачу можно представить в виде поиска пути на графе. Была изучена информация касаемо графов, что это совокупность связанных между собой точек (вершин), связями между точками являются ребра. Данная задача очень хорошо решается этим способом. Вся сложность заключается только в представлении графа. Нужно понять, что за стартовую вершину графа необходимо брать имеющуюся конфигурацию поля (стартовую или после каких-либо перестановок, не важно). От данной вершины будут отходить ребра, ребрами будут являться допустимые перестановки, которые можно совершить на стартовой вершине (конфигурации поля). Под допустимыми перестановками стоит понимать ходы, которые можно сделать, то есть нажатие на число и перемещение его на пустую клетку и сдвиг пустой клетки на прошлое место числа. В зависимости от положения пустой клетки перестановок может быть от двух (если пустая клетка стоит в одном из углов) до четырех (если пустая клетка не находится рядом с границей поля). За один ход, можно сделать одну перестановку, следовательно, каждый ход “создает” новую вершину, от которой в дальнейшем так же отходят ребра. Но стоит заметить, что из любой вершины графа, с помощью допустимых перестановок есть возможность прийти в любую вершину графа (если рассматривать решаемую конфигурацию, то из любой решаемой в любую решаемую, так же с нерешаемыми). Теперь необходимо представить в алгоритме данный граф и задать возможность совершать допустимые перестановки на каждом шаге алгоритма и ждать пока алгоритм не придет к решению задачи (целевой вершине, вершине с правильно упорядоченными числами). Но стоит заметить, если представлять задачу данным способом, количество вершин будет очень большое. Можно посчитать и убедиться. В данном примере, размер поля 3x3, следовательно, 9 положений для чисел и пустой клетки. За пустую клетку можно взять “0”. На первом месте может стоять 9 числе, на втором 8, на третьем 7 и так далее. Перемножив все, получается девять факториал вершин. Но из этих девять факториал, решаемыми будут только половина, а другая половина нерешаемыми. Из решаемой конфигурации в нерешаемую с помощью допустимых перестановок перейти нельзя и наоборот. Следовательно, нужно рассматривать 9!/2 вершин, что тоже большое число. И заметить, что из любой вершины можно попасть в любую вершину группы (решаемой или нерешаемой). Рассмотрев все это, можно перейти к поиску алгоритма поиска пути на графе. Существует достаточное количество алгоритмов, изначально был рассмотрен алгоритм поиска в ширину. Суть данного алгоритма заключается в последовательном переборе вершин до тех пор, пока не будет найдена целевая вершина или вершины не закончатся. На вход передается стартовая вершина, проверяется совпадает ли она с целевой или нет, если не подходит, от нее формируются другие вершины (из-за совершения допустимых перестановок) и добавляются в список всех вершин. Рассмотренная вершина добавляется в список рассмотренных вершин, чтобы алгоритм не “шел” назад и не зациклился. На следующем шаге проверяются вершины соседи, предыдущей вершины и до тех пор, пока не будут просмотрены все вершины или не найдется подходящая. Так как количество вершин очень большое, и алгоритм гарантированно пойдет в “сторону” от правильного решения он не эффективен для решения головоломок размеров 4x4 и больше. Даже с размером 3x3 он будет справляться довольно долго. Поэтому был найден другой алгоритм – “Astar”, основная суть которого заключается в поиске в ширину, только данных алгоритм в процессе поиска использует дополнительную информацию, чем является количество ходов и эвристика – приблизительная оценочная стоимость, сколько необходимо ходов, чтобы добраться до целевой вершины. Выбирая на каждом шаге вершину с минимальным значением числа ходов и эвристики алгоритм гарантированно будет двигаться в правильном направлении и достигать цели быстрей поиска в ширину. Выбрав способ представления задачи и алгоритм можно перейти к их подробному рассмотрению.