누군가가 방향성 비순환 그래프가 무엇인지 간단한 용어로 설명 할 수 있습니까? 위키 백과를 살펴 봤지만 프로그래밍에서 그 용도를 실제로 볼 수는 없습니다.
답변
다른 점을 가리키는 선이있는 점
답변
그래프 = 가장자리로 서로 연결된 노드로 구성된 구조
Directed = 노드 (가장자리) 사이의 연결은 방향을 갖습니다. A-> B는 B-> A와 동일하지 않습니다.
acyclic = “non-circular”= 가장자리를 따라 노드에서 노드로 이동하면 두 번째로 동일한 노드를 만나지 않습니다.
방향성 비순환 그래프의 좋은 예는 트리입니다. 그러나 모든 유 방향 비순환 그래프가 트리는 아닙니다.
답변
DAG (Directed Acyclic Graph)의 의미를 나타내는 많은 답변이 있지만 해당 응용 프로그램에 대한 답변은 없습니다. 여기 아주 간단한 것이 있습니다.
전제 조건 그래프 -엔지니어링 과정에서 모든 학생은 전제 조건과 같은 요구 사항을 따르는 과목을 선택하는 과제에 직면합니다. 이제 알고리즘 [A]에 대한 사전 필수 과정 없이는 인공 지능 [B]에 대한 수업을 수강 할 수 없습니다. 따라서 B는 A에 의존하거나 더 나은 용어로 A는 B로 향하는 우위를 가지고 있습니다. 따라서 노드 B에 도달하려면 노드 A를 방문해야합니다. 전제 조건이있는 모든 주제를 그래프에 추가하면 곧 분명해질 것입니다. , 그것은 방향성 비순환 그래프로 판명 될 것입니다.
주기가 있었다면 코스를 완료하지 못할 것입니다.
학생들이 과정에 등록 할 수 있도록하는 대학의 소프트웨어 시스템은 학생이 현재 과정에 등록하기 전에 필수 과정을 수강했는지 확인하기 위해 과목을 노드로 모델링 할 수 있습니다.
제 교수님이이 비유를 해주셨 고 복잡한 개념을 사용하는 것보다 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를 사용하여 프로그램 구성 요소의 적절한 빌드 순서를 보장합니다.
답변
몇 가지 답변이 그래프 사용 (예 : 네트워크 모델링)의 예를 제공했으며 “이것이 프로그래밍과 어떤 관련이 있습니까?”라고 물었습니다.
그 하위 질문에 대한 대답은 프로그래밍과 관련이별로 없다는 것입니다. 그것은 문제 해결과 관련이 있습니다.
연결 목록이 특정 문제 클래스에 사용되는 데이터 구조 인 것처럼 그래프는 특정 관계를 나타내는 데 유용합니다. 연결된 목록, 트리, 그래프 및 기타 추상 구조는 코드에서 구현할 수 있다는 점에서 프로그래밍과 만 연결됩니다. 그들은 더 높은 수준의 추상화에 존재합니다. 프로그래밍이 아니라 문제 해결에 데이터 구조를 적용하는 것입니다.
답변
DAG (Directed Acyclic Graph)에는 다른 그래프와 구별되는 다음과 같은 속성이 있습니다.
- 그들의 가장자리는 방향을 보여줍니다.
- 그들은주기가 없습니다.
글쎄요, 지금 당장 한 가지 용도를 생각할 수 있습니다. DAG ( Gate-For-Graphs 로 알려짐 -더 많은 기술적 세부 사항 )는 일련의 프로세스 및 리소스 (둘 다 DAG의 노드) 간의 종속성을 설명하므로 교착 상태를 감지하는 데 편리합니다. . 주기가 감지되면 교착 상태가 발생합니다.
답변
기본 그래프 용어를 이미 알고 있다고 가정합니다. 그렇지 않으면 그래프 이론 에 대한 기사에서 시작해야합니다 .
Directed 는 모서리 (연결)에 방향이 있다는 사실을 나타냅니다. 다이어그램에서 이러한 방향은 화살표로 표시됩니다. 그 반대는 무 방향 그래프로, 간선이 방향을 지정하지 않습니다.
비순환 이란 임의의 노드 X에서 시작하여 가능한 모든 에지를 통과하는 경우 이미 사용 된 에지로 돌아 가지 않고는 X로 돌아갈 수 없음을 의미합니다.
여러 응용 프로그램 :
