Государственный университет информатики и искусственного интеллекта

С.А. Ковтун

И.С. Грунский

    Построения контрольного эксперимента для графов с отмеченными вершинами

Задачи, связанные с анализом различных сред с помощью блуждающих по ним агентов (мобильных роботов, автоматов, поисковых программ и т.п.) [1,5] относятся к категории традиционных задач искусственного интеллекта. Агент перемещается по среде, получая при этом некоторую локальную информацию о среде, на основе которой, исходя из некоторой априорной информации, решает поставленные перед ним задачи: например, обходит среду и (или) делает заключения о ее свойствах. В таких задачах рассматриваются различные геометрические модели сред. Одним из них являются графы, которые можно рассматривать как топологическую модель среды [3].

Одна из актуальных задач, предназначенных для решения с помощью мобильных агентов, известна как «задача проверки правильности карты» (map validation problem [4, 5]). Эта задача состоит в следующем: для заданной карты некой среды агент должен проверить является ли эта карта описанием той среды, которую он исследует или нет [4]. В случае, когда в качестве среды выступает граф, задача состоит в том, чтобы по описанию графа-эталона определить, изоморфен ему исследуемый граф или нет. Роль агента в этом случае может выполнять конечный автомат, блуждающий по исследуемому графу.

В настоящей работе рассматриваются связные неориентированные инициальные графы с отмеченными вершинами. Рассматривается задача проверки агентом, блуждающим по графу, правильности карты, задаваемой графом-эталоном. Будем говорить, что агенту необходимо распознать граф-эталон в классе исследуемых графов. Находясь в некоторой вершине графа, агент «видит» отметку этой вершины и отметки всех смежных вершин. Агент может перемещаться по рёбрам графа от вершины к вершине. Задача заключается в том, чтобы, имея полное описание графа-эталона, построить такое конечное множество путей по исследуемому графу (контрольный эксперимент), которое позволяет проверить, изоморфен ли исследуемый граф графу-эталону. Подобные задачи изучались для конечных автоматов Мили и конечных входных – выходных автоматов.

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

Рассматривается класс K(M) всех конечных, простых (т.е. без петель и кратных рёбер), связных, помеченных, инициальных, неориентированных графов G=(SG, EG, XG, μ, g0), где SG – конечное множество вершин, EG – множество рёбер, XG⊆M – подмножество фиксированного конечного непустого алфавит отметок M, μ: SG→XG – сюръективная функция разметки вершин, g0 – инициальная вершина. M+ – множество всех непустых слов в алфавите M, e – пустое слово, M*=M+∪{e} – свободный моноид на множестве M, M1=M∪{e}.

Конечную последовательность вершин p=g1…gk такую, что при k>1 ∈EG, 1≤i<k, назовем путём длины (k-1) в графе G. Последовательность μ(p)=μ(g1)…μ(gk) назовём отметкой пути p. Отметку любого пути, исходящего из вершины g∈SG, будем называть словом, порожденным вершиной g. Язык Lg определим как множество всех слов, порожденных вершиной g∈SG. Вершины g,h∈SG назовём неотличимыми, если Lg=Lh, и отличимыми в противном случае. Граф G называется приведенным, если все его вершины попарно отличимы. Множество Lg0, где g0 – инициальная вершина графа G, назовём языком, представимым графом G, и обозначим его LG. Через LGk будем обозначать множество всех слов языка LG длиной не более k.

Будем говорить, что графы G и H из класса K(M) изоморфны и обозначать это G≅H, если между множествами их вершин существует биекция сохраняющая смежность, отметки вершин и инициальную вершину.

Конечное множество слов Р⊂M+ назовём контрольным экспериментом для графа G∈K(M) относительно класса F⊆K(M), если для любого графа H∈F из LH∩P = LG∩P следует G≅H. Граф G при этом будем называть графом–эталоном (или просто эталоном), а F – классом исследуемых графов.

Мощность |P| контрольного эксперимента P назовем его кратностью, длину l(P) его наибольшего слова – длиной эксперимента.

Метод построения контрольного эксперимента:

1. Строим список идентификаторов всех вершин

Пусть находясь в вершине h ∈ G мобильный автомат видит все метки смежных вершин и может составить множество слов Оb+(h)=Мk∩Lh, где Мk⊆М+ является множеством всех слов длины не больше k в алфавите меток М, и вычисляет мно¬жество слов Оb-(h)=Мk-Lh=Мk-Оb+(h). Таким образом, множество Ob(h)=Оb+(h)∪Оb-(h) однозначным образом идентифицирует вершину h. Объединение идентификаторов всех вершин приведенного помеченного графа является для него диагностическим тестом.

2. Строим элементарные проверки дуг

Вершины каждой дуги графа G помечаем идентификаторами. Таким образом все дуги графа G однозначно идентифицированы.

3. Отношение покрытия

Удаляем элементарные проверки дуг, которые покрываются более крупными элементарными проверками. Данная задача не имеет однозначного решения и относится к классу NP-полных задач.

4. Собираем связный граф, содержащий все элементарные проверки дуг

Решение данной задачи также неоднозначно. Результатом решения данной задачи будет множество вариантов связного графа H1, … , Hk.. Необходимо выбрать граф Нi, у которого min обход (по числу проходимых дуг). Такой выбор осуществляется с помощью известного метода построения тупикових тестов [6], для которых имеется ряд точных и приближенных алгоритмов решения.

Показано, что данный метод может строить более качественные контрольные эксперименты.

СПИСОК ЛИТЕРАТУРЫ

1. Харари Ф. Теория графов / Ф. Харари – М.: Мир, 1973. – 300 с.

2. Сапунов С.В. Анализ графов с помеченными вершинами / С.В. Сапунов // Дисс. канд. физ.– мат. наук: 27.09.07. – Донецк: 2007. – 150 с.

3. Кудрявцев В.Б. Введение теорию автоматов / В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин – М.: Наука, 1985. – 320 с.

4. Сапунов С.В. Контроль детерминированных графов / С.В. Сапунов // Труды ИПММ НАНУ, 2003. – т. 8. – С. 106–110.

5. Грунский И.С. Свойства языков, порождаемых неориентированными графами с отмеченными вершинами / И.С. Грунский, А.Н. Курганский // Материалы VIII Международного семинара «Дискретная математика и ее приложения» 6.02.2004. – М.: Изд-во механико-математического факультета МГУ, 2004. – С. 267–269.

6. Чегис И.А., Яблонский С.В. Логические способы контроля работы электронных схем / И.А. Чегис, С.В. Яблонский // «Труды математического института им. В.А. Стеклова», 1958. – т. 50. – С. 270?360.

                                                                                                                                                   Надійшла до редакції 2008 р.