Идентификация вершин помеченных графов
Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, назв...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2010
|
| Назва видання: | Труды Института прикладной математики и механики |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/123955 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-123955 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1239552017-09-16T03:03:35Z Идентификация вершин помеченных графов Грунский, И.С. Сапунов, С.В. Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, названные ее идентификаторами. Найдены условия существования, оценки сложности идентификаторов и разработаны методы их построения. Разработаны полиномиальные методы построения и проведения экспериментов по определению начальной вершины графа, основанные на построении идентификаторов всех его вершин. Розглянуто задачу визначення мобільним агентом свого положення в середовищі, яке моделюється за допомогою графа з позначеними вершинами. Агент може пересуватися дугами графа та спостерігати позначки вершин. Введено визначення ідентифікаторів вершин, тобто скінченні множини слів в алфавіті позначок, які відрізняють одну вершину графа від усіх інших його вершин. Знайдено умови існування, оцінки складності ідентифікаторів та розроблено методи їх побудови. Розроблено поліноміальні методи побудови і проведення експериментів по визначенню початкової вершини графа, які грунтуються на побудові ідентифікаторів усіх його вершин. The self-location problem for mobile agent in the topological environment is considered. Environment is modeled by the vertex labeled graph. The agent can move by graph edges and observe labels of vertices. A finite sets of words over the vertex labels alphabet distinguishing a given vertex from other called vertex identifier is proposed. Existence conditions and complexity estimations for vertex identifiers are discovered and constructions methods are developed. Polynomial constructions and realizations methods for experiments detecting the vertex where the mobile agent start walking based on all vertices’ identifiers construction are proposed. 2010 Article Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/123955 519.7 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Рассматривается задача определения мобильным агентом своего положения в среде моделируемой графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа от всех других его вершин, названные ее идентификаторами. Найдены условия существования, оценки сложности идентификаторов и разработаны методы их построения. Разработаны полиномиальные методы построения и проведения экспериментов по определению начальной вершины графа, основанные на построении идентификаторов всех его вершин. |
| format |
Article |
| author |
Грунский, И.С. Сапунов, С.В. |
| spellingShingle |
Грунский, И.С. Сапунов, С.В. Идентификация вершин помеченных графов Труды Института прикладной математики и механики |
| author_facet |
Грунский, И.С. Сапунов, С.В. |
| author_sort |
Грунский, И.С. |
| title |
Идентификация вершин помеченных графов |
| title_short |
Идентификация вершин помеченных графов |
| title_full |
Идентификация вершин помеченных графов |
| title_fullStr |
Идентификация вершин помеченных графов |
| title_full_unstemmed |
Идентификация вершин помеченных графов |
| title_sort |
идентификация вершин помеченных графов |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2010 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/123955 |
| citation_txt |
Идентификация вершин помеченных графов / И.С. Грунский, С.В. Сапунов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2010. — Т. 21. — С. 86-97. — Бібліогр.: 9 назв. — рос. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT grunskijis identifikaciâveršinpomečennyhgrafov AT sapunovsv identifikaciâveršinpomečennyhgrafov |
| first_indexed |
2025-07-09T00:36:04Z |
| last_indexed |
2025-07-09T00:36:04Z |
| _version_ |
1837127558288637952 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2010. Том 21
УДК 519.7
c©2010. И.С. Грунский, С.В. Сапунов
ИДЕНТИФИКАЦИЯ ВЕРШИН ПОМЕЧЕННЫХ ГРАФОВ
Рассматривается задача определения мобильным агентом своего положения в среде моделируемой
графом с помеченными вершинами. Агент может перемещаться по дугам графа и наблюдать метки
вершин. Введены конечные множества слов в алфавите меток, отличающие одну вершину графа
от всех других его вершин, названные ее идентификаторами. Найдены условия существования,
оценки сложности идентификаторов и разработаны методы их построения. Разработаны полино-
миальные методы построения и проведения экспериментов по определению начальной вершины
графа, основанные на построении идентификаторов всех его вершин.
Ключевые слова: граф с помеченными вершинами, идентификатор вершины, диагностический
эксперимент.
1. Введение. Развитие теории формальных языков и конечных автоматов вы-
звало интерес к графам с помеченными элементами (вершинами, дугами, точками
”прикосновения” дуги к вершине и т.п.) [1, 2]. Результаты исследований таких гра-
фов получили широкий спектр приложений. В частности, графы с помеченными
элементами (помеченные графы) оказались удобным средством для исследования
топологических операционных сред мобильных агентов (роботов, поисковых про-
грамм и т.п.)[3]. При планировании двигательного поведения мобильных агентов
(МА) возникают три взаимосвязанные фундаментальные задачи: задача построе-
ния модели неизвестной среды (exploration), задача определения положения робота
в известной среде (robot selflocation) и задача проверки соответствия неизвестной
среды и ее модели (карты) (map validation) [4]. Заметим, что эти задачи имеют
соответствующие аналоги в теории автоматов [5].
Центральной из перечисленных задач является задача самолокализации, так как
от ее решения зависит решение двух других задач. Состоит она в следующем: МА,
обладая картой (помеченным графом) среды, должен установить соответствие меж-
ду вершиной на карте и неизвестной ему априори областью среды, в которой он пер-
воначально находился. При изучении задачи самолокализации возник ряд подходов,
зависящих от того, какие элементы графа агент наблюдает и метки каких элементов
он может изменить. В работах [3, 4] рассматривается задача самолокализации МА, у
которого операционная среда моделируется конечным неориентированным графом с
помеченными концами ребер. МА, находясь в некоторой вершине графа, единствен-
ным образом нумерует концы ребер, инцидентных этой вершине. МА не отличает
вершины графа друг от друга. Если существует путь из одной вершины графа в
другую его вершину, то он описывается как последовательность пар номеров попар-
но смежных ребер. Авторы предлагают алгоритм определения начальной вершины
известного n-вершинного графа за O
(
n5
)
шагов при условии, что робот использует
один переносной маркер. Основная идея алгоритма состоит в построении O
(
n2
)
ги-
потез о начальной вершине и разметке инцидентных ей ребер. Далее, МА проверяет
86
Идентификация вершин помеченных графов
каждую гипотезу за время O
(
n3
)
. При этом он восстанавливает граф из начальной
вершины, параллельно сравнивая восстановленную часть графа с известной ему мо-
делью. Недостатком предложенных модели и алгоритма самолокализации является
невозможность однозначного определения положения робота на графе с симметрией
(нетривиальным автоморфизмом).
В данной работе в качестве топологической модели операционной среды рас-
сматриваются конечные ориентированные графы. Вершины этих графов заранее
помечены и эти метки агент не меняет. Такая модель возникает, например, при каче-
ственной навигации МА (qualitative navigation) [8]. Основой такой навигации служат
ориентиры, которые разбивают линиями действия, каждая из которых проходит че-
рез два ориентира, операционную среду на выпуклые многоугольники, являющиеся
областями информационной эквивалентности. Каждая такая область является, в
свою очередь, вершиной скелетного графа, а общая сторона двух многоугольни-
ков порождает ребро между соответствующими вершинами скелетного графа. Если
каждой вершине сопоставить упорядоченную по углу наблюдения последователь-
ность ориентиров, то получим неориентированный граф с помеченными вершинами.
2. Основные определения. Конечным ориентированным графом с помечен-
ными вершинами (помеченным орграфом) назовем четверку G = (G,E (G) ,M, µG),
где G – конечное множество вершин, |G| = n, E (G) ⊆ G×G – конечное множество
ребер, M – алфавит меток, |M |, µG : G → M – сюръективная функция разметки.
Последовательность меток вершин w = µG (g1) . . . µG (gk), соответствующую некото-
рому пути g1 . . . gk в графе G, назовем словом длины k, порожденным вершиной g1.
Через d(w) обозначим длину слова w. Инверсией слова w = x1 . . . xk назовем слово
wrev = xk . . . x1. Слово v называется подсловом слова w, если существуют слова u1 и
u2 (возможно пустые) такие, что w = u1vu2. Если u1 пусто, то слово v также назы-
вается начальным отрезком или префиксом prek(w) слова w длины k, где k = d(v).
Обозначим через M+ множество всех непустых слов в алфавите M . Пусть W ⊆ M+.
Высотой W назовем наибольшую из длин, входящих в него слов, его кратностью –
величину |W |, его объемом – сумму длин всех входящих в него слов.
Для слов u, w ∈ M+ введем их композицию u ◦ w равную uw′, если u = u′x,
w = xw′, x ∈ M , и не определено в противном случае. Введем частичную операцию
? : G × M+ → 2G соотношением: для любой вершины g ∈ G и любого слова w ∈
M+ через g ? w обозначим множество всех вершин h ∈ G таких, что существует
путь из g в h, помеченный словом w = µ (g) ◦ w ◦ µ (h). Распространим операцию
? на подмножества множества G естественным образом: если G′ ⊆ G, то G′ ? w =⋃
g∈G′ (g ? w).
Языком Lg вершины g назовем множество всех слов, порожденных этой верши-
ной. Будем говорить, что вершины g, h ∈ G неотличимы, т.е. (g, h) ∈ ε, если Lg = Lh.
Отношение ε рефлексивно, симметрично и транзитивно, т.е. является отношением
эквивалентности. Фактор-граф G/ε графа G по отношению ε назовем приведенным
графом. Всякому множеству вершин G′ ⊆ G поставим в соответствие множество
слов LG′ =
⋃
g∈G′ Lg.
Помеченный орграф G назовем детерминированным орграфом или D-орграфом,
87
И.С. Грунский, С.В. Сапунов
если для любой вершины g ∈ G и любых вершин s, t ∈ Γ−(g) из s 6= t следует, что
µ(s) 6= µ(t) (здесь Γ−g обозначает множество всех вершин, являющихся концами дуг,
исходящих из g). В противном случае G назовем ND-орграфом. В [9] показано, что
оценка длины кратчайшего слова, различающего две вершины D-орграфа равна
n−m + 1 и совпадает с верхней оценкой длины кратчайшего слова, различающего
состояния конечного всюду определенного детерминированного автомата Мура [6].
Простой D-граф G назовем сильно детерминированным или SD-графом, если для
него выполняются следующие ограничения: 1) для любых вершин g, h ∈ G если
(g, h) ∈ E(G), то (h, g) ∈ E(G); 2) для любой вершины g ∈ G и любых вершин
s, t ∈ O(g) из s 6= t следует, что µ(s) 6= µ(t) (здесь O(g) = Γ−g ∪ {g}).
3. Эксперименты с графами. Экспериментом с графом G относительно апри-
орной информации I, цели C и средств S назовем процесс, состоящий из трех этапов:
1) построение теста P ⊂ M+ на основе I и C; 2) получение мобильным агентом (МА)
экспериментальных данных W на основе P и S; 3) вывод заключений о свойствах
графа на основе W и I. Априорная информация - это класс графов, к которому
принадлежит G. Основное отличие экспериментов с графами от экспериментов с
автоматами [5] состоит в методах и средствах S получения экспериментальных дан-
ных, а именно, возможностях МА перемещаться по графу, воспринимать локальную
информацию о вершинах и ставить в них дополнительные стираемые/нестираемые
метки.
Эксперимент назовем диагностическим, если априори полностью известен граф
G и МА установлен в произвольную начальную вершину этого графа, а целью яв-
ляется определение этой вершины, то есть отличение этой вершины от всех других
вершин. Допуская вольность речи, множество W будем также называть экспери-
ментом и говорить, что эксперимент W порождается тестом P .
Будем рассматривать следующие меры сложности экспериментов. Операцион-
ной кратностью эксперимента назовем величину, равную, в зависимости от спосо-
ба проведения эксперимента, либо количеству экземпляров МА, использованных
при получении W, либо количеству установок МА экспериментатором в начальную
вершину исследуемого графа. Если используется только один экземпляр МА (одна
установка), то эксперимент назовем простым. Операционной высотой эксперимента
назовем наибольшую из длин путей, которые проходит каждый экземпляр МА по
исследуемому графу в ходе эксперимента.
Из определения эксперимента следует, что он осуществляется посредством про-
хождения МА некоторого связанного с тестом P множества путей по графу G из
вершины g. Будем полагать, что, находясь в любой вершине h ∈ G, МА воспри-
нимает множество слов Ob+(h) = Mk ∩ Lh, где Mk ⊆ M+ является множеством
всех слов длины не больше k в алфавите меток M , и вычисляет множество слов
Ob−(h) = Mk−Lh = Mk−Ob+(h). При k = 1 полагаем, что МА воспринимает толь-
ко метку текущей вершины. Таким образом, проходя путь g1 . . . gl в графе G, МА
воспринимает множество слов Ob+ (g1 . . . gl) =
⋃l
i=1 µ (g1) . . . µ (gi)◦Ob+ (gi) и вычис-
ляет множество слов Ob− (g1 . . . gl) =
⋃l
i=1 µ (g1) . . . µ (gi) ◦ Ob− (gi). В дальнейшем,
если не оговорено противное, будем считать, что k = 2.
88
Идентификация вершин помеченных графов
Пусть w ∈ M+. Обозначим через δg(w) множество всех путей из вершины g, ко-
торые помечены словом w. По произвольному множеству P ⊆ M+ и g ∈ G построим
пару W g =
{
W+
g ,W−
g
}
, где W+ =
⋃
w∈[P ] Ob+ (δg(w)) и W− =
⋃
w∈[P ] Ob− (δg(w)), а
[P ] является замыканием множества P по всем непустым начальным отрезкам слов
из P . Экспериментом W с графом G, порожденным тестом P , назовем семейство{
W g
}
g∈G
. Эксперимент W назовем диагностическим точно тогда, когда для любых
вершин g, h ∈ G из g 6= h вытекает W g 6= W h, то есть W+
g 6= W+
h или W−
g 6= W−
h . В
этом случае тест P также назовем диагностическим.
4. Идентификаторы вершин. Идентификатором вершины g ∈ G назовем ко-
нечное множество слов Wg ⊆ M+ такое, что для любой вершины h ∈ G равенство
Wg ∩ Lg = Wg ∩ Lh выполняется тогда и только тогда, когда g = h.
Ясно, что всякий идентификатор Wg можно представить как объединение W+
g ∪
W−
g двух множеств W+
g = Wg ∩ Lg и W−
g = Wg − Lg. Идентификатор Wg будем
называть позитивным, если W−
g = ∅ и негативным, если W+
g = ∅.
Рассмотрим условия существования идентификаторов вершин D-графов.
Теорема 1. Равносильны следующие утверждения:
1. Существует идентификатор вершины g ∈ G.
2. Существует идентификатор вершины g ∈ G высоты не больше n−m + 1 и
кратности не больше n− 1.
3. ε(g) = {g}.
Доказательство. Импликация 2 ⇒ 1 очевидна.
Покажем, что из утверждения 1 следует утверждение 3. Пусть Wg — идентифи-
катор вершины g, h — некоторая вершина и h ∈ ε(g). Из последнего соотношения
следует, что Lg = Lh и тогда Wg ∩ Lg = Wg ∩ Lh. По определению идентификатора
g = h, то есть ε(g) = {g}.
Покажем далее, что из утверждения 3 следует утверждение 2. Пусть G− {g} =
{g1, . . . , gn−1}. Так как ε(g) = {g}, то для любой вершины gi, 1 6 i 6 n−1, существует
слово wi ∈ Lg ⊕ Lgi . Пусть W = {w1, . . . , wn−1}. Очевидно, что для любой вершины
gi выполняется Lg ∩W 6= Lgi ∩W , то есть W является идентификатором g. Ясно,
что |W | = n− 1. По [9] длина слова wi не превосходит n−m + 1.
Теорема доказана. ¤
Рассмотрим алгоритм построения идентификаторов всех вершин произвольно-
го D-графа G. Основная идея алгоритма состоит в построении последовательности
π1, π2, . . . , πk разбиений множества вершин G до тех пор, пока πk = πk+1. Одно-
временно для каждого разбиения πi = {K1, K2, . . . ,Kr}, r 6 n, строится семейство
{W1,W2, . . . , Wr} множеств слов в алфавите M так, что каждому классу Kj ∈ πi,
1 6 j 6 r, соответствует множество Wj ⊆ M+. Финальному разбиению πk соответ-
ствует семейство идентификаторов всех вершин графа G.
Алгоритм 1. Построение идентификаторов вершин
Вход. D-граф G = (G,E, M, µ).
Выход. Семейство {Wg1 , ...,Wgn} идентификаторов всех вершин графа G.
Метод.
89
И.С. Грунский, С.В. Сапунов
1. Построим разбиение π1 = {X1, X2, . . . , Xm}, каждый класс которого состоит
из всех одинаково помеченных вершин, то есть Xi = G ? xi, где 1 6 i 6 m, xi ∈ M .
Инициализируем множество AK активных классов и положим AK = π1. С каждым
классом Xi ∈ π1 свяжем множество слов WXi и положим WXi = {xi}.
2. Положим k = 1.
3. Положим πk+1 = πk.
4. Если AK = ∅ и πk = πk+1, то финальное разбиение πk = {K1,K2, . . . ,Kr},
r 6 n, уже построено. Для каждого класса Ki ∈ πk, 1 6 i 6 r, и для каждой
вершины g ∈ Ki положим Wg = WKi . Алгоритм прекращает работу.
5. Если AK = ∅ и πk 6= πk+1, то положим k = k + 1.
6. Если AK 6= ∅, то выберем класс B ∈ AK и положим AK = AK \B.
7. Положим B′ = ∅, U ′ = ∅, U ′′ = ∅.
8. Для каждой метки x ∈ M такой, что существует вершина g ∈ B, для которой
выполняется g ? µ (B) x = ∅, положим U ′ = U ′ ∪ {x}.
9. Положим U ′′ = M \ U ′.
10. Если U ′ = ∅, то перейдем к 16.
11. Выберем метку x ∈ U ′ и положим U ′ = U ′ \ {x}.
12. Для каждой вершины g ∈ B такой, что g?µ (B) x = ∅, положим B′ = B′∪{g}.
13. Если B′ = B и U ′ 6= ∅, то положим B′ = ∅ и возвратимся к 11.
14. Если B′ = B и U ′ = ∅, то перейдем к 16.
15. Положим B′′ = B \B′, WB′ = WB′′ = WB ∪ {µ (B) x} и перейдем к 23.
16. Если U ′′ = ∅, то возвратимся к 4.
17. С каждой меткой x ∈ U ′′ свяжем класс Kx такой, что µ (Kx) = x, B?µ (B) x∩
Kx 6= ∅ и высота множества WKx наименьшая из возможных.
18. Выберем метку x ∈ U ′′, у которой высота WKx наименьшая, и положим
U ′′ = U \ {x}.
19. Для каждой вершины g ∈ B такой, что g ? µ (B) x = Kx, положим B′ =
B′ ∪ {h}.
20. Если B′ = B и U ′′ 6= ∅, то положим B′ = ∅ и возвратимся к 18.
21. Если B′ = B и U ′′ = ∅, то возвратимся к 4.
22. Положим B′′ = B \B′, WB′ = WB′′ = WB ∪ µ (B) WKx .
23. Положим πk+1 = (πk+1 \B) ∪B′ ∪B′′ и возвратимся к 4.
Анализ алгоритма 1 начнем со следующей теоремы.
Теорема 2. Алгоритм 1 строит семейство {Wg}g∈G идентификаторов всех
вершин произвольного D-графа G, для которых существует идентификатор.
Доказательство. Алгоритм останавливается тогда, когда все классы разбиения
неактивны. Класс становится неактивным, если он не разделился на два подкласса.
Поэтому алгоритм остановится, по крайне мере, после того, как будет получено
разбиение, состоящее из одноэлементных классов.
Покажем, что финальное разбиение, построенное алгоритмом 3.1, является ε-
эквивалентным разбиением множества G. Пусть g, h ∈ G, µ(g) = µ(h) и (g, h) 6∈ ε. То-
гда существует кратчайшее слово wxy, где w ∈ M∗, x, y ∈ M , такое, что wx ∈ Lg∩Lh
и wxy ∈ Lg ⊕ Lh. Так как одна из вершин g ? wxy или h ? wxy не существует, то на
90
Идентификация вершин помеченных графов
некоторой итерации алгоритма 1 вершины g ?wx и h?wx попадут в разные классы.
Тогда на некоторой следующей итерации вершины g ? w и h ? w также попадут в
разные классы. Далее, для любого k, 1 < k < d(w), вершины g?prek(w) и h?prek(w)
будут попадут в разные классы на соответствующих итерациях алгоритма. Так как
вершины g ? pre2(w) и h ? pre2(w) находятся в разных классах, то по окончании
работы алгоритма вершины g и h также находятся в разных классах финального
разбиения. Так как вершины g и h были выбраны произвольно, то тем самым доказа-
но, что финальное разбиение, построенное алгоритмом 1 является ε-эквивалентным
разбиением множества G.
Покажем, что по окончании работы алгоритма будет получено семейство иден-
тификаторов всех вершин графа G, то есть для любой вершины g ∈ G множество
слов Wg является ее идентификатором. Пусть g, h ∈ G. Если µ(g) 6= µ(h), то по по-
строению Wg∩Lg 6= Wg∩Lh, так как Wg∩Lg 6= ∅ и Wg∩Lh = ∅. Пусть µ(g) = µ(h).
Если g и h принадлежат одному и тому же классу ε-неотличимости, то Wg = Wh по
построению и, следовательно, Lg ∩Wg = Lh ∩Wg. Пусть µ(g) = µ(h) и вершины g и
h принадлежат разным классам ε-неотличимости. Покажем, что существует слово
w ∈ Wg ∩Wh такое, что w ∈ Lg ⊕ Lh. Пусть вершины g и h принадлежат одному и
тому же классу X разбиения πk−1 и µ (X) = x. Пусть, далее, при построении разби-
ения πk класс X разбивается на два подкласса X ′ и X ′′ такие, что g ∈ X ′, h ∈ X ′′.
Тогда для некоторой метки y ∈ M или (1) g?xy = ∅ и h?xy 6= ∅, или (2) существует
класс Y ′ ∈ πk такой, что µ (Y ′) = y, g ? xy ∈ Y ′ и h ? xy 6∈ Y ′ или h ? xy = ∅. Если в
случае (1) g ? xy = ∅ или в случае (2) h ? xy = ∅, то xy ∈ Wg ∩Wh и искомое слово
w = xy. Пусть h?xy ∈ Y ′′, где Y ′′ ∈ πk. Тогда xWY ′ ⊆ Wg, xWY ′′ ⊆ Wh и существует
класс Y , такой, что Y ∈ πk−l, Y 6∈ πk−l+1, 1 < l 6 k − 1 и Y – наименьший по
включению класс для которого Y ′, Y ′′ ⊆ Y . Так как при построении πk−l+1 класс Y
разбивается на два подкласса, то для некоторой метки z ∈ M или (1) Y ′ ? yz = ∅
и Y ′′ 6= ∅, или (2) существует класс Z ′ ∈ πk−l+1 такой, что µ (Z ′) = z, Y ′ ? yz ⊆ Z ′
и (Y ′′ ? yz) ∩ Z ′ = ∅. Если в случае (1) g ? xyz = ∅ или в случае (2) h ? xyz = ∅,
то xyz ∈ Wg ∩ Wh и искомое слово w = xyz. Если h ? xyz ∈ Z ′′, где Z ′′ ∈ πk−l+1,
то xyWZ′ ⊆ Wgи xyWZ′′ ⊆ Wh. Продолжая построение слова w, получим, что для
некоторой метки p ∈ M или (1) g ? xyz . . . p = ∅ и h ? xyz . . . p 6= ∅, или (2) суще-
ствует класс P ′ ∈ π2 такой, что µ (P ′) = P , g ? xyz . . . p ∈ P ′ и h ? xyz . . . p 6∈ P ′ или
h?xyz . . . p = ∅. Если в случае (1) g ?xyz . . . p = ∅ или в случае (2) h?xyz . . . p = ∅,
то xyz . . . p ∈ Wg ∩ Wh и искомое слово w = xyz . . . p. Если h ? xyz . . . p ∈ P ′′, то
xyz . . . WP ′ ⊆ Wg и xyz . . . WP ′′ ⊆ Wh. Тогда существует класс P ∈ π1 такой, что
P = P ′ ∪ P ′′. Покажем, что класс P на 2-м шаге алгоритма 3.1 разбивается на
подклассы тогда и только тогда, когда для некоторой метки q ∈ M выполняется
P ′ ? pq = ∅ и P ′′ ? pq 6= ∅ или наоборот P ′ ? pq 6= ∅ и P ′′ ? pq = ∅. Действитель-
но, в разбиении π1 каждый класс содержит все одинаково помеченные вершины,
поэтому, если для любой вершины g ∈ P выполняется g ? pq 6= ∅, то все вершины
g ? pq находятся в одном классе. Тогда слово xyz . . . pq ∈ Wg ∩Wh и искомое слово
w = xyz . . . pq. ¤
Таким образом, алгоритм 1 правильно строит идентификаторы всех вершин про-
91
И.С. Грунский, С.В. Сапунов
извольного D-графа G. Оценку сложности алгоритма 1 и сложности идентифика-
торов, построенных при его помощи дает следующая теорема.
Теорема 3. Алгоритм 1 за время O
(
m · n2 + n3
)
для каждой вершины g ∈ G
строит идентификатор Wg, высота и кратность которого равны O(n).
Доказательство. В наихудшем случае на каждой итерации алгоритма 1 в от-
дельный класс отделяется только одна вершина. Тогда, с учетом того, что первона-
чальное разбиение состоит из m классов, количество итераций ограничено сверху
числом n−m + 1.
Первоначально в каждом из множеств слов, порождаемых алгоритмом, нахо-
дятся слова длины 1. На каждой итерации алгоритма максимальная длина слова
среди всех слов, находящихся в этих множествах, увеличивается на 1. Таким обра-
зом, по окончании работы алгоритма, высота построенных им идентификаторов не
превосходит n−m + 1.
Вернемся к рассмотрению наихудшего случая. Если на каждой итерации алго-
ритма отделяется ровно одна вершина, то множество слов, ассоциированное с еще
неразличенными вершинами увеличивается на одно слово. Так как количество вер-
шин в одном блоке не превосходит n − m + 1, то в указанном множестве может
находиться не более n−m+1 слов. Следовательно кратность построенных алгорит-
мом 3.1. идентификаторов не превосходит n−m + 1.
Наиболее трудоемкой частью каждой из итераций алгоритма 1 является объ-
единение множеств слов. Для объединения двух множеств слов кратностью O (n),
высотой O (n) и алфавитом мощности m достаточно воспользоваться алгоритмом
лексикографической сортировки [7]. Сложность сортировки с такими параметрами
равна O
(
m · n + n2
)
.Таким образом, сложность построения идентификаторов всех
вершин графа G, с учетом верхней оценки числа итераций алгоритма 3.1., равна
O
(
m · n2 + n3
)
. ¤
5. Диагностический эксперимент. Напомним, что эксперимент с графом G
называется диагностическим, если априори полностью известен граф G и МА уста-
новлен в произвольную неизвестную ему вершину g этого графа, а целью экспери-
мента является определение этой вершины, то есть отличение вершины g от всех
других вершин. Из определения эксперимента следует, что он осуществляется по-
средством прохождения МА некоторого связанного с тестом P множества путей по
графу G из вершины g.
Очевидно, что если граф G не приведен, то диагностический эксперимент с ним
невозможен. Действительно, если (g, h) ∈ ε, то вершины g, h ∈ G по определению
неотличимы никаким словом из M+. Если граф G приведен, то, как показано в раз-
деле 2, существует k такое, что Lk
g 6= Lk
h для всех g 6= h, g, h ∈ G. Тогда P =
⋃
g∈G Lk
g
является диагностическим тестом для G, поскольку порожденный P эксперимент W
является диагностическим экспериментом с графом G, так как W ∩Lg 6= W ∩Lh, то
есть W g 6= W h для всех g 6= h. Поэтому в дальнейшем, если не оговорено противное,
будем считать, что все рассматриваемые графы приведены.
Следующая теорема описывает класс диагностических тестов, определяемых
идентификаторами вершин графа G. Рассмотрим множество слов P =
⋃
g∈G Wg,
92
Идентификация вершин помеченных графов
где Wg является некоторым идентификатором вершины g ∈ G. Очевидно, что для
любых различных вершин g, h ∈ G выполняется P ∩Lg 6= P ∩Lh. Действительно, так
как Wg ⊆ P , то по определению идентификатора Wg∩Lg 6= Wg∩Lh, а следовательно
P ∩ Lg 6= P ∩ Lh. Таким образом, справедливо следующее утверждение.
Теорема 4. Множество слов P =
⋃
g∈G Wg является диагностическим тестом
для графа G при любом семействе идентификаторов {Wg}g∈G.
Эта теорема дает метод построения диагностических тестов для помеченных
графов различных типов.
Опишем подробно каждый этап диагностического эксперимента.
Для построения теста P воспользуемся алгоритмом 1. Кратность такого теста
равна O
(
n2
)
, его высота не превосходит n −m + 1, а его объем равен O
(
n3
)
. Для
построения теста P достаточно O
(
m · n2 + n3
)
шагов.
На втором этапе МА получает экспериментальные данные W на основе теста
P . Так как перемещение МА по исследуемому графу G может быть осуществлено
с использованием различных стратегий (алгоритмов), то экспериментальные дан-
ные могут быть получены с использованием различных методов. Первая страте-
гия заключается в том, что МА, стартуя из неизвестной ему вершины h графа G,
строит разбиение теста P на два класса путем непосредственной проверки нали-
чия/отсутствия в G путей, помеченных словами из P . При этом МА анализирует
окрестности вершин при их прохождении, одновременно уменьшая множество под-
лежащих проверке слов. Причем проверка каждого слова проводится из началь-
ной вершины h, априори неизвестной МА. Экспериментальными данными являют-
ся полученное в результате таких проверок разбиение π (h) теста P на два класса
P+
h = P ∩ Lh и P−
h = P − Lh.
Алгоритм 2. Диагностический эксперимент (стратегия 1)
Вход. Приведенный D-граф G = (G,E, M, µ).
Семейство {Wg1 , ...,Wgn} идентификаторов всех вершин графа G.
МА установлен в неизвестную ему вершину h ∈ G.
Выход. Разбиение π (h) теста P на два класса P+
h = P ∩ Lh и P−
h = P − Lh.
Метод.
1. Положим P+
h = ∅, P−
h = ∅, P ′ = ∅, P ′′ = ∅.
2. Считать метку µ (h) вершины h.
3. Для каждого слова w ∈ P , начинающегося с µ (h), положим P ′ = P ′ ∪ {w}.
4. Положим P−
h = P \ {P ′}.
5. Если P ′ = ∅, то положим P+
h = ∅ и P−
h = P . Алгоритм прекращает работу.
6. Если P ′ 6= ∅, то выберем слово w ∈ P ′ и положим P ′ = P ′ \ {w}. Иначе
алгоритм прекращает работу.
7. Положим i = 1.
8. Положим wi = prei (w).
9. Если i = d (w), то положим P+
h = P+
h ∪ {w}. Перейти к п. 6.
10. Перейти в вершину h ? wi.
11. Вычислить C = Ob− (h ? wi).
93
И.С. Грунский, С.В. Сапунов
12. Для каждого слова u ∈ P ′ такого, что u является начальным отрезком какого-
либо слова из C, положим P−
h = P−
h ∪ {u} и P ′ = P ′ \ {u}.
13. Если wi+1 ∈ C, то положим P−
h = P−
h ∪ {w}. Перейти к п. 6.
14. Положим i = i + 1. Перейти к п. 8.
Рассмотрим свойства алгоритма 2.
Теорема 5. Алгоритм 2 строит разбиение диагностического теста P на два
класса за O
(
n3
)
шагов.
Доказательство. Поскольку при каждой итерации цикла из P ′ удаляется, по
крайней мере, одно слово, то этот алгоритм всегда завершается и при P ′ = ∅ полу-
чаем разбиение π(h) теста P на два класса P+
h и P−
h . В наихудшем случае алгоритм
построения π(h) требует проверки всех слов из P . Следовательно, сложность такого
построения равна объему P , то есть равна O
(
n3
)
. ¤
На данном этапе уже могут быть сделаны заключения об операционной высо-
те и кратности диагностического эксперимента. Поскольку, в общем случае, тест
P кратный, то при выполнении второго этапа эксперимента предполагается, что
или МА перед началом анализа слова w ∈ P ′ переносится экспериментатором в
начальную вершину h, или в h помещается новый экземпляр МА. Таким образом,
для теста P кратности k и данной стратегии проведения диагностического экспери-
мента операционная кратность диагностического эксперимента не превосходит k, а
операционная высота диагностического эксперимента равна высоте теста P .
На третьем этапе эксперимента определяется начальная вершина путем анализа
экспериментальных данных. Для теста P с каждой вершиной g ∈ G свяжем его
разбиение π(g) на два класса P+
g = P ∩Lg и P−
g = P −Lg. Ясно, что для построения
семейства {π(g)}g∈G таких разбиений достаточно O
(
n4
)
шага. Далее, построенное
экспериментально разбиение π(h) сравнивается со всеми разбиениями из семейства
{π(g)}g∈G. Если для некоторого π(g) выполняется π(g) = π(h), то g = h и экспери-
мент окончен. Из правил построения семейства {π(g)}g∈G и разбиения π(h) следует,
что последнее равенство всегда достигается. Из описания алгоритма построения
разбиения π(h) и правила вывода заключения непосредственно следует, что дей-
ствительная начальная вершина h всегда будет определена правильно.
Прежде чем приступить к изложению второй стратегии, рассмотрим полезную
конструкцию, позволяющую переходить от множества слов к помеченным графам.
Пусть W = {w1, . . . , wl} некоторое множество конечных слов в алфавите M . С каж-
дым словом wi = xi1 . . . xik , 1 6 i 6 l, свяжем помеченное корневое ориентированное
дерево T(wi), множество вершин которого равно {ti1 , . . . , tik}, множество дуг состо-
ит из всех пар
(
tij , tij+1
)
, 1 6 j < k, метка µT
(
tij
)
равна xij , а корнем является
вершина ti1 . С множеством W свяжем помеченный лес F (W ), являющийся прямой
суммой всех корневых деревьев T(w), где w ∈ W . Если все слова в W начинаются
с одной и той же метки, то с W связывается помеченное корневое дерево T(W ),
полученное из F (W ) отождествлением всех корней ti1 , 1 6 i 6 l, и последующей де-
терминизацией, то есть многократным и исчерпывающим применением следующей
операции: если в множество преемников некоторой вершины попадают вершины
с одинаковыми метками, то такие вершины отождествляем, заменяя возникающие
94
Идентификация вершин помеченных графов
кратные дуги одной дугой. Очевидно, что T(W ) является D-графом и W = LT(W ).
С тестом P свяжем помеченный лес F (P ) корневых деревьев и детерминизируем
этот лес. Обозначим через Px множество всех слов из P , начинающихся с метки x ∈
M . Ясно, что Px является объединением идентификаторов всех вершин g ∈ G таких,
что µ (g) = x. Тогда корневое ориентированное дерево T(Px) является компонентой
леса F (P ). Для всех x ∈ M с деревом T(Px) свяжем множество вершин Gx = G ? x
(то есть, всех вершин с меткой x). Обозначим корень дерева T(Px) через tx. Для
каждого слова w ∈ Px вершину tx ? w дерева T(Px) назовем выделенной. С каждой
выделенной вершиной t = tx ? w свяжем два множества G (t) = {g ∈ G |w ∈ Lg}
и G̃ (t) = {g ∈ G |µ(g) = x ∧ w 6∈ Lg}. Множество всех выделенных вершин дерева
T(Px) обозначим через Tx.
Во второй стратегии процесс получения экспериментальных данных заключа-
ется в том, что МА, стартуя из неизвестной ему вершины h графа G, проверяет
наличие/отсутствие в G путей, помеченных теми же словами, что и пути из корня
дерева T
(
Pµ(h)
)
во все выделенные вершины этого дерева. В зависимости от исхода
каждой из таких проверок уменьшаются подмножества вершин графа G, связан-
ные с выделенными вершинами дерева T
(
Pµ(h)
)
. По окончании работы алгоритма
множество Gµ(h) содержит единственную вершину, которая и является искомой на-
чальной вершиной графа G. Таким образом, вторая стратегия объединяет этапы
получения экспериментальных данных и вывода заключений.
Алгоритм 3. Диагностический эксперимент (стратегия 2)
Вход. D-граф G = (G,E, M, µ).
Лес F (P ) корневых деревьев.
МА установлен в неизвестную ему вершину h ∈ G.
Выход. Множество Gµ(h).
Метод.
1. Считать метку µ (h) вершины h.
2. Выберем из леса F (P ) дерево T
(
Pµ(h)
)
.
3. Если
∣∣Gµ(h)
∣∣ = 1, то вершина h уже определена. Алгоритм прекращает работу.
4. Выберем выделенную вершину s = tµ(h) ? w и положим Tµ(h) = Tµ(h) \ {s}.
5. Положим i = 1.
6. Положим wi = prei (w).
7. Если переход из вершины h в вершину h?wi графа G невозможен, то перейти
к п. 8, иначе перейти к п. 9.
8. Для каждой вершины t ∈ Tµ(h) положим G (t) = G (t)\G (s), G̃ (t) = G̃ (t)\G (s)
и Gµ(h) = Gµ(h) \G (s). Перейти к п. 3.
9. Если i = d (w), то для каждой вершины t ∈ Tµ(h) положим G (t) = G (t)∩G (s),
G̃ (t) = G̃ (t) \G(s), Gµ(h) = G (s). Перейти к п. 3.
10. Положим i− i + 1. Перейти к п. 6.
Анализ алгоритма 3 начнем со следующей теоремы.
Теорема 6. По окончании работы алгоритма 4.2 множество Gµ(h) всегда со-
держит единственную вершину.
95
И.С. Грунский, С.В. Сапунов
Доказательство. Предположим, что после некоторой итерации алгоритма∣∣Gµ(h)
∣∣ > 1 и Tx = ∅, то есть условие окончания алгоритма не достигнуто, но
дальнейшее его выполнение невозможно. Пусть Gµ(h) = {h} ∪ G′, где h 6∈ G′. Из
построения теста Pµ(h) следует, что для любой вершины g ∈ G′ существует слово
w ∈ Pµ(h) такое, что w ∈ Lh ⊕ Lg. Тогда вершина s = tµ(h) ? w является выделенной
вершиной дерева T
(
Pµ(h)
)
и, либо h ∈ G (s) и g ∈ G̃ (s), либо наоборот g ∈ G (s)
и h ∈ G̃ (s). Так как Tµ(h) = ∅, то вершина s была удалена из Tµ(h) в ходе неко-
торой итерации алгоритма. Рассмотрим как могло произойти такое удаление. Если
вершина s была удалена из Tµ(h) по причине того, что G(s) = ∅, то на этой же
итерации либо вершина h, либо вершина g была удалена из Gµ(h), что невозможно.
Следовательно, на этой итерации МА побывал в вершине s и по этой причине эта
вершина была удалена из Tµ(h). Тогда на этой же итерации либо вершина h, либо
вершина g была удалена из Gµ(h), что невозможно. Из проведенных рассуждений
следует, что при Tµ(h) = ∅ выполняется Gµ(h) = {h}. ¤
В наихудшем случае на каждой итерации алгоритма из Gµ(h) удаляется одна
вершина. Так как число вершин графа G с меткой равной µ(h) не превосходит n−
m + 1, то алгоритм оканчивает свою работу через не более чем n−m итераций.
Поскольку, в общем случае, дерево T
(
Pµ(h)
)
содержит более одной ветви, то при
реализации предложенной стратегии предполагается, что МА перед началом ана-
лиза выделенной вершины t ∈ Tµ(h) переносится экспериментатором в начальную
вершину h ∈ G, или в h помещается новый экземпляр МА. В наихудшем случае МА
проверяет n −m выделенных вершин дерева T
(
Pµ(h)
)
. Следовательно, операцион-
ная кратность диагностического эксперимента не превосходит n−m. Операционная
высота диагностического эксперимента равна высоте множества слов Pµ(h).
6. Заключение. В работе решена задача различения вершин топологической
модели (помеченного графа-карты) операционной среды мобильного агента. Реше-
ние заключается в построении диагностического эксперимента и способа его реали-
зации на модели. Найдены оценки сложности соответствующих алгоритмов. С точки
зрения синтеза диагностических экспериментов с помеченными графами представ-
ляет интерес исследования условий существования и методов построения оптималь-
ных по сложности идентификаторов вершин.
1. James A. Anderson. Automata Theory with Modern Applications. – Cambridge University Press,
2006. – 255 p.
2. Edmund M. Clarke, Jr., Orna Grumberg, and Doron A. Peled. Model Checking. – The MIT Press,
1999. – 416 p.
3. Dudek G., Jenkin M. Computational Principles of Mobile Robotics. – Cambridge University Press,
Cambridge, 2000. – 280 p.
4. Dudek G., Jenkin M., Milios E., Wilkes D. Map validation and Robot Self-Location in a Graph-Like
World // Robotics and Autonomous Systems. – 1997. – Vol. 22, № 2. – P. 159–178.
5. Zvi Kohavi. Switching and finite automata theory. – McGraw-Hill, New York, 1970. – 592 p.
6. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами // Автоматы. –
М.: ИЛ, 1956. – С. 179-210.
7. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. The design and analisys of computer algorithms.
– Addison-Wesley, 1974, – 432 p.
96
Идентификация вершин помеченных графов
8. Levitt T., Lawton D.T. Qualitative navigation for mobile robot // Artificial Intelligence, 1990. – v.
40. – p. 306–360.
9. Сапунов С.В. Контроль детерминированных графов // Труды ИПММ. – 2003. – в. 8. – С.
106-110.
I.S. Grunsky, S.V. Sapunov
Topological identifiers of vertices of vertex labeled graphs.
The self-location problem for mobile agent in the topological environment is considered. Environment is
modeled by the vertex labeled graph. The agent can move by graph edges and observe labels of vertices.
A finite sets of words over the vertex labels alphabet distinguishing a given vertex from other called
vertex identifier is proposed. Existence conditions and complexity estimations for vertex identifiers are
discovered and constructions methods are developed. Polynomial constructions and realizations methods
for experiments detecting the vertex where the mobile agent start walking based on all vertices’ identifiers
construction are proposed.
Keywords: vertex labeled graph, vertex identifier, distinguishing experiment.
I.С. Грунський, С.В. Сапунов
Топологiчнi iдентифiкатори вершин позначених графiв.
Розглянуто задачу визначення мобiльним агентом свого положення в середовищi, яке моделюєть-
ся за допомогою графа з позначеними вершинами. Агент може пересуватися дугами графа та
спостерiгати позначки вершин. Введено визначення iдентифiкаторiв вершин, тобто скiнченнi мно-
жини слiв в алфавiтi позначок, якi вiдрiзняють одну вершину графа вiд усiх iнших його вершин.
Знайдено умови iснування, оцiнки складностi iдентифiкаторiв та розроблено методи їх побудови.
Розроблено полiномiальнi методи побудови i проведення експериментiв по визначенню початкової
вершини графа, якi грунтуються на побудовi iдентифiкаторiв усiх його вершин.
Ключовi слова: графи з позначеними вершинами, iдентифiкатор вершини, дiагностичний екс-
перимент.
Ин-т прикл. математики и механики НАН Украины, Донецк
sapunov sv@iamm.ac.donetsk.ua
Получено 25.11.10
97
|