Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай




Скачать 449.33 Kb.
НазваниеНеизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай
страница1/5
Дата13.02.2013
Размер449.33 Kb.
ТипЗадача
  1   2   3   4   5




И.Б.Бурдонов, А.С.Косачев, В.В.Кулямин.
НЕИЗБЫТОЧНЫЕ АЛГОРИТМЫ ОБХОДА ОРИЕНТИРОВАННЫХ ГРАФОВ. ДЕТЕРМИНИРОВАННЫЙ СЛУЧАЙ.
"Программирование". 2003. No. 5.



Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай.



И.Б.Бурдонов, А.С.Косачев, В.В.Кулямин


Рассматриваются проблемы тестирования программных систем, моделируемых детерминированными конечными автоматами. Необходимой, а иногда и достаточной, частью такого тестирования является обход графа состояний автомата. Основное внимание уделяется, так называемым, неизбыточным алгоритмам обхода, которым не требуется заранее заданной полной структуры графа («обход неизвестного графа» или «on-line алгоритмы»).

1.Введение



Задача обхода графа, то есть, построения маршрута, проходящего по всем ребрам графа, хорошо известна. Ее специальным случаем является задача китайского почтальона [6,7,27], в которой обход должен иметь минимальную длину или минимальный вес для графа с заданными весами дуг. Для ориентированного графа задача усложняется, поскольку маршрут должен проходить каждое ориентированное ребро (дугу) только в направлении его ориентации.


В большинстве работ предполагается, что граф задан явно до построения его обхода [17,19]. Более сложным является случай, когда до начала работы о графе ничего неизвестно и мы получаем информацию об устройстве графа в процессе его обхода [20,24,25]. Это известная задача обхода лабиринта [10] человеком или устройством, находящимся внутри него и не имеющим плана лабиринта. Дуге графа соответствует коридор лабиринта, а вершине – перекресток. Находясь на перекрестке, мы видим выходящие из него коридоры, но мы не знаем, куда ведет тот или иной коридор, до тех пор, пока не прошли по нему до следующего перекрестка. Для выполнения нашей задачи мы, во-первых, имеем некоторую внутреннюю память (блокнот в руках человека), куда можем записывать полученную информацию о пройденной части лабиринта, и, во-вторых, делать пометки в пройденных перекрестках и коридорах. Ориентированному графу соответствует лабиринт, в котором каждый коридор закрыт с обеих сторон дверями: входная дверь открывается только с перекрестка, а выходная – только изнутри коридора, что разрешает двигаться по каждому коридору только в одном направлении.


Алгоритм, работающий на таком не заданном заранее графе, будем называть неизбыточным алгоритмом. Такие алгоритмы называются в литературе также online-алгоритмами. Его частным случаем, когда внутренняя память ограничена конечным числом состояний, является робот (конечный автомат) на графе как разновидность машины Тьюринга [3,5,8,9,12,18,24,28]. Вместо ленты у нас есть граф, ячейке ленты соответствует вершина графа, а движение влево или вправо заменяется на переход по одной из дуг, выходящих из текущей вершины графа. (Чтобы автомат робота был конечным, граф должен иметь ограничение сверху на полустепень выхода вершины – число выходящих дуг. Это ограничение можно снять, если каждой дуге также поставить в соответствие ячейку и ячейки всех дуг с общим началом связать в цикл.)


В последнее время задача обхода ориентированных графов стала особенно актуальной в связи с тестированием конечных автоматов, точнее, объектов, рассматриваемых как конечные автоматы. Написано довольно много работ о тестировании конечных автоматов. Например, обстоятельный обзор таких работ представлен в статьях Lee и Yannakakis [15] и Bochmann и Petrenko [13].


