Направленный ациклический граф

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Directed acyclic graph.png

Направленный ациклический граф (ориентированный ациклический граф, DAG от англ. directed acyclic graph) — орграф, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса).

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

Оптимизация префиксного дерева[править | править вики-текст]

DAWG (англ. directed acyclic word graph) — компактная форма хранения префиксного дерева, списка слов, оптимизированная для выяснения, входит ли некое слово в данный список или нет. Сам список получить несложно рекурсивным обходом дерева. С точки зрения программы, осуществляющей обход или поиск, DAWG ничем не отличается от дерева, просто одинаковые поддеревья хранятся в единственном экземпляре.

Сам способ преобразования очевиден: поиск одинаковых поддеревьев и переподключение ссылок на единственный экземпляр. На самом деле помимо буквы в вершинах хранится флажок, указывающий, является ли данная буква последней. Так что для списков неповторяющихся слов преобразование в DAWG и обратно происходит без потерь (с точностью до порядка слов).