О задаче выхода агента на границу графа мозаичной структуры с дырами

Аннотация

Шатохина Н.К., Кузнецов Ю.А. О задаче выхода агента на границу графа мозаичной структуры с дырами. Рассмотрена проблема анализа дискретных структур, представленных графом специального вида. В частности, рассмотрена задача выхода агентом на границу графа и обхода его по граничным вершинам, в котором могут присутствовать дыры. Описан алгоритм решения задачи, приведена оценка его временной сложности.

Постановка проблемы. В предложенной работе рассматривается тематика, связанная автоматным анализом геометрических сред, графов, изображений[1]. Аналогичные задачи возникают при разработке ПО для использования, например, в робототехнике или молекулярной физике: построение модели карты среды, модели объекта. Этой тематике посвящено большое количество работ, например [2], [3], [4].

В данной работе рассматривается лабиринт специального вида, представленный плоским неориентированным графом мозаичной структуры, состоящей из правильных треугольников. Работа является продолжением исследований, описанных в [5]. В качестве усложнения модели объекта используется неориентированный плоский граф мозаичной структуры с дырами.

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

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

Постановка задачи исследования. Разработать алгоритм выхода агента на границу графа мозаичной структуры, в котором присутствуют дыры и алгоритм описания границы графа. Оценить временную сложность алгоритма для передачи информации следующему автомату. Основные определения и обозначения. В данной работе рассматривается неориентированный граф G без петель и кратных ребер. В графе может присутствовать одна или несколько дыр. Для графа G(V,E), где V – множество вершин, E={(vi,vj)|(vi,vj)}∈V – множество ребер, заданы такие ограничения, описывающие его мозаичную структуру:
1) для всех v∈V выполняется соотношение 1≤deg(v)≤5;
2) длина всех ребер е=(v1,v2)∈Е постоянна, |e|=const.

Моделью дыры проанализирован случай отсутствия одного из ребер любой из внутренних вершин сильно связного графа.

Степень вершины — количество рёбер графа G , инцидентных вершине v.

Граф называется сильно связным, если для любых двух v, w его вершин существует маршрут (v,v2),(v1,v2),…, ( vn-1,w), связывающий эти вершины.

Обозначим множество инцидентных ребер вершины v через E(v)={e1,},|E(v)|≤5. На E(v) определим функцию q: E(v)∪H={a,b,c,-a,-b,-c}. Множество Н описывает метки инцидентных ребер вершины v, расставляя их смежным ребрам в порядке поворота на угол 60 против часовой стрелки относительно некоторого случайно взятого ребра. Знак «-» перед а означает, что ребро является диаметрально противоположным ребру а. Можно также интерпретировать Н как множество {x, x+1, x+2, x+3, x+4, x+5}, степень букв обозначает количество поворотов против часовой стрелки на угол 60° относительно ребра х. Как видим, функцию q можно интерпретировать как направление, так и угол поворота относительно некоторого ребра.

Свойства системы перемещений.

Любое перемещение агента по любому ребру (операция перемещения) можно представить свободным вектором, имеющим начало - в некоторой вершине v, конец – в вершине w, а х= q(v,w) задает направление свободного вектора. Другими словами между свободными векторами и направлениями, определяемыми функцией q, имеет место взаимно однозначное соответствие, поэтому данный вектор будем обозначать буквой х. В качестве нулевого вектора, будем рассматривать вектор, у которого начало и конец совпадают, тогда х+0=х.

Свойства агента.

Рассмотрены следующие свойства агента.

1. Располагаясь в вершине, он может воспользоваться ее локальной информацией – степенью вершины.
2. Располагаясь в вершине, он может определить и хранить в пямяти степени вершин смежных с текущей вершиной.
3. Располагаясь в вершине, он может выполнять повороты по и против часовой стрелке.
4. Перемещаться к следующей вершине по ребрам.
5. Определять направление своего перемещения.

При перемещении по границе графа агент выполняет следующие действия.

