알고리즘, 네트워크 및 선형 계획법
도입됨| English | 의미 |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | 최소 신장 트리 |
가장 저렴한 네트워크 또는 가장 짧은 경로?
- 학교가 건물들을 케이블로 연결해야 할 때, 두 건물 사이의 최단 경로와 전체 네트워크의 최소 비용은 서로 다른 문제입니다.
- 이 수업에서는 최소 스팬닝 트리(minimum spanning tree) 를 다룹니다: 모든 정점을 연결하되 총 간선 무게가 가장 작은 사이클이 없는 네트워크입니다.
수학적 구조 선택하기
- 크루스칼(Kruskal)은 사이클을 피하면서 간선을 무게가 증가하는 순서로 선택합니다. 디스트라(Dijkstra)는 시작점으로부터의 최단 가설 거리를 업데이트합니다. 선형 계획법은 허용 가능한 영역 내에서 선형 목적 함수를 최적화하며, 필요할 경우 꼭짓점과 정수 제한 사항을 점검하십시오.
- 계산 전에 허용된 입력값과 단위를 명시하라. 방정식은 단순히 계산기 입력 내용을 기록하는 것보다 관계성을 표현해야 한다.
크루스칼 알고리즘과 최단 경로 알고리즘이 예제 네트워크에서 모두 총 6을 산출했습니다. 왜 이 두 알고리즘은 서로 교체 가능하지 않은가요?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
목적이 다릅니다: 최소 신장 트리(MST)는 모든 정점을 연결(n-1개의 간선, 순환 없음)하는 반면, 최단 경로는 단일 기점-도착지 루트를 최적화합니다. 이번 사례에서 결과가 동일한 것은 우연에 불과합니다.
검증된 사례를 풀이해 보기
- 시작값과 결과를 대조하십시오. 원본 관계에 대입하거나, 적절한 경우 그래프와 수치적 답을 비교하십시오.
정점 A,B,C,D와 변 AB=2, BC=3, AC=4, CD=1, BD=5인 경우, 크루스칼 알고리즘은 CD, AB, BC를 선택하여 총 6를 얻습니다. A에서 D까지의 최단 경로는 A-B-C-D로, 역시 6이지만 이 동등성은 우연에 불과합니다. 3x+2y를 최대화하되 x+y≤4, x≤2, x,y≥0 조건을 만족할 때, 최적 정점은 (2,2)이며, 그 값은 10입니다.
알고리즘, 네트워크 및 선형 계획법
크루스칼(Kruskal)은 사이클을 형성하지 않으면서 가중치가 증가하는 순서로 간선을 선택한다.
모델과 풀이 사례를 비교하여 하나의 변화를 설명하시오.
예시 네트워크의 최소 스펜닝 트리 가중치를 구하시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
크스컬算法은 사이클이 없는 엣지 가중치 1,2,3를 선택하여 모든 정점을 연결합니다: 총합 6.
유혹적인 단축법을 시험해 보십시오
- 스팬닝 트리는 사이클이 없으며 모든 정점을 연결합니다. 가장 긴 단일 간선이 모든 최적 해에서 자동으로 제외되는 것은 아닙니다. 최단 경로 알고리즘은 최소 스팬닝 트리 알고리즘을 대체할 수 없습니다.
- 단축법이 실패하면 그 단축법이 위배하는 가정을 식별하십시오. 요청된 최종 반올림까지 정확한 값을 유지하십시오.
두 정점 사이의 최단 경로는 반드시 전체 네트워크의 최소 스팬닝 트리여야 한다고 주장하는 것은 틀렸습니다. 이 주장은 어떤 정의나 가정 위반을 설명하십시오.
예시 실현 가능 영역에서 3x+2y의 최대값을 구하시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
가능성 있는 꼭지점을 확인하시오: (2,2)은 3×2+2×2=10을 주어 가장 큰 목적 함수 값을 산출한다.
두 정점 사이의 최단 경로는 전체 네트워크의 최소 스펜닝 트리가 되야 합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
스펜딩 트리는 사이클이 없으며 모든 정점을 연결합니다. 가장 긴 단일 엣지가 모든 최적 해에서 자동으로 제외되지는 않습니다. 최단 경로 알고리즘은 최소 스펜닝 트리 알고리즘을 대체할 수 없습니다.
새로운 상황을 해석하십시오
- 임계 경로(critical paths)에 대해서는 earliest 및 latest 이벤트 시간을 계산하고, 슬랙(slack)이 0인 활동을 식별하십시오. 단위를 명시하고 최적해를 해석하십시오. 기존 아카이브에는 D1 쌍이 없으므로, 본 원본 과제는 검토된 D1 과거 고사 은행을 형성하지 않습니다.
- 완전한 해답은 수학적 결과를 제시하고 그 의미를 설명해야 합니다. 주어진 맥락 내에서 가능한지 확인하십시오.
4개의 정점을 가진 스펜딩 트리에 엣지는 몇 개 있습니까?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
n개의 정점을 가진 나무는 n-1개의 엣지를 가지므로, 네 개의 정점에는 세 개의 엣지가 필요합니다.
각 알고리즘을 그에 맞는 규칙과 짝지어 보십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
각 알고리즘은 자체 문제 클래스에 대해 정확합니다. 제시된 규칙(동점 처리 방법 포함)을 따라 추적을 수행해야 점수를 받을 수 있습니다.
과정에 활용하십시오
- 에덱셀 IAL 수학; 공식 단위 D1. 다른 단원의 심화 과정은 범위 검토에서 식별되며, 추가 비용 항목이 아닙니다.
- 최종 답보다 방법을 먼저 제시하고, 시험지의 계산기 및 공식 규칙을 준수하십시오. 틀린 답을 검토할 때는 첫 번째 유효하지 않은 단계 위치를 찾아보십시오.
모든 정점을 연결하면서 전체 간선 무게가 가장 작은 연결된 순환 없는 네트워크입니다. 관계 선택, 방법 제시, 가정 점검 및 결과 해석을 하십시오.