Алгоритм идентификации объектов, основанный на одновременном анализе их положения в графе

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Алгоритм идентификации объектов, основанный на одновременном анализе их положения в графе

И.Г. Этко

Аннотация. В данной статье представлен алгоритм идентификации объектов, основанный на одновременном перемещении этих объектов в вершинах графа и анализе их текущего положения. Рассматривается прототип данного алгоритма - решение задачи идентификации объектов, передвигающихся по k-значному n-мерному кубу, и приводятся преимущества нового алгоритма.

Ключевые слова: алгоритм, идентификация, граф, поиск, объект.

Abstract. This article represents objects identification algorithm based on simultaneous shifting of these objects within the graph nodes and analysis of their current location in graph. Article goes over prototype of present algorithm - identification of objects moving in k-dimensional n-dimensional cube, and adduce advantages of new algorithm.

Key words: algorithm, identification, graph, search, object.

В настоящее время теория графов и программные средства ее реализации находят применение в целом ряде различных практических задач, к которым, в частности, относятся:

· нахождение минимальных путей (практическая значимость алгоритмов находится в области транспортных задач, задачи коммивояжера, некоторых оборонных задач и др.);

· размещение "центров", покрывающих заданную область (примерами таких задач являются задачи размещения радиопередающих станций, АЗС, центров торговли и др.);

· прокладка магистралей минимальной длины и/или стоимости (примерами задач данного типа являются прокладки: дорог, нефте- и газопроводов, линий электропередач, линий связи и др.).

В работе А.С. Нагорного [1] представлено решение задачи идентификации объектов, передвигающихся по k-значному n-мерному кубу (графу), основное содержание которого сводится к следующему.

В качестве исходных данных известны:

1) ориентированный граф, вершины которого помечены упорядоченными наборами , где (дуги проводятся во всех парах вершин вида и от первой ко второй), и других дуг нет.

2) s объектов , каждый из которых имеет свой номер b и находится в определенной вершине куба , причем в любой момент в каждой вершине находится не более одного объекта (такая расстановка объектов на кубе называется позицией).

На каждом шаге алгоритма разрешается выбрать один объект по номеру (например, объект b) и дать ему одну команду вида move(b, j, d) - «объекту b переместится в соседнюю по j-й координате вершину в направлении d ( - по убыванию или по возрастанию j-й координаты)» Результатом выполнения такой команды будет следующее. Если перемещение, указанное в команде, возможно (т.е. нужная соседняя вершина существует и не занята другим объектом), то это перемещение объекта b происходит, и во внешнюю среду (т.е. устройству, выполняющему алгоритм) возвращается условный сигнал Ok. Если же перемещение, указанное в команде, невозможно (т.е. нужная вершина либо не существует, либо занята другим объектом), то объект b остается на своем прежнем месте, а во внешнюю среду возвращается сигнал Er, отличный от Ok и не зависящий от причины отказа. В любом случае положение остальных объектов (с номерами, отличными от b) в результате указанной команды не меняется.

Требуется, используя описанные выше команды move выяснить позицию s объектов в некоторый момент времени.

Решение задачи, представленное в указанной работе, сводится к следующему утверждению:

«Задача идентификации s объектов на кубе неразрешима при и разрешима при , причем в последнем случае она требует не более

команд, где

».

Возможная программная реализация этой задачи приведена в работе [2].

В данной статье представлен модифицированный алгоритм идентификации передвигающихся по графу объектов, основанный на одновременном анализе положения всех объектов в графе. Рассматривается следующая модель взаимодействия объектов. Всем объектам, размещенным в вершинах графа , одновременно дается команда вида move(j, d) - «всем объектам переместиться в соседнюю по j-й координате вершину в направлении d» (- направление движения, т.е. по убыванию или по возрастанию j-й координаты). В зависимости от того, сумел ли объект b переместиться в требуемом направлении или нет, он возвращает во внешнюю среду сигнал Ok или Er. Одновременно с получением ответа от объекта формируется запись вида b_j_d_Okили b_j_d_Er соответственно. Таким образом, после определения текущего положения объектов можно восстановить и их исходное положение.

Реализация указанных принципов представлена на приведенной в статье схеме алгоритма (рис. 1).

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Рис. 1

Будем называть алгоритмом - безусловный алгоритм, состоящий из

последовательных команд:

move(2,+); move(1,+) … move(2,+); move(1,+); move(1,-) … move(1,-).

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

Пусть ? коэффициент распознаваемости алгоритма , . Тогда

.

алгоритм граф идентификация программный

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

Локальный безусловный алгоритм реализуется пятью командами: move(1,2,-), move(1,2,+) ,move(2,2,-), move(2,2,+),move(1,1,+) и в комплексе с алгоритмом определяет все позиции двух объектов в графе , обеспечивая тем самым решение поставленной задачи.

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

Литература

1. Нагорный А.С. О сложности задачи идентификации объектов, передвигающихся по кубу // Синтез и сложность управляющих систем. Материалы XIII международной школы семинара, часть II (Пенза, 14-20 октября 2002г.). - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. - С. 172-176.

2. Этко И.Г. Принципы организации программного обеспечения идентификации положения объектов на вершинах графа // Информатизация образования. Материалы международной научно-практической конференции (Елец, 28-31 мая 2005г.). - Елец: Елецкий государственный университет им. И.А. Бунина, 2005. - С. 208-212.

Размещено на Allbest.ru