1. Первую встреченную граничную вершину агент метит.
2. При передвижении по границе он фиксирует строку букв, соответствующих выбранным направлениям и сохраняет в строку для последующей передаче следующему агенту.
3. Агент прекращает работу, как только встретит ранее отмеченную вершину.

Обход графа.

Процесс обхода графа состоит из двух шагов:

• выход на границу графа с учётом дыр;
• обход границы графа и передача полученной информации, для работы следующего агента.

Алгоритм выхода агента на границу графа.

После постановки агента на произвольную вершину графа ему необходимо выйти на границу графа.

1. Агент помещается случайным образом в произвольную вершину графа v.
2. Агент проверяет степень вершины, на которую попал.
3. Если степень вершины, на которую попал агент меньше пяти, то это граничная вершина. Алгоритм заканчивает работу.
4. Агент проверяет степени вершин смежных с текущей вершиной.
5. Если хотя бы у одной из смежных вершин степень меньше пяти, то рассматриваемая вершина является граничной и переходим на неё. Алгоритм заканчивает работу.
6. Если степень текущей вершины равна шести или пяти и присутствует диаметрально противоположное ребро относительно первого встречного ребра, то переходим на следующую вершину. Дальнейший анализ производится, начиная с пункта 2.
7. Если диаметрально противоположное ребро отсутствует, то это дырка и выполняется алгоритм обхода дырки.
8. Действия повторяются, пока агент не выйдет на границу.

Алгоритм обхода дырки.

1. Относительно диаметрально противоположного ребра один поворот почасовой стрелке и переход на следующую вершину.
2. Относительно ребра, по которому перешли на данную вершину два поворота по часовой стрелке и переход на следующую вершину по текущему ребру.
3. Относительно ребра диаметрально противоположного ребру, по которому перешли на текущую вершину два поворота по часовой стрелке и переход на следующую вершину.
4. По ребру диаметрально противоположному отсутствующему переходим в следующую вершину.
5. Дальнейший анализ производится, начиная с пункта 2 общего алгоритма.

Временная сложность алгоритма рассчитывается на основании количества подсчётов степеней вершин требуемых для выхода агента на границу графа.

Показано, что суммарная временная сложность этого алгоритма в худшем случае оценивается как О(4n/5-9).

Алгоритм обхода графа по граничным вершинам.

После выхода на вершину графа агенту требуется описать границу графа. Во время выполнения алгоритма агент движется против часовой стрелки.

1. После получения вершины, на которую вышел агент в результате предыдущего алгоритма, агент, поворачиваясь против часовой стрелки на 60°, находит первое встречное ребро.
2. Агент помечает ребро, фиксируя букву-направление своего перемещения, и переходит на следующую вершину.
3. Агент находит следующее ребро и если оно ещё не помечено переходит на него, иначе конец алгоритма.
4. Действия повторяются до тех пор, пока агент не обойдёт весь граф.

Показано, что временная сложность алгоритма оценивается как O(n).

Выводы. В данной работе предложен алгоритм выхода агента на границу графа мозаичной структуры, в котором могут присутствовать дыры. Так же предложен алгоритм обхода графа по граничным вершинам. Далее предполагается разработать алгоритм описания и восстановления графа мозаичной структуры с дырами.

Список использованной литературы

1. Капитонова Ю.В. Математическая теория проектирования вычислительных систем/ Ю.В.Капитонова, А.А.Летичевский.-М.:Наука,1998.-296 с.

2. Levitt T., Lawton D.N. Qualitative navigation for mobile robots// Artificial Intelligence, 1990, v.40, p. 305-360.

3. В.Б. Кудрявцев, Ш. Ушчумлич, Г. Килибарда. О поведении автоматов в лабиринтах // Дискретная математика.-1992.-Т.4, вып.3.- С.3-28.

4. Шатохина Н.К., Шатохин П.А. Распознавание графа мозаичной структуры коллективом агентов. // Наукові праці Донецького національного технічного універсітету. Серія: Проблеми моделювання та проектування (МАП2011), випуск 9(179). Донецьк, ДонНТУ, 2011. С. 111-121.