알고리즘 설계 및 분석|5가지 알고리즘

1) 분할 정복 방법

규모 n 문제의 경우 문제가 쉽게 해결될 수 있으면(예: 규모 n이 작음) 그렇지 않으면 직접 해결합니다. , 이를 직접 해결합니다. 서로 독립적이고 원래 문제와 동일한 형태를 갖는 k개의 작은 하위 문제로 분해한 다음 각 하위 문제의 솔루션을 결합하여 다음을 얻습니다. 원래 문제에 대한 해결책.

2) 역추적 방법(깊이 우선)

역추적 방법은 목표를 달성하기 위해 최적화 조건에 따라 전방향으로 탐색하는 최적화 검색 방법입니다. 그러나 검색이 특정 단계에 도달하고 원래 선택이 최적이 아니거나 목표 달성에 실패하는 것으로 밝혀지면 한 걸음 물러나 다시 선택합니다. 아무데도 갈 수 없을 때 되돌아갔다가 다시 시도하는 이 기술이 백트래킹(backtracking) 방법이다.

3) 그리디 방법은 전체를 고려하지 않고 항상 현재 최선의 선택을 합니다. 그것이 만드는 각 단계는 단계의 로컬 최적 선택일 뿐입니다. , 그러나 반드시 전체적으로 최적의 선택은 아닙니다. 최적의 해를 찾기 위해 가능한 모든 해를 다 동원할 필요는 없으므로 시간 소모가 적고 일반적으로 만족스러운 해를 빠르게 얻을 수 있으나 최적의 해를 얻을 수는 없다.

4) 동적 프로그래밍 방법

문제 해결에 있어서 각 의사 결정 단계마다 가능한 다양한 로컬 솔루션을 나열한 다음 특정 판단 조건을 기반으로 어떤 솔루션을 선택해야 하는지 설명합니다. 폐기되어 얻을 수 없음 최적 솔루션의 로컬 솔루션을 모든 단계에서 선별하여 모든 단계가 최적 솔루션이 되도록 글로벌 솔루션이 최적 솔루션임을 보장합니다.

5) 분기 및 경계 방법(폭 우선)

분할 정복 알고리즘으로 해결된 하위 문제는 서로 독립적입니다.

동적 프로그래밍 알고리즘은 최적의 하위 구조와 중첩되는 하위 문제의 속성을 가지고 있습니다.

그리디 알고리즘은 최적의 해를 추구하지 않고, 실현 가능한 해만을 추구하므로 최적의 하부 구조의 특성을 갖지 않습니다.

역추적 알고리즘은 문제의 해 공간을 그래프나 트리 구조로 변환한 후 깊이 우선 탐색 전략을 사용하여 순회 과정에서 가능한 모든 해 또는 최적을 기록하고 찾습니다. 솔루션.

분기 경계 알고리즘은 너비 우선 방식으로 솔루션 공간 트리를 검색한다는 점에서 역추적 알고리즘과 유사합니다.