Обход неизвестного ориентированного графа конечным роботом




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




И.Б.Бурдонов.
ОБХОД НЕИЗВЕСТНОГО ОРИЕНТИРОВАННОГО ГРАФА КОНЕЧНЫМ РОБОТОМ.
"Программирование". 2004. No. 4.


Обход неизвестного ориентированного графа конечным роботом


И.Б.Бурдонов

Institute for System Programming of Russian Academy of Sciences (ISPRAS),

B. Communisticheskaya, 25, Moscow, Russia

igor@ispras.ru

http://www.ispras.ru/˜RedVerst/


Abstract. Обход ориентированного графа – это маршрут, проходящий через все вершины и дуги графа, причем дуга проходится только в направлении ее ориентации. Обход, начинающийся с любой начальной вершины, существует только для сильно-связных графов, в которых из каждой вершины можно попасть в каждую вершину по некоторому маршруту. Сильная связность – это единственное ограничение на рассматриваемый класс графов. Как известно, на классе таких графов длина обхода (nm), где n – число вершин, а m – число дуг графа. Для любого графа существует обход длиной O(nm) и существуют графы с минимальной длиной обхода (nm). Обход неизвестного графа означает, что топология графа заранее неизвестна и мы узнаем ее только в процессе движения по графу. В каждой вершине видно, какие дуги из нее исходят, но в какую вершину ведет дуга можно узнать, только пройдя по ней. Это аналогично задаче обхода лабиринта роботом, находящимся внутри него и не имеющем плана лабиринта. Если робот – это «компьютер общего вида» без ограничения на число его состояний, то известны алгоритмы обхода с той же оценкой O(nm).


Если число состояний ограничено, то робот – это конечный автомат. Такой робот является аналогом машины Тьюринга: лента заменена графом, а ее ячейки привязаны к вершинам и дугам графа. В настоящее время неизвестна нижняя оценка длины обхода конечным роботом. В 1971 г. автор статьи предложил робот с длиной обхода O(nm+n2logn). Алгоритм робота основан на построении остова графа, ориентированного от корня, и метода поиска в ширину (BFS) на этом остове. В 1993 г. Y.Afek и E.Gafni [1] описали алгоритм с той же оценкой длины обхода, также основанный на построении остова графа, но использующий метод поиска в глубину (DFS). В настоящей статье предлагается алгоритм, совмещающий поиск в ширину (BFS) с методом отката по остову графа (backtracking), предложенным Y.Afek и E.Gafni, за счет чего достигается оценка O(nm+n2loglogn). Робот использует константное число битов памяти для каждой вершины и дуги графа.

  1. Введение



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

В большинстве работ предполагается, что граф задан явно до построения его обхода [12,13]. Более сложным является случай, когда до начала работы о графе ничего неизвестно и мы получаем информацию об устройстве графа в процессе его обхода [2,9]. Это известная задача обхода лабиринта [14] человеком или устройством, находящимся внутри него и не имеющим плана лабиринта. Дуге графа соответствует коридор лабиринта, а вершине – перекресток. Находясь на перекрестке, мы видим исходящие из него коридоры, но мы не знаем, куда ведет тот или иной коридор, до тех пор, пока не прошли по нему до следующего перекрестка. Для выполнения нашей задачи мы, во-первых, имеем некоторую внутреннюю память (блокнот в руках человека), куда можем записывать полученную информацию о пройденной части лабиринта, и, во-вторых, делать пометки в пройденных перекрестках и коридорах. Ориентированному графу соответствует лабиринт, в котором все коридоры «с односторонним движением».

Если внутренняя память ограничена конечным числом состояний, мы имеем робот (конечный автомат) на графе как разновидность машины Тьюринга [1,3,4,10,11,15]. Вместо ленты у нас есть граф, ячейке ленты соответствует вершина графа, а движение влево или вправо заменяется на переход по одной из дуг, исходящих из текущей вершины графа. Робот должен каким-то образом указывать, по какой исходящей дуге он перемещается. Если дуги, исходящие из вершины v перенумерованы 1..dout(v), где dout(v) – полустепень исхода вершины v, робот может указывать номер исходящей дуги. Однако, чтобы выходной алфавит робота оставался конечным, граф должен иметь ограничение сверху на полустепень исхода dout.


