Sorting, packing and network algorithms
도입됨| English | 의미 |
|---|---|
| algorithm/ˈælɡərɪθəm/ | 알고리즘 |
빠른 포장 방법이 항상 최적입니까?
- 포장 방법은 상자를 빠르게 채울 수 있으나, 유효한 빠른 배치 방식이 반드시 가장 적은 상자를 사용해야 하는 것은 아닙니다.
- 이 수업에서는 알고리즘을 다룹니다: 정의된 문제 유형의 해법을 제공하는 유한한 순서 Instruction(명령)의 집합입니다.
수학적 구조 선택하기
- 명시된 알고리즘을 정확히 추跡(tracing)하십시오, 그중 tie rules(동점 규칙)도 포함하여. first-fit packing(최적 적합 포장)에서는 각 물품을 수용할 수 있는 첫 번째 빈 바구니에 배치합니다. first-fit decreasing(최적 적합 감소 정렬)은 first-fit 적용 전에 정렬합니다. 히ュー리스틱(optimaity 보장이 없는 경험적 접근법)은 최적이지 않아도 유효할 수 있습니다.
- 계산 전에 허용된 입력값과 단위를 명시하라. 방정식은 단순히 계산기 입력 내용을 기록하는 것보다 관계성을 표현해야 한다.
First-fit used 2 bins for 6,5,4,3,2 with capacity 10, matching the lower bound. What may be concluded?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Meeting the lower bound proves optimality for this case only. A heuristic’s success on one example says nothing about worst cases - other item lists make first-fit exceed the bound.
검증된 사례를 풀이해 보기
- 시작값과 결과를 대조하십시오. 원본 관계에 대입하거나, 적절한 경우 그래프와 수치적 답을 비교하십시오.
바구니 용량 10과 물품 6,5,4,3,2을 해당 순서로 할 때, first-fit는 6와 4를 바구니 1에, 이후 5,3,2를 바구니 2에 배치합니다. 총 2개의 바구니를 사용합니다. 총 크기는 20이므로 하한은 ceil(20/10)=2이며, 이 배치는 해당 인스턴스에 대해 최적입니다.
Sorting, packing and network algorithms
Trace the named algorithm exactly, including its tie rules
Compare the model with the worked case and explain one change.
How many bins does the worked first-fit arrangement use?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
The first-fit arrangement fills two bins, each with total size 10.
유혹적인 단축법을 시험해 보십시오
- 성공 사례 예시는 히ュー리스틱이 항상 최적임을 증명하지 않습니다. 정렬 추跡(tracing) 중 중간 목록을 유지하고, 입력에서 최종 정렬된 목록으로 점프하지 마십시오. 경로 요청 시 shortest-path update(최단 경로 업데이트)는 전구자 predecessor 정보를 유지해야 합니다.
- 단축법이 실패하면 그 단축법이 위배하는 가정을 식별하십시오. 요청된 최종 반올림까지 정확한 값을 유지하십시오.
한 예제에서 잘 작동하는 포장 히어리즘이 항상 최적이어야 한다는 주장은 틀렸습니다. 이 주장이 어떤 정의나 가정과 모순되는지 설명하십시오.
Find the lower bound on bins for total size 20 and capacity 10.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Every bin holds at most 10, so at least ceiling(20/10)=2 bins are needed.
A packing heuristic that works well on one example must always be optimal.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
An example of success does not prove a heuristic is always optimal. Keep intermediate lists in a sorting trace; do not jump from input to a sorted final list. A shortest-path update must retain predecessor information if a route is requested.
새로운 상황을 해석하십시오
- 디(resolve)스트라法是：选择最小的未决临时标签并更新其邻居。对于路线检查问题，区分闭合路线与开放路线，并在配对前识别奇度顶点。
- 완전한 해답은 수학적 결과를 제시하고 그 의미를 설명해야 합니다. 주어진 맥락 내에서 가능한지 확인하십시오.
Find space remaining in a bin containing items 5,3,2 with capacity 10.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Unused capacity=10-(5+3+2)=0.
Match each packing rule to its action.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Trace the algorithm exactly as defined; the lower bound judges how good a packing could possibly be.
과정에 활용하십시오
- 에덱셀 IAL 수학; 공식 단위 D1. 다른 단원의 심화 과정은 범위 검토에서 식별되며, 추가 비용 항목이 아닙니다.
- 최종 답보다 방법을 먼저 제시하고, 시험지의 계산기 및 공식 규칙을 준수하십시오. 틀린 답을 검토할 때는 첫 번째 유효하지 않은 단계 위치를 찾아보십시오.
정해진 문제의 한 종류를 해결하는 유한 순서 지시들의 집합입니다. 관계를 선택하고, 방법을 보여주고, 가정을 확인하며 결과를 해석하십시오.