Обход неизвестного ориентированного графа конечным роботом.
Обход неизвестного ориентированного графа конечным роботом.
Авторы
Аннотация
Обход ориентированного графа – это маршрут, проходящий через все вершины и дуги графа, причем дуга проходится только в направлении ее ориентации. Обход, начинающийся с любой начальной вершины, существует только для сильно-связных графов, в которых из каждой вершины можно попасть в каждую вершину по некоторому маршруту. Сильная связность – это единственное ограничение на рассматриваемый класс графов. Как известно, на классе таких графов длина обхода Θ(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). Робот использует константное число битов памяти для каждой вершины и дуги графа.
Издание
Программирование, №4, 2004.
Научная группа
Все публикации за 2004 год
Все публикации