Может ли кто-нибудь объяснить мне в простых терминах, что такое направленный ациклический граф?

графика = структура, состоящая из узлов, которые соединены друг с другом с края

directed = соединения между узлами (ребрами) имеют направление: A -> B не то же самое, что B -> A

acyclic = "некруглый" = перемещение от узла к узлу по краям, вы никогда не столкнетесь с тем же узлом во второй раз.

хорошим примером направленного ациклического графа является дерево. Обратите внимание, однако, что не все направленные ациклические графы являются деревья.

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

предварительный график - во время инженерного курса каждый студент сталкивается с задачей выбора предметов, которые соответствуют требованиям, таким как предварительные условия. Теперь ясно, что вы не можете взять класс по искусственному интеллекту[B] без предварительного курса по алгоритмам[A]. Следовательно, B зависит от A или в лучших терминах A имеет ребро, направленное на B. Таким образом, чтобы достичь узла B, вам нужно посетить узел A. вскоре будет ясно, что после добавления всех предметов с его предпосылками в граф он окажется направленным ациклическим графом.

Если бы был цикл, то вы никогда не закончили бы курс: p

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

мой профессор дал эту аналогию, и это лучше всего помогло мне понять DAG, а не использовать какую-то сложную концепцию!

другой пример в реальном времени ->в реальном масштабе времени пример как DAG можно использовать в системе версии

примеры использования направленного ациклического графа в программировании включают в себя более или менее все, что представляет связность и причинность.

например, предположим, что у вас есть конвейер вычислений, который настраивается во время выполнения. В качестве одного из примеров этого предположим, что вычисления A,B,C,D,E, F и G зависят друг от друга: a зависит от C, C зависит от E и F, B зависит от D и E, А D зависит от F. Это можно представить как DAG. После того, как у вас есть DAG в памяти, вы можете написать алгоритмы для:

• убедитесь, что вычисления выполняются в правильном порядке (топологическая сортировка)
• если вычисления могут выполняться параллельно, но каждое вычисление имеет максимальное время выполнения, вы можете вычислить максимальное время выполнения всего набора

среди многих других вещей.

вне сферы прикладного программирования, любой достойный автоматизированный инструмент сборки (make, ant, scons и т. д.) будем использовать группы доступности баз данных для обеспечьте правильный порядок сборки компонентов программы.

несколько ответов дали примеры использования графиков (например, сетевое моделирование), и вы спросили: "какое это имеет отношение к программированию?".

ответ на этот подвопрос, что он не имеет ничего общего с программированием. Это связано с решением проблем.

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

направленные ациклические графы (DAG) имеют следующие свойства, которые отличают их от других графов:

1. их края показывают направление.
2. у них нет циклов.

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

Я надеюсь, что это помогает.

ура

Я предполагаю, что вы уже знаете основную терминологию графа; в противном случае вы должны начать со статьи на теория графов.

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

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

несколько приложений:

• электронные таблицы; это объясняется в Даг статьи.
• контроля версий: Если вы посмотрите на диаграмму на этой странице, вы увидите, что эволюция кода, контролируемого ревизией, направлена (она идет "вниз", на этой диаграмме) и ациклическая (она никогда не возвращается "вверх").
• Семейное дерево: он направлен (вы ребенок своих родителей, а не наоборот) и ациклический (ваши предки никогда не могут быть вашим потомком).

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

DAG-это граф, где все течет в одном направлении, и ни один узел не может ссылаться на себя.

подумайте о родословных деревьев; они на самом деле дагов.

У всех дагов есть

• узлы (места для хранения данных)
• направленные края (эта точка в том же направлении)
• предковый узел (узел без родителей)
• листья (узлы, которые не имеют детей)

DAG отличаются от деревья. В древовидной структуре должен быть уникальный путь между каждыми двумя узлами. В DAG узел может иметь два родительских узла.

здесь хорошая статья о DAGs. Надеюсь, это поможет.

С точки зрения исходного кода или даже трех адресов(TAC) вы можете легко визуализировать проблему на этой странице...

http://cgm.cs.mcgill.ca/~hagha / topic30 / topic30. html#Exptree

Если вы перейдете в раздел дерева выражений, а затем немного опустите страницу, он покажет "топологическую сортировку" дерева и алгоритм оценки выражения.

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

основной алгоритм вычисления DAG в не древнеегипетском (т. е. английском) заключается в следующем:

1) Сделайте свой объект DAG так

вам нужен живой список, и этот список содержит все текущие узлы Live DAG и DAG суб-выражения. Вложенное выражение DAG-это узел DAG, или его можно также назвать внутренним узлом. То, что я имею в виду под живым узлом DAG, заключается в том, что если вы назначаете переменной X, то она становится живой. Общее подвыражение, которое затем использует X использует этот экземпляр. Если X назначается снова, то новый узел DAG создается и добавляется в живой список, а старый X удаляется, поэтому следующее под-выражение, которое использует X, будет ссылаться на новый экземпляр и, таким образом, не будет конфликтовать с под-выражениями, которые просто используют то же самое имя переменной.

как только вы назначаете переменной X, то попутно все узлы суб-выражения DAG, которые находятся в режиме реального времени в точке назначения, становятся не-живыми, поскольку новое назначение делает недействительным значение суб-выражений с использованием старого значения.

class Dag {
  TList LiveList;
  DagNode Root;
}