Это ограничение легко снимается, если в каждой вершине v добавить столько ячеек памяти, сколько дуг исходит из v (полустепень исхода dout), и связать эти ячейки в цикл, который будем называть v-циклом. Для робота добавляется внутреннее перемещение на ячейку следующей по v-циклу дуги. При внешнем перемещении по дуге (v,v`) робот попадает в ячейку первой дуги в v`-цикле. Тем самым, роботу не нужно идентифицировать дугу, а достаточно указать, какой переход он делает: внешний (o) или внутренний (i) (рис.1).




Рис.1: Вершина v и v-цикл исходящих дуг


Мы будем считать, что роботу одновременно доступны для чтения и записи две ячейки: ячейка вершины и ячейка текущей дуги, исходящей из этой вершины. Заметим, что это не является ограничением. Если ячейка вершины v отсутствует, то вместо нее всегда может использоваться ячейка первой дуги v-цикла. Попадая в вершину, робот считывает информацию о вершине из ячейки первой дуги и запоминает ее в своем состоянии. Для изменения информации о вершине, робот по v-циклу перемещается в ячейку первой дуги и делает запись в нее. Предполагается, что первоначально все ячейки пусты (содержат стандартный пустой символ).


Задача обхода графа конечным роботом была поставлена М.О. Рабином в 1967 г. [15].


Автор настоящей статьи занимался этой проблемой в 1969-1971 гг., во время обучения на механико-математическом факультете Московского Государственного Университета. В то время было известно, что на классе сильно связных ориентированных графов длина (нероботного) обхода (nm), где n – число вершин, а m – число дуг графа. Для любого графа существует обход длиной O(nm) и существуют графы с минимальной длиной обхода (nm). Также был известен робот R0 с одним состоянием, который мог обходить любой сильно-связный ориентированный граф за экспоненциальное время, но не умел останавливаться после завершения обхода. Этот робот проходит дуги, исходящие из вершины, все время по одному и тому же циклу: 1,2,...,dout,1,2,….


Автору удалось показать [5], что экспонециальная длина маршрута и невозможность остановки имеют место для любого робота с одним состоянием. Также были предложены два робота для графов с ограниченной полустепенью исхода. Оба алгоритма были основаны на построении в процессе обхода графа out-дерева – остова графа, ориентированного от корня, и леса in-деревьев, ориентированных к корням. Эти деревья позволяли роботу найти путь из конца пройденной дуги в ее начало. Алгоритмы обходили out-дерево, используя различные методы. Первый робот R1 использовал поиск в глубину (DFS) и строил обход длиной O(n3), второй робот R2 использовал поиск в ширину (BFS) и строил обход длиной O(n2logn). В переложении для графа без ограничения на полустепень исхода, но с v-циклами дуг, эти оценки имеют вид O(nm+n3) и O(nm+n2logn).


В обеих оценках второе слагаемое возникает из-за проблемы отката (backtracking): необходимости в процессе поиска по out-дереву n-1 раз возвращаться в предыдущую вершину дерева (ближе к корню). Хотя для отката по одной дуге нужно пройти простой путь длиной O(n), робот, не умеющий «заглядывать вперед», вынужден многократно проходить такой путь для поиска нужной вершины. Робот R1 строил простой out-путь от начальной вершины и лес in-деревьев, позволявший ему из любой пройденной вершины попасть на out-путь. Когда все дуги, исходящие из конца out-пути оказывались пройденными, роботу требовалось вернуться из конца out-пути в предыдущую вершину. Для этого использовался контур из простого in-пути и простого out-пути. Робот помечал первую вершину на out-части контура и, проходя одну дугу, запоминал, не является ли ее конец концом out-пути. Если нет, то на следующем проходе метка смещалась на следующую вершину контура. В результате требовалось O(n) проходов и суммарно на все возвращения тратилось O(n3) проходов по дугам. Робот R2 использовал тот же прием, но вместо out-пути у него было out-дерево и метка смещалась не на следующую врешину, а на ближайшую развилку этого out-дерева. За счет этого суммарная оценка уменьшалась до O(n2logn).


В 1978 г. появилась статья К. Кобаяши [17], где он представил останавливающийся алгоритм обхода экспоненциальной сложности, основанный на идее DFS. В 1988 г. С. Куттен [18] предложил алгоритм обхода минимальной сложности O(nm), но его робот не был конечным, так как использовал ячейки графа с логарифмическим (от числа вершин) количеством битов памяти. Наконец, в 1993 г. Y.Afek и E.Gafni [1] предложили конечный робот A (который они назвали Traversal-3), основанный на поиске в глубину (DFS), с оценкой длины обхода O(nm+n2logn). Этот робот похож на робот R1, но делает меньшее число проходов по каждому контуру при откате. Для этого метка ставится на всех вершинах out-пути, кроме его конца, и определяется четность числа помеченных вершин. На следующем проходе удаляются метки с вершин противоположной четности и заново определяется четность числа оставшихся помеченными вершин, и так далее до тех пор, пока не останется одна помеченная вершина – предпоследняя вершина out-пути. За счет этого «метода четности» вместо O(n) проходов достаточным оказывается O(logn) проходов.


Как практическая задача обхода графов возникает в сетях передачи данных. Граф интерпретируется как сеть, вершины графа – это узлы сети, а дуги – соединения. Изучение распределенных сетей обычно фокусируется на двунаправленных сетях, соответствующих неориентированным графам. Однако, с однонаправленными сетями (ориентированные графы) приходится иметь дело чаще, чем это можно было бы ожидать. Во-первых, однонаправленные сети возникают как результат сбоев или разрушениях в соединениях. Например, модемная БИС на одном конце соединения может перестать принимать (или посылать) данные, но продолжать работать в другом направлении. Кроме того, односторонние соединения можно обнаружить в радиосетях с асимметричными матрицами передачи как результат различий в пропускной способности станций, в оптоволоконных сетях, и в СБИС [11].


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


В некоторых приложениях, таких как СБИС, размер памяти в узлах и длина сообщения ограничены. Именно в этом случае возникает проблема алгоритмического обхода с константным числом битов в каждом узле и с процессом обхода, несущим конечное количество информации (во второй интерпретации, в однонаправленной сети конечных автоматов, в которой циркулирует единственное сообщение конечной длины).


Интерес автора к этой проблеме вновь возник в 90-ые годы во время работы в группе RedVerst [16], занимающейся задачей тестирования на основе имплицитных формальных спецификаций программных объектов, моделируемых конечными автоматами [6,7,8,19,20]. Здесь также возникает проблема обхода неизвестного графа состояний тестируемого автомата. Правда, как правило, не требуется реализация алгоритма обхода конечным роботом. Некоторым «побочным» результатом этой работы стал предлагаемый в настоящей статье робот R3, совмещающий поиск в ширину робота R2 и «метод четности» робота A. В результате достигается оценка длины обхода O(nm+n2loglogn).
  1   2   3   4   5   6

Похожие:

Обход неизвестного ориентированного графа конечным роботом iconНеизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай
Необходимой, а иногда и достаточной, частью такого тестирования является обход графа состояний автомата. Основное внимание уделяется,...
Обход неизвестного ориентированного графа конечным роботом iconТема: Представление информации в форме графа
Цель: Познакомить учащихся с понятием графа, историей возникновения и развития теории графов, представлением информации в форме графа...
Обход неизвестного ориентированного графа конечным роботом iconОриентированного графа
Они позволяют анализировать программу, работая с ее компонентами, а не исходным кодом. Графическое представление упрощает отладку...
Обход неизвестного ориентированного графа конечным роботом iconОбъезд препятствий мобильным роботом, снабжённым одной телекамерой
При управлении мобильным роботом возникают три главных задачи: определение текущих координат робота, построение траекторий движения...
Обход неизвестного ориентированного графа конечным роботом iconАнализа естественноязыковых текстов доц. М. И. Гринчук 1 год
Грамматики с конечным числом состояний. Приведение грамматики к стандартному (однозначному) виду. Объединение, пересечение и дополнение...
Обход неизвестного ориентированного графа конечным роботом iconИспользование конструктора образовательных веб-сайтов Edu of ru
Удобно представлять модель веб-сайта графически – в виде ориентированного графа, в котором узлы соответствуют документам, а стрелки...
Обход неизвестного ориентированного графа конечным роботом iconПлан введение сущность объектно-ориентированного подхода к программированию > Объектно-ориентированный анализ Процесс объектно-ориентированного проектирования > Пример объектно-ориентированного анализа
Первый объектно-ориентированный язык программирования Simula 67 был разработан в конце 60-х годов в Норвегии. Авторы этого языка...
Обход неизвестного ориентированного графа конечным роботом iconРеконструкции автомобильной дороги м-32” Гр. Рф (на Самару) Шымкент”, участок км. 1807-1837 (обход г. Кызылорда)

Обход неизвестного ориентированного графа конечным роботом iconУроках математики, как одно из условий успешной реализации личностно ориентированного обучения
I. Психологический аспект личностно ориентированного обучения
Обход неизвестного ориентированного графа конечным роботом iconМетодические рекомендации при изучении темы «Квадратные уравнения» в системе личностно ориентированного обучения
Теоретические основы личностно ориентированного обучения. 6 §2Квадратные уравнения в науке и школьных учебниках математики. 9
Разместите кнопку на своём сайте:
Библиотека


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