Основу многих алгоритмов обработки сетевой информации составляют алгоритмы обхода (итерации) графов, в процессе которых производится поиск необходимой информации или определение каких-либо характеристик сети. Теория графов, как самостоятельная математическая дисциплина, сформировалась в тридцатые годы двадцатого века и нашла широкое применение во многих разделах науки и техники. Методы теории графов успешно используются в теории информации, планировании производства, генетике и химии, на транспорте, в маршрутизации данных в интернете и многих других областях науки, техники и общественной жизни. Теория графов является основным инструментом обработки таких интересных объектов, как лабиринты.
Исторически сложилось так, что лабиринты вначале имели мистико-аллегорический статус, затем использовались в качестве элементов садово-парковой культуры и практически не рассматривались как интересный математический объект. Все изменилось во второй половине XX века. Развитие робототехники, проблемы, связанные с автоматизацией проектирования электроники, – все это заставило человечество по-новому взглянуть на лабиринты, увидеть их математическую сущность, рассматривать их как математический объект и в полной мере оценить их практическую важность.
В дальнейшем используются следующие понятия и определения:
- Лабиринт – это какая-либо структура, которая располагается в двухмерном или трехмерном пространстве и состоит из запутанных путей к выходу. Данные пути представляют собой некоторую последовательность локаций;
- Локация – это входящее в состав лабиринта помещение, имеющее не более четырех соседних помещений, в каждое из которых может вести проход, причем только один. В случае отсутствия прохода, локации отделены друг от друга стеной;
- Решение лабиринта – это поиск маршрута, соединяющего некоторую начальную (стартовую) локацию и отличную от нее конечную (финальную).
В отношении лабиринтов можно условно выделить две фундаментальные проблемы, решение которых позволяет применять лабиринты в выше обозначенных прикладных областях: проблема построения лабиринта и проблема поиска пути в лабиринте. Инструментарий для решения данных задач предоставляет такая область математической науки как дискретная математика, имеющая в своем составе теорию графов, на основе положений которой можно формализовать лабиринт с целью его дальнейшей обработки.
Лабиринт можно рассматривать как совокупность трех множеств. Первое множество включает в себя множество локаций, которые содержит лабиринт. С точки зрения теории графов, это множество вершин графа. Вторым множеством является некоторое конечное множество ребер – проходов между локациями. Третье множество ставит паре локаций в соответствие некоторый проход, соединяющий данные локации, причем только один. Следовательно, лабиринт можно представить в виде графа.
На основе положений теории графов можно провести формализацию лабиринта, которая будет заключаться в определении класса графов, представителем которого является произвольный лабиринт.
Прежде всего, необходимо определить, обязан ли лабиринт являться связным графом, т.е. можно ли связать цепочкой ребер любые две вершины данного графа. Предположим, что это утверждение истинно. Следовательно, не могут существовать лабиринты, которые не имеют решения для некоторой пары точек (локаций). С другой стороны, определение лабиринта не исключает возможности того, что для двух произвольных точек может не существовать маршрута, их соединяющего, что, фактически, приводит к противоречию. Отсюда можно сделать вывод: граф, являющийся формализацией произвольного лабиринта, не является связным.
Теперь следует проверить, является ли граф орграфом или ориентированным графом, т. е. графом, для которого задано направление всех ребер (дуг). Проход, которому ставится в соответствие ориентированное ребро, может быть пройден только в выбранном направлении. Но определение локации не содержит требования о невозможности прохождения одного и того же ребра в разных направлениях, что порождает очередное противоречие. Значит, граф, описывающий произвольный лабиринт, является неориентированным – все его ребра не имеют направления.
Осталось выяснить, может ли граф содержать кратные ребра (различные ребра, соединяющие одинаковые вершины) или петли (ребра, у которых совпадают начало и конец). Произвольная локация лабиринта, соответствующая данному выше определению, не может содержать прохода, ведущего в эту же локацию. Таким образом, граф не может содержать петель. Наличие кратных ребер подразумевает наличие между локациями двух и более проходов, что также противоречит выше приведенному определению локации. Таким образом, можно заключить, что граф произвольного лабиринта является простым, т. е. не содержит петель и кратных ребер, и неориентированным.
Проведенная формализация лабиринта ставит ему в соответствие некоторый граф. Кроме того, по имеющемуся графу можно восстановить лабиринт, которому он соответствует. В связи с этим, проблему генерации лабиринта можно свести к проблеме генерации псевдослучайного графа заданного размера и заданных свойств. В свою очередь, проблему генерации псевдослучайного графа можно упростить и свести к проблеме генерации минимального остового дерева. Из этого следует, что допустимо использование алгоритмов Р. Прима (Robert C. Prim) и Д. Краскала (Joseph B. Kruskal) для генерации минимального остового дерева, но с небольшими модификациями, которые связаны с тем, что граф, лежащий в основе лабиринта, не является взвешенным (это следует из того, что в определении локации не указана «стоимость прохода» по тому или иному маршруту), в то время как исходные алгоритмы Прима и Краскала рассчитаны на взвешенные графы.
Рассмотрим алгоритм Краскала. В начале работы данного алгоритма имеется множество не связанных между собой точек, каждая из которых является вершиной будущего графа и множество локацией будущего лабиринта. Каждая из вершин будущего графа образует подграф. Таким образом, в самом начале работы алгоритма имеется граф, состоящий из N-подграфов, не связанных между собой. Конечной задачей является построение N–1 ребра таким образом, чтобы в результате получился полностью связный граф, из любой вершины которого существует маршрут в любую другую вершину.
Для решения задачи необходимо выяснить, каким именно образом нужно соединять вершины ребрами. В случае тривиального графа, содержащего всего две вершины, их соединение возможно единственным ребром. Данный случай можно рассматривать в качестве базового. Если количество вершин в графе больше чем две, множество вершин необходимо разбить на два подмножества, каждое из которых примерно в два раза меньше исходного. После этого, если в получившихся множествах оказалось более чем по две вершины, следует провести разбиение каждого из имеющихся подмножеств на два еще меньших подмножества. Разбиения проводятся до тех пор, пока не получится некоторое количество подмножеств, содержащих не более чем две вершины будущего графа, для которых выполняются построения базового случая. Далее множества попарно объединяются путем соединения получившихся пар подграфов одним ребром. Пары подграфов соединяю до тех пор, пока в результате не останется один единственный граф, который и будет являться минимальным остовым деревом для заданного множества точек. В случае с лабиринтами будет получен граф, соответствующий некоторому лабиринту, содержащему N локаций.
Алгоритм может быть упрощен следующим образом. Изначально по-прежнему имеется N вершин, каждая из которых является графом. Соединяются две произвольные вершины и тем самым количество подграфов уменьшается на единицу. До тех пор, пока не останется ровно один подграф, т. е. пока не будет построен связный граф, содержащий N вершин, выбирается случайная вершина А, которая соединяется с другой произвольной вершиной B. При этом между вершинами А и B не должно существовать пути – в противном случае граф перестанет быть минимальным, т. к. одно из ребер будет потрачено не на добавление новой вершины, а на образование цикла (на соединение двух вершин, уже встроенных в конечный граф).
Задача решения лабиринтов может быть решена следующим образом. Решение лабиринта относительно двух его локаций – это маршрут, соединяющий две данные локации. К настоящему времени разработано большое количество различных алгоритмов, предназначенных для решения лабиринтов. Остановимся на одном из них, который был первоначально открыт в 1956 году в рамках задачи о решении лабиринтов Э. Ф. Муром (E. P. Moore), а также независимо открыт Ч. Ли (C. Y. Lee) при формализации алгоритмов трассировки печатных плат (1961 г.). Речь идет об алгоритме волновой трассировки, известном как алгоритм Ли.
По отношению к имеющемуся графу, описывающему лабиринт, данный алгоритм может быть представлен следующим образом. Начальная вершина, из которой будет начинаться поиск, помечается некоторым числом a (как правило – нулем), после чего все вершины, имеющие ребра, общие с начальной вершиной, получают метку на единицу большую. На следующем шаге алгоритм последовательно перемещается в каждую из вершин, имеющих метку a+1, и ставит метки всем связанным с данной, но еще не отмеченным вершинам. Процесс продолжается до тех пор, пока не будет отмечена искомая вершина, или пока не будут отмечены все доступные вершины. В случае, если достигнут второй результат, а искомая вершина так и не получила метку, говорят, что нет решения для двух данных точек, т. к. не существует маршрута, который включал бы их обеих. В случае, если искомая вершина получила некоторую метку b, алгоритм прекращает расстановку новых меток и перемещается в искомую вершину. Поскольку все вершины, которые входят в маршрут, соединяющий начальную и конечную вершины, имеют некоторые метки, лежащие в интервале (a, b), можно восстановить маршрут, действуя следующим образом.
Запомнить вершину, имеющую метку b, после чего выбрать вершину, имеющую метку b-1, переместиться в нее и запомнить эту вершину. После этого выбрать новую вершину, имеющую метку на единицу меньше, переместиться в нее и также запомнить. Подобные действия совершаются до тех пор, пока не будет достигнута точка, имеющая метку a. В результате вершины, которые были запомнены во время обратного движения, будут составлять искомый маршрут.
Реализация основных составляющих данного алгоритма на языке программирования C++, может выглядеть следующим образом:
1) присваивание меток всем вершинам графа происходит до тех пор, пока существуют неотмеченные вершины, которым можно присвоить метку, и искомая вершина остается неотмеченной:
do
{
/* stop – сигнализирует о том, что больше нет ячеек, которым можно присвоить метку.
max_x, max_y – максимальные координаты локаций лабиринта.
cMaz – матрица, хранящая информацию о локациях и окружающих их стенах.
d – текущая метка.
dx, dy – массивы, использующиеся для просмотра соседних с данной локаций.
ix, iy – координаты очередной локации, соседней с данной.
*/
stop = true;
for (x = 0; x < max_x; ++x)
{
for (y = 0; y < max_y; ++y)
{
if (cMaz[x][y] == d)
{
for (k = 0; k < 4; ++k)
{
int ix = x + dx[k];
int iy = y + dy[k];
if(ix >= 0 && ix < max_x && iy >= 0 && iy < max_y && cMaz[ix][iy] == -2)
{ cMaz[ix][iy] = d+1;
stop = false;
}}}}}
d++;
}while (!stop && cMaz[end_x][end_y] == -2);
2) проверка, помечена ли конечная ячейка. Если нет – функция поиска пути возвращает -1 как код ошибки, и зарезервированная память освобождается:
if (cMaz[end_x][end_y]==-2)
{
for (int i=0; i< max_x; i++)
delete[] cMaz[i];
delete[] cMaz;
for (int i=0; i<max_x*max_y, i++)
delete[] path[i];
delete[] path;
return -1;
}
3) в противном случае происходит восстановление пути:
d=cMaz[end_x][end_y];
len=d;
x=end_x;
y=end_y;
while (d>0)
{
path[d][0]=x;
path[d][1]=y;
d–;
for (k=0; k<4; k++)
{
int ix=x+dx[k];
int iy=y+dy[k];
if (ix>=0&&ix<max_x&&iy>=0&&iy<=max_y&&сMaz[ix][iy]==d)
{
x=x+dx[k];
y=y+dy[k];
break;
}}}
4) высвобождается зарезервированная память, и функция прекращает свою работу.
Проведенная формализация понятия лабиринта, как математического объекта в теории графов и рассмотренный алгоритм позволяют решать многие важные и интересные задачи, связанные с генерацией и решением лабиринтов [1]. Проблемы, связанные с данной тематикой, в том числе генерация и, особенно, решение лабиринта, меняющегося при каждом движении в нем, а также программное прохождение лабиринта в условиях ограниченного обзора, детально рассмотрены не были, что оставляет возможность дальнейших изысканий в этой области. Еще одно направление развития данной темы связано со сравнительным анализом различных алгоритмов генерации и решения лабиринтов.
Представленные сведения носят универсальный характер и могут служить дидактическими материалами в ходе организации обучения будущих программистов при рассмотрении вопросов программирования алгоритмов обхода графов.
Библиографический список
- Мартынюк Ю.М., Использование математического моделирования при обучении программированию/Мартынюк Ю.М., Ванькова В.С., Ваньков Б.П. // Современная педагогика. 2014. № 11 (24). С. 41-44.