Автомат определяется множеством своих состояний и переходов. Переход автомата – это четверка (v,x,y,v`), где v – пресостояние, x – стимул, y – реакция, v` – постсостояние. Обычно автомат задается графом состояний, вершины которого – состояния, а дуги – переходы. Автомат (граф состояний) всюду определен, если в каждом состоянии v допустим каждый стимул x, то есть, существует хотя бы один переход вида (v,x,y,v`). В противном случае, автомат частично определен. Автомат (граф состояний) детерминирован, если пресостояние и стимул однозначно определяют реакцию и постсостояние. В настоящей статье мы ограничимся рассмотрением только детерминированных частично определенных автоматов, а недетерминированный случай рассмотрим в следующей статье.


Если граф состояний автомата известен, то обычно интересуются вопросами, удовлетворяет ли он тем или иным требованиям. Эти задачи решаются аналитическими методами и о тестировании обычно речь не идет. Тестирование нужно тогда, когда граф состояний автомата неизвестен. Автомат рассматривается как «черный ящик»: мы можем подавать на автомат стимулы и получать ответную информацию о выполненном переходе, то есть, в общем случае, о реакции и постсостоянии. Задачей тестирования является проверка того, что тестируемый автомат удовлетворяет заранее заданным спецификационным требованиям. Это тестирование соответствия (conformance testing) в широком смысле. В общем случае спецификация не подразумевает проверки каждого перехода автомата. Если, например, мы хотим проверить, что число состояний автомата не меньше заданного, то тестирование прекращается, как только мы в этом убедимся, и оставшиеся непроверенными переходы нас не интересуют. Однако, такие требования являются скорее исключением, чем правилом. Обычно нас интересует полная функциональность автомата, и нам требуется проверка каждого его перехода. Такое тестирование опирается на следующие предположения.


Изменение состояния. Состояние меняется только в результате тестового воздействия, то есть, подачи стимула на автомат. С одной стороны, это означает, что автомат находится под исключительным управлением теста и никто «не мешает» тестированию, точнее, такое постороннее воздействие не изменяет наблюдаемую функциональность автомата. (Информацию о тестировании при наличии таких «помех» можно найти в работах по тестированию «серым ящиком» или «полууправляемому» тестированию [14,23].) С другой стороны, это означает, что у теста нет других средств изменить состояние автомата. Если бы множество состояний было известно (неизвестны только переходы) и имелась возможность произвольно менять состояние с помощью прямой записи или специальной (нетестируемой) операции, задача перебора всех переходов автомата стала бы тривиальной. Априорное знание о множестве состояний реализации – сильное требование; обычно мы узнаем о нем только в процессе тестирования и только «поэлементно», то есть, о существовании состояния мы узнаем только после перехода в него.


Допустимость стимулов. В каждый момент времени мы можем тем или иным способом узнать, какие стимулы можно подавать на автомат. Понятно, что в противном случае ни о каком тестировании не может идти речь. Заметим, что во многих работах [15] эта проблема обходится предположением, что автомат всюду определен, то есть, во всех состояниях допустимы все стимулы из его алфавита стимулов. Следует также отметить, что на практике нам важна допустимость только «интересующих» нас стимулов, по которым проводится тестирование, то есть, стимулов, определенных в модели. Если в реализации допустимы какие-то другие стимулы, то это не влияет на тестирование. Фактически, это означает, что для реализации R и модели M тестируется подавтомат R(M)R, определяемый переходами по модельным стимулам и состояниями, достижимыми из начального по таким переходам.


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

Отдельно стоит вопрос о наблюдаемости состояний автомата. Если в любой момент времени мы можем узнать состояние автомата, прочитав его или получив в ответ на специальную операцию status message (предполагается, что операция не изменяет состояние) [15], то такое тестирование будем называть тестированием с открытым состоянием. В противном случае, будем говорить о тестировании со скрытым состоянием.


Специальный случай тестирования соответствия (в узком смысле), когда спецификация – это модельный автомат, эксплицитно заданный своим графом состояний, и проверяется эквивалентность реализационного (тестируемого) автомата модельному [15]. Два состояния (одного или разных автоматов) эквивалентны, если любая последовательность стимулов, допустимая, начиная с одного состояния, допустима, начиная с другого состояния, и вызывает одну и ту же последовательность реакций. Автоматы эквивалентны, если каждому состоянию одного автомата соответствует эквивалентное ему состояние другого автомата. Модельный автомат, тем самым, описывает класс эквивалентных ему реализационных автоматов.


При наличии модельного автомата тестирование с открытым состоянием сводится к обходу модельного графа [15], при котором каждый модельный переход сопровождается подачей на реализационный автомат того же стимула и проверкой того, что получаемые реализационные реакция и постсостояние такие же, как в модельном переходе. Заметим, что в такой постановке задачи, поскольку модельный граф известен, не требуется неизбыточности алгоритма обхода. Если реализационное состояние нам недоступно (тестирование со скрытым состоянием), приходится вводить специальные ограничения на реализацию и модель и прибегать к гораздо более сложным методам проверяющих последовательностей (checking sequence) [15]. Обход модельного графа в этом случае недостаточен, но, очевидно, также необходим, и также для этого не требуется неизбыточности алгоритма обхода.


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


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


Обычно считается, что спецификация описывает возможные, но не обязательные, переходы автомата. Если спецификация допускает несколько переходов по данному стимулу из данного пресостояния, то это не обязательно означает недетерминизм реализации. Допускается, чтобы реализация имела хотя бы один из таких переходов, но не обязательно все; детерминированная реализация должна иметь ровно один такой переход. Фактически, это означает, что модельному автомату соответствует не один класс эквивалентных реализационных автоматов, а семейство таких классов. Реализационный автомат, точнее, как сказано выше, его подавтомат R(M)R, определяемый модельными стимулами, эквивалентен некоторому подавтомату M(R) спецификационного автомата M, причем в каждом состоянии M(R) допустимы все стимулы, которые в этом состоянии допустимы в M, но среди всех переходов в M из данного состояния по данному стимулу не все должны присутствовать в M(R). (Иногда в этом случае говорят о квази-эквивалентности R и M(R) и редукции R к M [13].) Понятно, что в этом случае, во-первых, работа по эксплицированию спецификационного автомата M может оказаться чрезмерной, так как нам требуется только его подавтомат M(R), число состояний и переходов которого может быть во много раз меньшим, чем в M. Во-вторых, сам M(R) заранее неизвестен, поскольку определяется не только M, но и R.


Можно также отметить, что недетерминированный спецификационный автомат M может использоваться для тестирования детерминированных реализационных автоматов R [16]. В этом случае эксплицированный подавтомат M(R) также детерминирован. Это важно, поскольку тестирование детерминированных автоматов намного проще тестирования недетерминированных.


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


В части 2 настоящей статьи формулируются основные понятия графа, обхода и алгоритма. В части 3 изучается проблема существования и длины обхода графов. В части 4 предлагаются неизбыточные алгоритмы обхода. В части 5 описывается применение этих алгоритмов в тестировании.
  1   2   3   4   5

Похожие:

Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconМетодические указания к выполнению лабораторных работ по курсу "Дискретная математика"
Ализом метрических свойств, связности, независимости, паросочетаний, покрытий и циклов неориентированных и ориентированных графов...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconОбход неизвестного ориентированного графа конечным роботом
Это аналогично задаче обхода лабиринта роботом, находящимся внутри него и не имеющем плана лабиринта. Если робот – это «компьютер...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconЛабораторная работа «представление графов. Алгоритмы на графах»
Изучить способы представления графов с помощью матриц: матрица смежностей, матрица инцидентности, матрица достижимости, другие матричные...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconсистема интеллектуального обхода web-сайтов
«скрытый веб». Метод основан на классификации web-форм при помощи дерева решений. Предложена модификация стандартной схемы обхода...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconМетодические указания по проведению лабораторных работ «Задачи декомпозиции графов» по курсу
Вых структурах. Дается содержательное описание объекта исследования, строится общая математическая модель, ставятся оптимизационные...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconТЕория конечных графов
Целью курса является изучение классической теории графов, а также применение методов теории графов в прикладных задачах
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconПрограмма наименование дисциплины: Теория конечных графов
Цели и задачи дисциплины: Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай icon3. Математические основы имитационного моделирования
Постановка задачи математического моделирования динамической системы. Основные подходы к созданию математической модели системы:...
Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай iconФильтр Калмана Лекция 12 Общие сведения по теории фильтрации
На нем основаны многие рекурсивные алгоритмы, известные как алгоритм Калмана. Среди всех алгоритмов следует выделить алгоритмы фильтрации,...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница