Автор: Шатохина Н.К., Кузнецов Ю.А.
Источник: Сучасні тенденції розвитку інформаційних технологій в науці, освіті та економіці / Матеріали VIII Всеукраїнської науково-практичної конференції. – Луганськ, ДЗ „ЛНУ імені Тараса Шевченка” – 2014. – С. 124–126.
Шатохина Н.К., Кузнецов Ю.А. О задаче выхода агента на границу графа мозаичной структуры с дырами. В данной работе представлен новый алгоритм выхода на границу графа агента, который поставлен в случайную вершину графа мозаичной структуры с дырами.
В предложенной работе рассматривается тематика, связанная автоматным анализом геометрических сред, графов, изображений. Этой тематике посвящено большое количество работ, например [1, с. 305-360], [2, с. 3-28].
Одной из задач этой тематики является нахождения выхода из графа-лабиринта автоматом-агентом (далее агентом).
В данной работе рассматривается лабиринт специального вида, представленный плоским неориентированным графом мозаичной структуры, состоящей из правильных треугольников. Работа является продолжением исследований, описанных в [3, с. 111-121]. В качестве усложнения модели объекта используется неориентированный плоский граф мозаичной структуры с дырами. Моделью дыры проанализирован случай отсутствия одного из ребер любой из внутренних вершин.
Рассмотрены следующие свойства агента. Располагаясь в вершине, он может воспользоваться ее локальной информацией – степенью вершины и может определить степени смежных с ней вершин, может выполнять повороты по и против часовой стрелки, перемещаться в следующей вершине по ребрам и определять направление своего перемещения.
После постановки агента на произвольную вершину графа ему необходимо выйти на границу графа.
1. Агент помещается случайным образом в произвольную вершину графа.
2. Проверяем степень вершины, на которую попал агент и степени смежных с ней вершин.
3. Если степень текущей вершины меньше пяти, то это граничная вершина графа. Алгоритм заканчивает работу.
4. Если хотя бы у одной из вершин смежных с текущей вершиной степень меньше пяти, то рассматриваемая вершина является граничной вершиной графа и переходим на неё. Алгоритм заканчивает работу.
5. Если степень текущей вершины равна шести или пяти и присутствует диаметрально противоположное ребро относительно первого встречного ребра, то переходим на следующую вершину. Дальнейший анализ производится, начиная с пункта 2.
6. Если диаметрально противоположное ребро отсутствует, то это дырка и её требуется обойти для продолжения алгоритма.
Алгоритм обхода дырки:
- Относительно диаметрально противоположного ребра один поворот почасовой стрелке и переход на следующую вершину.
- Относительно ребра, по которому перешли на данную вершину два поворота против часовой стрелки и переход на следующую вершину по текущему ребру.
- Относительно ребра диаметрально противоположного ребру, по которому перешли на текущую вершину один поворот по часовой стрелке и переход на следующую вершину.
- Дальнейший анализ производится, начиная с пункта 2.
Действия повторяются, пока агент не выйдет на границу графа.
Показано, что суммарная временная сложность этого алгоритма в худшем случае оценивается как О(4n/5-9).
1. Levitt T., Lawton D.N. Qualitative navigation for mobile robots// Artificial Intelli-gence, 1990, v.40, p. 305-360.
2. В.Б. Кудрявцев, Ш. Ушчумлич, Г. Килибарда. О поведении автоматов в лабиринтах // Дискретная математика.-1992.-Т.4, вып.3.- С.3-28.
3. Шатохина Н.К., Шатохин П.А. Распознавание графа мозаичной структуры коллективом агентов. // Наукові праці Донецького національного технічного універсітету. Серія: Проблеми моделювання та проектування (МАП2011), випуск 9(179). Донецьк, ДонНТУ, 2011. С. 111-121.