Алгоритмы уточняющего обхода графов

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

Определение. Алгоритмом движения по графу называется алгоритм, который в процессе своей работы строит маршрут в графе.

Определение. Алгоритмом уточняющего движения по графу с уточняемыми вершинами называется алгоритм, который в процессе своей работы строит уточняющий маршрут в графе.

Как и в работе [], будем считать, что алгоритму предоставляются две специальные внешние операции status(), возвращающая идентификатор текущей вершины, и call(x), которая осуществляет переход из текущей вершины по дуге, помеченной стимулом x. Для детерминированного графа такая дуга, если существует, то единственная. Предусловием операции call(x) является допустимость стимула x в текущей вершине. Маршрут строится алгоритмом как последовательность дуг, проходимых последовательными вызовами операции call().

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

Определение. Для маршрута в графе вершину будем называть завершенной, если этот маршрут содержит все выходящие из вершины дуги.

Определение. Неизбыточным алгоритмом называется алгоритм движения по графу, который зависит только от пройденной части графа и допустимости стимулов в текущей вершине.

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

Определение. Алгоритмом уточняющего обхода графа называется алгоритм, который в процессе своей работы строит уточняющий обход графа.

Нас будут интересовать только такие алгоритмы, которые останавливаются через конечное число шагов.

Рассмотрим общую схему неизбыточных алгоритмов обхода графов. // пока есть незавершенные вершины while (!сompleted()) { // если текущая вершина незавершена if (next(status()) != ) { // подать очередной стимул call(next(status())); } else { // попасть в пройденную незавершенную вершину rollback(); } }

Операция completed() возврашает true тогда и только тогда, когда в графе все вершины завершены, то есть не существует вершин графа, из которых ведут не пройденные дуги.

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

конечными,
монотонными,
детерминированными,
открытыми,
сильно-связными

существует неизбыточный алгоритм уточняющего обхода. Доказательство. Рассмотрим следующий алгоритм, точнее его идею, в рамках определенной ранее схемы. Поскольку граф является монотонным, любой маршрут в нем является уточняющим, следовательно, для него определены уровни неопределенности. Алгоритм хранит в памяти некоторую структуру данных, связанных с текущим уровнем неопределенности, например, подобную описанной в работе []. Операция complete() возвращает true тогда и только тогда, когда все пройденные вершины на текущем уровне неопределенности завершены, то есть операция next() для них возвратила ε . Операция rollback() строит маршрут из текущей вершины в незавершенную вершину текущего уровня неопределенности, в которой есть еще не пройденные дуги. Например, это можно сделать на основе остова []. Поскольку различные вершины одного уровня неопределенности несравнимы в отношении уточнения, пройденный на текущем уровне неопределенности граф является подграфом некоторой информационной проекции исходного графа, а следовательно, является детерминированным и сильно-связным что и требуется в []. В случае, если в операции call(x) происходит выбор дуги в вершину, уточняющую одну из вершин текущего уровня неопределенности, текущий уровень неопределенности изменяется, структуры данных освобождаются, алгоритм работает так, как если бы новое состояние было начальным. Поскольку граф конечен, детерминирован и сильно-связен, любая его информационная проекция является конечной, детерминированной и сильно-связной, поэтому внутри любого уровня неопределенности, за исключением последнего, можно гарантированно достичь вершину, в которой допустим стимул, такой что операция call обязательно выберет дугу, выводящую из этого уровня неопределенности.Такие вершина и стимул существуют, поскольку граф является открытым. Таким образом, за конечное число шагов алгоритм достигнет последнего уровня неопределенности, состоящего из полностью определенных вершин исходного графа. Обход которого завершит уточняющий обход исходного графа.

Содержание раздела