Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 2

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

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

acyclic = "non-circle" = переход от node к node, следуя за ребрами, вы никогда не столкнетесь с тем же node во второй раз.

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

Ответ 3

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

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

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

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

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

Другой пример в реальном времени → Пример реального времени использования DAG в системе версий

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ну, я могу вспомнить одно использование прямо сейчас - DAG (известный как Wait-For-Graphs - больше технических подробностей) удобен для обнаружения взаимоблокировок, поскольку они иллюстрируют зависимости между множеством процессов и ресурсов (оба являются узлами в DAG). Тупиковая ситуация может возникнуть при обнаружении цикла.

Ответ 7

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

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

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

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

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

Ответ 8

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

Ответ 9

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

Подумайте о деревьях предков; они на самом деле DAG.

Все DAG имеют

  • Узлы (места для хранения данных)
  • Направленные края (которые указывают в одном направлении)
  • Родовой узел (узел без родителей)
  • Листья (узлы, которые не имеют детей)

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

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

Ответ 10

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

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

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

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

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

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

Вам нужен живой список, и этот список содержит все текущие узлы DAG и DAG-подвыражения. Дополнительное выражение DAG является DAG Node, или вы также можете назвать его внутренним node. То, что я имею в виду под живым DAG Node, состоит в том, что если вы назначаете переменную X, она становится живой. Общее подвыражение, которое затем использует X, использует этот экземпляр. Если X назначается снова, тогда создается новый DAG Node и добавляется в живой список, а старый 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;
}

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

Итак, для каждого 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 без детей, присвойте этому Node текущий номер сортировки и увеличьте номер сортировки, так как рекурсия освободит номера, назначенные в порядке возрастания.

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

// 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;
}

Ответ 11

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

Ответ 12

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

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

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

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

Ответ 13

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