n개의 입력이 있고 해당 솔루션은 n개의 입력의 하위 집합으로 구성됩니다. 이러한 하위 집합은 제약 조건을 충족해야 합니다. 제약 조건을 충족하는 실현 가능한 솔루션이 두 개 이상 있을 수 있습니다. 이러한 실현 가능한 솔루션의 품질을 측정하기 위해 특정 표준이 일반적으로 함수 형식으로 제공됩니다. 목적 함수가 극한값을 달성하게 만드는 문제(최대값 또는 최소값)를 최적해라고 하며 이러한 유형의 문제를 최적화 문제라고 합니다.

n개의 입력이 있는 최적화 문제의 경우 솔루션 프로세스는 종종 여러 단계로 나눌 수 있습니다. 각 단계의 의사 결정은 이전 단계의 상태에만 의존합니다. 다음 단계 결정의 기초. 따라서 끊임없이 변화하는 상태에서 일련의 결정이 생성됩니다. 이러한 의사결정 순서에 따른 프로세스를 다단계 의사결정 프로세스라고 합니다.

동적 프로그래밍 방법으로 해결하기에 적합한 문제의 경우 분해 후 얻은 하위 문제는 서로 독립적이지 않은 경우가 많습니다. 분열과 정복과는 다릅니다.

해결 프로세스 중에 해결된 하위 문제에 대한 솔루션이 저장되며 필요할 때 쉽게 검색할 수 있습니다. 이렇게 하면 의미 없는 반복 계산이 많이 발생하지 않으므로 알고리즘의 시간 복잡도가 줄어듭니다.

해결된 하위 문제의 솔루션을 저장하는 방법은 무엇입니까? 일반적으로 테이블 형식, 즉 실제 해결 과정에서는 특정 하위 문제가 계산되면 향후 해당 문제의 사용 여부에 관계없이 계산 결과가 테이블에 채워지고 하위 문제는 필요할 때 표에서 찾을 수 있습니다. 문제에 대한 해결책, 특정 동적 프로그래밍 알고리즘은 다양하지만 양식 채우기 형식은 동일합니다.

최적해의 속성을 분석하고 최적해의 구조적 특성을 특성화 - 동적 프로그래밍 방법을 사용하는 것이 적합한지 검토

최적의 값을 재귀적으로 정의합니다(즉, 재귀적 또는 동적 프로그래밍 방정식 설정).

상향식으로 최적의 값을 계산하고 관련 정보를 기록합니다.

최적값을 계산하여 얻은 정보를 바탕으로 최적해를 구축합니다.

최적의 하부구조 특성

특징: A[i:j]를 계산하는 최적의 순서에 포함된 계산 행렬 하위 체인 A[i:k] 및 A[k 1:j]의 순서도 최적입니다.

행렬 곱셈 계산 순서 문제에 대한 최적해에는 해당 하위 문제에 대한 최적해가 포함됩니다. 이 특성을 최적의 하부구조 특성이라고 합니다. 문제의 최적 하위 구조 속성은 동적 프로그래밍 알고리즘으로 해결할 수 있는 문제의 중요한 특징입니다.

분할정복 방식의 설계 아이디어는 직접적으로 해결하기 어려운 큰 문제를 여러 개의 작은 동일한 문제로 나누어 개별적으로 극복하고 분할정복할 수 있도록 하는 것입니다.

직접 해결하기 어려운 큰 문제를 더 작은 하위 문제로 나누어 개별적으로 해결할 수 있도록 분할하고 정복하세요.

그런 다음 하위 문제의 솔루션을 더 큰 문제의 솔루션으로 병합하고 점차적으로 아래에서 위로 원래 문제에 대한 솔루션을 찾습니다.

분할정복법으로 해결할 수 있는 문제는 일반적으로 다음과 같은 특징을 갖는다.

문제의 규모가 어느 정도 줄어들면 문제는 쉽게 해결될 수 있습니다. 문제는 동일한 크기의 여러 개의 작은 문제로 분해될 수 있습니다. 즉, 문제는 최적의 하위 구조 특성을 갖습니다.

이 문제를 사용하여 분해된 하위 문제에 대한 솔루션은 이 문제의 솔루션에 병합될 수 있습니다.

이 문제로 분해된 하위 문제는 서로 독립적입니다. 즉, 하위 문제 사이에 공통 하위 문제가 없습니다.

이 특징은 분할 정복 방법의 효율성과 관련이 있습니다. 분할 정복 방법은 분할 정복 방법이더라도 불필요한 작업을 많이 수행하고 공통 하위 문제를 반복적으로 해결해야 합니다. -and-conquer 방법도 이때 사용할 수 있습니다. 일반적으로 동적 프로그래밍이 더 좋습니다.

나누다

하위 문제 해결

병합

어떻게 분할할 것인가, 즉 문제를 합리적으로 분해할 것인가?

치료 방법, 즉 문제를 해결하는 방법

문제의 핵심 - 라운드 로빈 일정을 만드는 과정에서 규칙성을 발견하는 것

퀵소트의 분할 정복 전략은 다음과 같습니다.

퀵 정렬 알고리즘의 분할 정복 전략

탐욕스러운 방법은 문제 해결 전략에 있어 근시안적이며 항상 현재 순간 최선의 선택을 합니다. 그리고 일단 선택을 하면, 미래에 어떤 결과가 나오더라도 이 선택은 변하지 않을 것입니다. 즉, 그리디 방법은 전체 최적을 고려하지 않지만, 그것이 내리는 선택은 어떤 의미에서 국소 최적일 뿐입니다.

