Применение теории автоматов

Содержание

Ключевае слова:
Автомат
Программирование
Визуализатор
Нейронные сети
Микроконтроллеры
Документооборот

Обход деревьев на основе автоматного подхода

Постановка задачи обхода двоичного дерева

Для реализации обхода вводится состояние, но автомат в явном виде не строится.


Двоичное дерево

Необходимо осуществить его обход — сформировать последовательность номеров его вершин. Три порядка обхода дерева: прямой (preorder), обратный (postorder) и центрированный (inorder). Такие порядки используются при обходе дерева в глубину.

Пример последовательностей, порождаемые обходами дерева, представленного на рис.3:

Данная задача может быть решена несколькими известными способами: рекурсивно, итеративно с применением стека и итеративно без использования стека.

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

Обход двоичного дерева без использования стека

Рассмотрим обход двоичного дерева без применения стека. Идея предлагаемого алгоритма состоит в том, что при обходе двоичного дерева могут быть выделены следующие направления движения: влево, вправо, вверх. Обход начинается от корня дерева. В зависимости от номера текущей вершины и направления движения, можно принять решение о том, куда двигаться дальше. При этом стек не требуется — используется указатель на родительскую вершину node.

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

Таким образом, автомат имеет следующие состояния:

Автомат оперирует переменной node, являющейся указателем на текущий узел дерева.

Граф переходов, описывающий поведение автомата. Переходы между состояниями определяются условиями, которыми помечают соответствующие дуги графа переходов. Условия node->l, node->r и node->p обозначают наличие у текущего узла левого потомка, правого потомка и родителя соответственно. Отрицание будем обозначать восклицательным знаком (!). Например, переход из состояния Parent в состояние Start осуществляется при условии, что у вершины нет родителя.

Некоторые дуги графа помечены не только условиями (расположены в числителе дроби), но и действиями (расположены в знаменателе дроби). Например, переход из состояния Right в состояние Left производится при условии, что у вершины есть правое поддерево. При этом на указанном переходе выполняется действие — изменяется переменная node, в которой хранится указатель на текущую вершину.

Кроме действий на переходах в автомате также выполняются действия в состояниях, например, в состоянии Left производится вывод номера текущей вершины на экран.


Граф переходов автомата для реализации нерекурсивного обхода двоичного дерева

В случае безусловного перехода из одного состояния в другое дуга помечается символом 1 (переход из нулевой вершины в первую). Еще одной особенностью этого графа является пометка дуг «числами с двоеточием» — приоритетами. Эти пометки указывают последовательность, в которой будут проверяться условия на дугах, исходящих из вершины. В случае если условия являются попарно ортогональными, то приоритеты не расставляются.

Данный подход позволяет, используя один и тот же граф переходов автомата, осуществлять все три обхода, за счет вывода номера текущей вершины только в одном из состояний: Left, Right, Parent. При этом в зависимости от выбранного состояния получим три стандартных обхода:

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


См. также
Пример 4 - Поиск цепочек в тексте


X