Автор: Грунский И.С., Чепурко В.А.
Источник: Чепурко B.А. Распознавание графа при помощи построения на нем М – нумерации /
В.А. Чепурко, И.С. Грунский // II международная научно-практическая конференция молодых учёных
«Современная информационная Украина: информатика, экономика, философия». – 2008. – т.8. – С. 57–62.
Целью данной работы является введение достаточно общего понятия эксперимента с помеченным графом, который проводит система агентов, взаимодействующих между собой и с графом. Такие эксперименты относятся к проблематике взаимодействия управляющей и управляемой систем, которая является одной из классических для теоретической кибернетики [1,2]. В настоящее время эта проблема актуальна в связи с задачами навигации автономных мобильных роботов [3].
Под помеченным графом Q будем понимать конечный орграф без кратных дуг и с вершинами, помеченными метками из конечного множества М [4]. Экспериментом с графом Q относительно априорной информации I, цели С и средств S назовем процесс, состоящий из трех этапов:
1) построение теста Р⊆M на основе I и С;
2) получение системой агентов экспериментальных данных W на основе Р и S;
3) вывод заключений о свойствах графа на основе W и I. Априорная информация – это класс графов, к которому принадлежит Q.
Основное отличие экспериментов с графами от экспериментов с автоматами [1,5] состоит в методах и средствах S получения э кспериментальных данных: взаимодействующие агенты могут перемещаться по ребрам графа от вершины к вершине, воспринимать локальную информацию о вершинах графа и их окрестностях, ставить в вершинах и/или на дугах дополнительные стираемые/нестираемые метки, обмениваться этой информацией друг с другом.
Допуская вольность речи, множество W будем также называть экспериментом и говорить, что эксперимент W порождается тестом Р. Будем рассматривать следующие меры сложности экспериментов. Высотой теста Р назовем наибольшую из длин его слов, его кратностью – величину |Р|, его объемом – сумму длин всех его слов. Операционной кратностью эксперимента назовем величину, равную, в зависимости от способа проведения эксперимента, либо количеству экземпляров агента-исследователя (АИ), использованных при получении W, либо количеству установок агентом-экспериментатором (АЭ) агента–исследователя в начальную вершину исследуемого графа.
Если используется только один экземпляр АИ (одна установка), то эксперимент назовем простым. Операционной высотой эксперимента назовем наибольшую из длин путей, которые проходит каждый экземпляр АИ по исследуемому графу в ходе эксперимента. Полагаем, что АИ, находясь в любой вершине д графа Q, воспринимает ее окрестность, проходя некоторый путь по графу Q, агент может построить множество слов в алфавите М, которые он воспринял, и вычислить множество слов, которые не обнаружил.
Эксперимент назовем диагностическим, если априори полностью известен граф Q и АИ установлен в произвольную начальную вершину этого графа, а целью является определение этой вершины, т.е. отличие этой вершины от всех других вершин. Идентификатором вершины д помеченного графа Q назовем конечное множество слов в алфавите М, отделяющее д от всех других вершин этого графа.
В докладе предложен метод построения и проведения диагностических экспериментов с помеченными графами, основанный на построении идентификаторов всех вершин исследуемого графа. Для детерминированных графов [4] предложена стратегия, объединяющая второй и третий этапы диагностического эксперимента, при которой эксперимент всегда является простым и его операционная высота равна О (n3)Е (О (n2))Е для связного графа), где n – число вершин исследуемого графа. Это коренным образом отличается от результатов теории экспериментов с автоматами, где И. К. Рысцовым (см.[1]) показано, что высота кратчайшего простого диагностического эксперимента равна О (n6).
Эксперимент назовем контрольным, если полностью известен инициальный граф-эталон Q0, задан класс графов К и АИ установлен в начальную вершину произвольного графа Q∈К, а целью является проверка изоморфизма Q и Q0.
В докладе для инициального сильно детерминированного графа–эталона, являющегося частным случаем симметричного детерминированного графа, предложен полиномиальный метод построения и проведения контрольного эксперимента относительно класса всех таких графов с числом вершин не большим, чем у эталона. Предложенный метод построения контрольного теста использует идею известного в теории экспериментов с автоматами метода Василевского (см. [1]).
Далее предложен полиномиальный метод построения и проведения контрольного эксперимента для инициального сильно детерминированного графа-эталона и класса всех таких графов; этот метод основан на введенном новом представлении графа определяющей парой конечных множеств слов в алфавите меток, аналогичной системе определяющих соотношений для конечного автомата[6]; найдены критерии, при которых произвольная пара конечных множеств слов является определяющей парой некоторого помеченного графа.
Далее рассмотрена задача восстановления конечного, неориентированного помеченного графа с помощью АИ, который перемещается по неизвестному графу из вершины в вершину, метит вершины и инциденторы красками, воспринимает некоторую локальную информацию о графе и передает ее АЭ, который восстанавливает граф. Заметим, что в отличие от диагностического и контрольного экспериментов, где АИ не окрашивает вершины, в рассматриваемом эксперименте способ раскраски вершин является определяющим.
В докладе предлагается новый восстанавливающий эксперимент Процесс восстановления графов состоит из двух этапов:
1) обход АИ неизвестного графа окраска и перекраска его вершин и передача некоторой локальной информации о метках вершин агенту–экспериментатору;
2) восстановление исследуемого графа агентом-экспериментатором. Каждый из этапов выполняется отдельным агентом, параллельно или последовательно. Для выполнения этапов были разработаны алгоритмы, имеющие временную сложность 0(n2). Найдены и исследованы частные случаи графов, для которых временная сложность является либо линейной либо растет медленнее чем 0(n2).
Введены операции над такими графами, сохраняющая такую сложность. Полученный метод требует фиксированное множество меток, причем АИ имеет конечную память, а АЭ – линейно зависящую от n [7].
1.Кудрявцев В.Б. Введение в теорию автоматов / В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин – М.: Наука, 1985. – 320 с.
2. Капитонова Ю.В. Математическая теория проектирования вычислительных систем / Ю. В. Капитонова, А. А. Летичевский – М.: Наука, 1988. – 296 с.
3. Dudek G. Computational Principles of Mobile Robotics / G. Dudek, M. Jenkin – Cambridge University Press, Cambridge, 2000. – 280 p.
4. Сапунов C.B. О методе построения отношения неотличимости помеченных графов / С.В. Сапунов // Труды ИПММ НАН Украины, – 2008. – т.16. – С. 179–189.
5. Грунский И.С. Анализ поведения конечных автоматов / И.С. Грунский – Луганск: Изд-во Луганск, гос. пед. ун-та, 2003. – 318 с.
6. Грунский И.С. Свойства систем определяющих соотношений для автоматов / И.С. Грунский, А.С. Сенченко // Дискретная математика, – 2004. – т.16, №4. – С. 79–87.
7. Калибарда Г.Независимые системы автоматов в лабиринтах / Г. Калибарда, В.Б. Кудрявцев, Ш. Ущумлич // Дискретная математика – 2003. – т. 15, вып. 3. – С. 3–39.
8. Грунский И.С. Алгоритм распознавания графов / И.С. Грунский, Е.А. Татаринов // Труды 4 междунар. конф. «Параллельные вычисления и задачи управления», РАСО’2008, 27–29 октября 2008 г., Москва. – М.: ИПУ РАН им. В. А. Трапезникова, 2008. – С. 1483–1498.