문제의 최적해가 하위 문제의 최적해를 포함하는 경우 해당 문제는 최적의 하위 구조 특성을 갖는다고 하며 문제가 최적성의 원칙을 충족한다고도 합니다.

소위 탐욕적 선택(Greedy Selection) 특성은 일련의 지역적 최적 선택, 즉 탐욕적 선택(현재 상태에서 최선의 선택만 함)을 통해 문제에 대한 전체 최적해를 얻을 수 있음을 의미합니다.

후보 집합 C: 문제에 대한 해결책을 구성하기 위해 문제에 대한 가능한 해결책으로 후보 집합 C가 있습니다. 즉, 문제에 대한 최종 해결책은 후보 집합 C에서 가져옵니다. 예를 들어 지불 문제에서는 다양한 단위의 통화가 후보 집합을 형성합니다.

솔루션 집합 S: 욕심 많은 선택이 진행됨에 따라 솔루션 집합 S는 문제를 만족하는 완전한 솔루션을 형성할 때까지 계속 확장됩니다. 예를 들어, 지불 문제에서는 지불된 돈이 해결 세트를 구성합니다.

솔루션 기능: 솔루션 세트 S가 문제에 대한 완전한 솔루션을 구성하는지 확인합니다. 예를 들어, 지불 문제에서 해결 기능은 지불한 금액이 지불할 금액과 정확히 동일하다는 것입니다.

선택 함수 선택(Selection function select), 즉 그리디 전략(greedy strategy)은 어떤 후보 객체가 문제에 대한 해결책을 형성하는 데 가장 유망한지를 지적하는 것입니다. 선택 함수는 일반적으로 목적 함수와 관련이 있습니다. 예를 들어 지불 문제에서 그리디 전략은 후보 집합에서 액면가가 가장 높은 통화를 선택하는 것입니다.

실현 가능 기능: 솔루션 세트에 후보 객체를 추가하는 것이 가능한지, 즉 솔루션 세트가 확장된 후 제약 조건을 만족하는지 확인합니다. 예를 들어 결제 문제에서 실행 가능한 함수는 선택한 통화와 각 단계에서 지불하는 통화의 합이 결제 금액을 초과하지 않는 것입니다.

탐욕스러운 선택 속성

최적의 하부구조 특성

가중치가 큰 잎이 뿌리에 가장 가깝습니다. (빈도가 높은 문자는 짧은 코드를 가집니다.)

그래프 G의 간선 수가 적으면 크루스칼을 사용할 수 있다는 것을 알고리즘의 아이디어에서 알 수 있습니다. 왜냐하면 크루스칼 알고리즘은 간선의 수가 크면 매번 가장 짧은 간선을 찾기 때문입니다. , 매번 정점을 하나씩 추가하므로 Prim 알고리즘을 사용할 수 있습니다. Kruskal은 희소 그래프에 적합한 반면 Prim은 조밀한 그래프에 적합한 것을 알 수 있습니다.

시간적으로 보면 Prim 알고리즘의 시간 복잡도는 O(n2)이고, Kruskal 알고리즘의 시간 복잡도는 O(eloge)입니다.

공간 측면에서 볼 때 Prim의 알고리즘에서는 각 스캔이 개별 지점에서 시작되고 각 스캔이 현재 정점 세트에 해당하는 가장자리만 스캔하기 때문에 알고리즘을 완료하는 데 작은 공간만 필요하다는 것이 분명합니다. 하지만 크루스칼 알고리즘에서는 현재 간선 집합에서 가장 작은 가중치를 갖는 간선이 어디에 있는지 항상 알아야 하기 때문에 매우 큰 그래프의 경우 크루스칼 알고리즘이 훨씬 더 많은 공간을 차지합니다. Prim 알고리즘보다

특정 문제를 해결하기 위한 단계에 대한 설명을 말하며, 이는 여러 지침의 유한한 순서입니다.

특성

자연어

제도법

프로그래밍 언어

이점

결점

의사코드

해결해야 할 문제를 완전히 이해

수학적 모델링

알고리즘 상세 설계

알고리즘 설명

알고리즘 아이디어의 정확성 검증

알고리즘 분석

컴퓨터 구현 및 알고리즘 테스트

서류 준비

알고리즘에 필요한 두 가지 컴퓨터 리소스(시간과 공간)를 추정합니다.

목적

알고리즘 복잡성 = 알고리즘을 실행하는 데 필요한 컴퓨터 리소스의 양

1. 알고리즘 문제 크기의 척도로 사용할 매개변수를 결정합니다.

2. 알고리즘에서 기본문을 찾아보세요

3. 기본문 실행 횟수가 문제 크기에만 의존하는지 확인

4. 기본문의 실행횟수 합산식을 수립한다.

5. 이 합산식을 점근적 표기법으로 표현합니다.

서브루틴(또는 함수)은 재귀라고 하는 일련의 호출 문을 통해 직접적으로 또는 간접적으로 자신을 호출합니다.

자신을 직접 또는 간접적으로 호출하는 알고리즘을 재귀 알고리즘이라고 합니다.

재귀 알고리즘을 사용하여 문제를 해결하는 일반적인 단계: