Автор: Грунский И.С., Ковтун С.А.
Источник: Ковтун C.A. Построения контрольного
эксперимента для графов с отмеченными вершинами / И.С. Грунский,
С.А. Ковтун // II международная научно-практическая конференция
молодых учёных «Современная информационная Украина: информатика,
экономика, философия». – 2008. – т.8. – С. 78–80.
Задачи, связанные с анализом различных сред с помощью блуждающих по ним агентов (мобильных роботов, автоматов, поисковых программ и т.п.) [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
Будем говорить, что графы 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.