// In your DagNode you need a way to refer to the original things that
// the DAG is computed from. In this case I just assume an integer index
// into the list of variables and also an integer index for the opertor for
// Nodes that refer to operators. Obviously you can create sub-classes for
// different kinds of Dag Nodes.
class DagNode {
  int Variable;
  int Operator;// You can also use a class
  DagNode Left;
  DagNode Right;
  DagNodeList Parents;
}

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

Так что для каждого XNode вам нужно чтобы решить, как добавить его в DAG, и есть вероятность, что он уже находится в DAG.

Это очень простой псевдокод. Не предназначен для компиляции.

DagNode XNode::GetDagNode(Dag dag) {
  if (XNode.IsAssignment) {
    // The assignment is a special case. A common sub expression is not
    // formed by the assignment since it creates a new value.

    // Evaluate the right hand side like normal
    XNode.RightXNode.GetDagNode();  


    // And now take the variable being assigned to out of the current live list
    dag.RemoveDagNodeForVariable(XNode.VariableBeingAssigned);

    // Also remove all DAG sub expressions using the variable - since the new value
    // makes them redundant
    dag.RemoveDagExpressionsUsingVariable(XNode.VariableBeingAssigned);

    // Then make a new variable in the live list in the dag, so that references to
    // the variable later on will see the new dag node instead.
    dag.AddDagNodeForVariable(XNode.VariableBeingAssigned);

  }
  else if (XNode.IsVariable) {
    // A variable node has no child nodes, so you can just proces it directly
    DagNode n = dag.GetDagNodeForVariable(XNode.Variable));
    if (n) XNode.DagNode = n;
    else {
      XNode.DagNode = dag.CreateDagNodeForVariable(XNode.Variable);
    }
    return XNode.DagNode;
  }
  else if (XNode.IsOperator) {
    DagNode leftDagNode = XNode.LeftXNode.GetDagNode(dag);
    DagNode rightDagNode = XNode.RightXNode.GetDagNode(dag);


    // Here you can observe how supplying the operator id and both operands that it
    // looks in the Dags live list to check if this expression is already there. If
    // it is then it returns it and that is how a common sub-expression is formed.
    // This is called an internal node.
    XNode.DagNode = 
      dag.GetOrCreateDagNodeForOperator(XNode.Operator,leftDagNode,RightDagNode) );

    return XNode.DagNode;
  }
}

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

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

что касается сортировки Dag, вы проходите через каждый DagNode слева направо. Другими словами, следуйте за левым краем DagNodes, а затем за правым боковым краем. Номера назначаются в обратном порядке. Другими словами, когда вы достигаете DagNode без дочерних узлов, назначьте этому узлу текущий номер сортировки и увеличьте номер сортировки, так как рекурсия разматывает номера, назначенные в порядке возрастания.

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

// Most basic DAG topological ordering example.
void DagNode::OrderDAG(int* counter) {
  if (this->AlreadyCounted) return;

  // Count from left to right
  for x = 0 to this->Children.Count-1
    this->Children[x].OrderDag(counter)

  // And finally number the DAG Node here after all
  // the children have been numbered
  this->DAGOrder = *counter;

  // Increment the counter so the caller gets a higher number
  *counter = *counter + 1;

  // Mark as processed so will count again
  this->AlreadyCounted = TRUE;
}

Если вы знаете, какие деревья в программировании, то DAG в программировании похожи, но они позволяют узлу иметь более одного родителя. Это может быть удобно, когда вы хотите, чтобы узел был сгруппирован под более чем одним родителем, но не имеет проблемы узловатого беспорядка общего графа с циклами. Вы все еще можете легко перемещаться по DAG, но есть несколько способов вернуться к корню (потому что может быть более одного родителя). Один DAG может вообще иметь несколько корней но на практике может быть лучше просто придерживаться одного корня, как дерево. Если вы понимаете одно и множественное наследование в ООП, то вы знаете дерево против DAG. Я уже ответил на это здесь.

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

Я не могу говорить со всеми видами использования (Википедия помогает там), но для меня DAG чрезвычайно полезны при определении зависимостей между ресурсами. Например, мой игровой движок представляет все загруженные ресурсы (материалы, текстуры, шейдеры, открытый текст, анализ json и т. д.) Как один DAG. Пример:

материал-это N программ GL, каждая из которых нуждается в двух шейдерах, и каждый шейдер нуждается в источнике шейдера открытого текста. Представляя эти ресурсы как DAG, я могу легко запросить график для существующих ресурсов, чтобы избежать повторяющихся нагрузок. Допустим, вы хотите, чтобы несколько материалов использовали вершинные шейдеры с одним и тем же исходным кодом. Это расточительно, чтобы перезагрузить источник и перекомпилировать шейдеры для каждого использования, когда вы можете просто установить новый край к существующему ресурс. Таким образом, вы также можете использовать график, чтобы определить, зависит ли что-либо от ресурса вообще, а если нет, удалите его и освободите его память, на самом деле это происходит почти автоматически.

по расширению, DAG полезны для выражения конвейеров обработки данных. Ациклическая природа означает, что вы можете безопасно писать код контекстной обработки, который может следовать указателям вниз по краям от вершины, никогда не пересчитывая одну и ту же вершину. Визуальные языки программирования, такие как ПППП,Max MSP или интерфейсы Autodesk Maya на основе узлов все полагаются на DAG.

направленный ациклический граф полезен, когда вы хотите представить...направленный ациклический граф! Канонический пример-генеалогическое древо или генеалогия.