Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом.
Проблема отката по дереву при обходе неизвестного ориентированного графа конечным роботом.
Авторы
Аннотация
Обход ориентированного графа – это маршрут, проходящий через все вершины и дуги графа, причем дуга проходится только в направлении ее ориентации. Обход с любой стартовой вершины существует только для сильно-связных графов. Обход неизвестного графа означает, что топологию графа мы узнаем только в процессе движения по нему, что аналогично задаче обхода лабиринта роботом, находящимся внутри него и не имеющем плана лабиринта. Если робот – это «компьютер общего вида» без ограничения на число его состояний, то известны алгоритмы обхода с оценкой O(nm), где n – число вершин, а m – число дуг графа. Если число состояний ограничено, то робот – это конечный автомат, аналог машины Тьюринга, в которой лента заменена графом, а ее ячейки привязаны к вершинам и дугам графа. Выбор роботом еще не пройденной им дуги, исходящей из текущей вершины, определяется заданным извне порядком исходящих дуг для каждой вершины.
Наилучшие известные алгоритмы обхода для конечного робота основаны на построении выходящего остова графа с корнем в стартовой вершине и обходе его с целью поиска всех еще непройденных дуг. При этом возникает проблема отката (backtracking) по дереву: перебор всех вершин дерева в порядке обратном их естественной частичной упорядоченности – от листьев к корню. Поэтому верхняя оценка алгоритмов отличается от оптимальной O(nm) на величину, требуемую для совершения отката по выходящему дереву. Наилучшая известная оценка O(nm+n2loglogn) предложена автором в предыдущей статье [1].
В настоящей статье предлагается конечный робот, который выполняет откат по дереву с оценкой O(n2log*(n)). Функция log* определяется как целочисленное решение неравенства 1≤log2 log*(n)<2, где logt=log◦log◦…◦log (знак суперпозиции ◦ применяется t–1 раз) – t-ая композиционная степень логарифма. Для обхода графа соответствующая оценка O(nm+n2log*(n)) получается на любом сильно связном графе при некотором (но, к сожалению, не любом) порядке исходящих дуг. Интересно, что такой порядок дуг может быть отмечен символами конечного робота, совершающего обхода графа. Тем самым, можно построить робот, который дважды обходит граф, первый раз с оценкой
O(nm+n2loglogn), а второй раз с оценкой O(nm+n2log*(n)).
Издание
Программирование, №6, 2004.
Научная группа
Все публикации за 2004 год
Все публикации