일반적으로 사용되는 알고리즘 설계 전략은 무엇입니까?

일반적인 알고리즘 설계 전략:

1. 분할 정복

분할 정복 방법의 설계 아이디어는 직접 해결하기 어려운 큰 문제를 k개의 작은 하위 문제로 나누는 것입니다. 문제는 서로 독립적이고 원래의 문제와 동일하며, 이후에는 별도로 해결되어 분할되어 정복됩니다.

분할 정복 방법은 재귀와 결합하여 자주 사용됩니다. 분할 정복을 반복적으로 적용하면 하위 문제가 원래 문제 유형과 일치하게 만들어지고 규모가 지속적으로 줄어듭니다. -문제는 해법을 쉽게 찾을 수 있을 정도로 줄어들어 자연스럽게 재귀 알고리즘으로 이어집니다.

2. 동적 프로그래밍

동적 프로그래밍 방법은 분할 정복 방법과 유사합니다. 기본 아이디어는 원래 문제를 여러 하위 문제로 분해하는 것입니다. 분할 정복 방법과 달리 분해된 하위 문제는 서로 독립적이지 않은 경우가 많습니다. 이 경우 분할 정복 방법을 사용하면 일부 하위 문제가 여러 번 해결되므로 이는 분명히 불필요합니다. 동적 프로그래밍 방법은 풀이 과정에서 해결된 모든 하위 문제에 대한 답을 저장하므로 하위 문제의 반복적인 해결을 방지합니다.

동적 프로그래밍은 종종 최적화 문제를 해결하는 데 사용됩니다. 동적 프로그래밍을 최적화 문제에 적용할 수 있는지 여부는 문제에 다음 두 가지 속성이 있는지 여부에 따라 달라집니다.

최적 하위 구조 속성:

문제의 최적 솔루션에 하위 문제의 최적 솔루션이 포함되어 있는 경우 이를 The 문제는 최적의 하부구조 특성을 가지고 있습니다.

하위 문제의 중첩 특성: 하위 문제의 중첩 특성은 원래 문제에서 분해된 하위 문제가 서로 독립적이지 않고 중첩된다는 의미입니다.

문제가 최적의 하위 구조 속성을 갖는 경우 동적 프로그래밍 방법으로 해결할 수 있습니다. 그러나 때로는 동적 프로그래밍보다 더 간단하고 직접적이며 효율적인 알고리즘인 탐욕적 방법이 있습니다. 탐욕적 방법은 항상 현재 최선의 선택을 하는데, 이는 탐욕적 방법이 내리는 선택은 어떤 의미에서는 국소적 최적 선택일 뿐이라는 것을 의미합니다.

역추적 방법은 문제의 해 공간 트리에 대해 깊이 우선 탐색을 수행하는 것이지만, 각 노드에 대해 DFS를 수행하기 전에 먼저 해당 노드에 해가 포함될 가능성이 있는지 확인해야 합니다. 문제에. 확실히 포함되지 않은 경우 이 노드에 뿌리를 둔 하위 트리 검색을 건너뛰고 계층별로 조상 노드로 역추적합니다. 포함이 가능하다면 하위트리에 진입하여 DFS를 수행한다.

분기 및 경계 방법의 검색 전략은 먼저 현재 노드에서 모든 하위 노드(분기)를 생성하고 이를 만족하는 각 하위 노드에 대한 함수 값(바운드)을 계산하는 것입니다. ), 제약 조건을 충족하는 모든 하위 노드를 솔루션 공간 트리의 라이브 노드 우선 순위 대기열에 추가합니다. 그런 다음 현재 라이브 노드 우선 순위 대기열에서 우선 순위가 가장 높은 노드를 선택합니다(노드의 우선 순위는 제한 함수 값에 따라 결정됨). 이 과정은 리프 노드에 도달할 때까지 반복됩니다. 도달한 리프 노드가 최적의 솔루션입니다. ~

위 내용은 일반적으로 사용되는 알고리즘 설계 전략은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!