6 에서 자주 사용 하 는 알고리즘 디자인: 궁 거 법, 분 치 법, 동태 계획, 욕심 법, 역 추적 법 과 분계선 법

알고리즘 디자인 의 여섯 가지 상용 알고리즘 디자인 방법
1. 직접 옮 겨 다 니 기 (궁 거 법)
       프로그램 실행 상 태 는 옮 겨 다 닐 수 있 습 니 다. 알고리즘 을 옮 겨 다 니 며 모든 상 태 를 실행 하면 가장 좋 은 실행 가능 한 해 를 찾 을 수 있 습 니 다.극소 규모 나 복잡 도 선형 성장 을 해결 하 는 데 적용 되 며 선형 규 모 는 크 지 않 은 상태 다.
2. 분 치 법
      직접적 으로 해결 하기 어 려 운 큰 문 제 를 규모 가 작은 똑 같은 작은 문제 로 나 누 어 각각 격파 하고 나 누 어 해결 하도록 한다.
사상 전략:
     한 규모 가 n 인 문제 에 대해 만약 에 이 문 제 를 쉽게 해결 할 수 있다 면 (예 를 들 어 규모 n 이 비교적 작다) 직접 해결 해 야 한다. 그렇지 않 으 면 이 를 k 개의 규모 가 비교적 작은 서브 문제 로 분해 한다. 이런 서브 문 제 는 서로 독립 되 고 원래 의 문제 형식 과 같 으 며 이런 서브 문 제 를 재 귀적 으로 해결 한 다음 에 각 서브 문제 의 해 제 를 원래 의 문제 로 합 친다.
특징:
1) 이 문제 의 규 모 를 어느 정도 축소 하면 쉽게 해결 할 수 있다  2) 이 문 제 는 몇 개의 규모 가 작은 똑 같은 문제 로 나 눌 수 있다. 즉, 이 문 제 는 가장 좋 은 서브 구조 성 을 가진다.  3) 이 문제 로 분 해 된 하위 문제 의 해 를 이용 하여 이 문제 의 해 로 합 칠 수 있다.  4) 이 문제 에서 분 해 된 각 하위 문 제 는 서로 독립 된 것 이다. 즉, 하위 문제 사이 에 공공 하위 문 제 를 포함 하지 않 는 다.
첫 번 째 특징 은 절대 다수의 문제 가 모두 만족 할 수 있다 는 것 이다. 왜냐하면 문제 의 계산 복잡성 은 일반적으로 문제 규모 의 증가 에 따라 증가 하기 때문이다.  두 번 째 특징 은 분 치 법 을 응용 하 는 전제 이 고 대부분 문제 가 만족 할 수 있다. 이 특징 은 재 귀 사상의 응용 을 나타 낸다.  세 번 째 특징 은 관건 이다. 분 치 법 을 이용 할 수 있 느 냐 없 느 냐 는 문제 가 세 번 째 특징 을 가지 고 있 느 냐 에 달 려 있다. 만약 에 첫 번 째 와 두 번 째 특징 을 가지 고 세 번 째 특징 을 가지 지 않 으 면 욕심 법 이나 동태 계획 법 을 사용 하 는 것 을 고려 할 수 있다.  제4 조 특징 은 분 치 법의 효율 과 관련된다. 만약 에 각 서브 문제 가 독립 적 이지 않 으 면 분 치 법 은 불필요 한 일 을 많이 하고 공공 서브 문 제 를 반복 적 으로 풀 어야 한다. 이때 분 치 법 을 사용 할 수 있 지만 보통 동태 계획 법 을 사용 하 는 것 이 좋다.
기본 단계:
1 분해: 원래 의 문 제 를 몇 개의 규모 가 작고 서로 독립 되 며 원래 의 문제 형식 과 같은 서브 문제 로 분해한다.  2. 해결: 만약 에 서브 문제 의 규모 가 작고 해결 되 기 쉬 우 면 직접 해결 하고 그렇지 않 으 면 각 서브 문 제 를 재 귀적 으로 해결한다.  3. 합병: 각 하위 문제 의 해 를 원래 문제 의 해 로 합 친다.
분 치 법 을 적용 하여 해답 을 구 하 는 고전적 인 문제:

1) 2 점 검색

2) 큰 정수 곱셈

3) 병합 정렬

4) 빠 른 정렬

5) 한 노 타

3. 동적 기획
매번 결정 은 현재 상태 에 의존 하고 곧 상태의 전 이 를 일으킨다.하나의 결정 서열 은 바로 변화 하 는 상태 에서 발생 한 것 이기 때문에 이런 다단 계 에서 결정 을 최적화 하여 문 제 를 해결 하 는 과정 을 동태 계획 이 라 고 한다.
사상 전략:
구 해 야 할 문 제 를 몇 개의 키 문제 (단계) 로 분해 하고 순서대로 서브 단계, 앞의 문제 의 해 를 구하 여 뒤의 문제 의 해결 에 유용 한 정 보 를 제공 했다.어떤 문 제 를 풀 때 여러 가지 가능 한 부분 해 를 열거 하고 결정 을 통 해 가장 좋 은 부분 해 를 달성 할 수 있 는 부분 해 를 보류 하 며 다른 부분 해 를 버린다.각 하위 문 제 를 순서대로 해결 하고, 마지막 하위 문 제 는 초기 문제 의 풀이 이다.
특징:
동적 계획 을 채택 하여 해답 을 구 할 수 있 는 문 제 는 일반적으로 세 가지 성질 을 가 져 야 한다.  (1) 최 적 화 된 원리: 만약 에 문제 의 최 적 화 된 해석 에 포 함 된 서브 문제 의 해석 도 최 적 화 된 것 이 라면 이 문 제 는 최 적 화 된 서브 구 조 를 가지 고 있다 고 한다. 즉, 최 적 화 된 원 리 를 만족 시 키 는 것 이다.  (2) 무 후 효성: 즉, 특정한 단계 의 상태 가 확정 되면 이 상태 이후 의 결정 에 영향 을 받 지 않 는 다.즉, 어떤 상태 이후 의 과정 은 이전의 상태 에 영향 을 주지 않 고 현재 상태 와 만 관련 이 있다 는 것 이다.  (3) 중첩 자 문제 가 있다. 즉, 자 문제 간 에 독립 되 지 않 고 한 자 문 제 는 다음 단계 의 결정 에서 여러 번 사 용 될 수 있다.(이 성질 은 동적 기획 이 적용 되 는 필수 조건 이 아니 지만 이 성질 이 없 으 면 동적 기획 알고리즘 은 다른 알고리즘 에 비해 우세 하지 않다)
기본 단계:
(1) 최 적 화 된 성질 을 분석 하고 그 구조 적 특징 을 묘사한다.  (2) 재 귀적 정의 가 가장 좋다.  (3) 아래 에서 위로 또는 위 에서 아래로 의 기억 화 방식 (비망록 법) 으로 최 적 치 를 계산한다.  (4) 최 우수 치 를 계산 할 때 얻 은 정보 에 따라 구조 문제 의 최 적 화 를 말한다.

                    ，         ，            ，      。             ，                  (           )。    。               ，           ：    →│  １│→│  ２│→…→│  ｎ│→    

동적 계획 을 적용 하여 해답 을 구 하 는 고전적 인 문제:

매트릭스 연승,

최 장 공공 서브 시퀀스 (LCS),

최 장 증가 서브 시퀀스 (LIS),

최대 화 투자 수익 문제 의 실현,

동적 계획 으로 미사일 요격 을 실현 한다.

동적 계획 0 / 1 가방 문제

4. 탐욕 법
문 제 를 풀 때 는 항상 현재 로 서 는 가장 좋 은 선택 을 한다.즉, 전체적인 최 적 화 를 고려 하지 않 고 그 가 한 것 은 특정한 의미 에서 국 지적 으로 만 최 적 화 된 것 이다.
사상 전략:
욕심 알고리즘 은 고정된 알고리즘 프레임 워 크 가 없고 알고리즘 디자인 의 관건 은 욕심 전략의 선택 이다.반드시 주의해 야 할 것 은 욕심 알고리즘 이 모든 문제 에 대해 전체적인 최 적 화 를 얻 을 수 있 는 것 이 아니 라 선택 한 욕심 전략 은 반드시 비효 율 성 을 가 져 야 한 다 는 것 이다. 즉, 특정한 상태 이후 의 과정 은 예전 의 상태 에 영향 을 주지 않 고 현재 상태 와 만 관련 이 있다.그래서 사용 하 는 욕심 전략 에 대해 서 는 그 만족 여 부 를 꼼꼼 히 분석 해 야 한다.
기본 단계:
1. 수학 모형 을 만들어 문 제 를 묘사한다.  2. 해답 을 구 하 는 문 제 를 몇 개의 하위 문제 로 나눈다.  3. 모든 문 제 를 해결 하고 서브 문제 의 부분 적 인 최 적 화 를 얻는다.  4. 하위 문제 의 해 를 부분 적 으로 가장 잘 풀 어 원래 문 제 를 푸 는 해 를 합성 한다.
탐욕 법 을 적용 하여 해답 을 구 하 는 고전적 인 문제:

Huffman 인 코딩,

Dijkstra 알고리즘 (최 단 경로 풀이),

최소 생 성 트 리 알고리즘

5. 역 추적 법
역 추적 알고리즘 은 실제 적 으로 매 거 진 검색 시도 과정 과 유사 하 다. 주로 검색 시도 과정 에서 문제 의 해 를 찾 는 것 이다. 해결 조건 이 만족 하지 않 는 것 을 발견 하면 '역 추적' 으로 돌아 가 다른 경 로 를 시도 한다.  역 추적 법 은 우수한 검색 법 을 선택 하여 우수한 조건 에 따라 앞으로 검색 하여 목 표를 달성 하 는 것 이다.그러나 어떤 단 계 를 탐색 할 때 원래 의 선택 이 좋 지 않 거나 목 표를 달성 하지 못 한 것 을 발견 하면 한 걸음 물 러 서서 다시 선택한다. 이런 통 하지 않 으 면 되 돌아 가 는 기술 은 역 추적 법 이 고 역 추적 조건 을 만족 시 키 는 특정한 상태의 점 을 '역 추적 점' 이 라 고 한다.  많은 복잡 하고 규모 가 큰 문 제 는 모두 역 추적 법 을 사용 할 수 있 으 며 '통용 문제 풀이 방법' 이라는 미칭 이 있다.
사상 전략:
문 제 를 포함 하 는 모든 해 공간 트 리 에서 깊이 우선 검색 전략 에 따라 루트 노드 에서 공간 트 리 를 깊이 탐색 합 니 다.어떤 결점 을 탐색 할 때 먼저 이 결점 에 문제 의 해 가 포함 되 어 있 는 지 판단 하고 포함 되 어 있 으 면 이 결점 에서 출발 하여 계속 탐색 해 야 한다. 만약 에 이 결점 에 문제 의 해 가 포함 되 어 있 지 않 으 면 한 층 한 층 조상 결점 으로 거 슬러 올라간다.(사실 역 추적 법 은 암시 적 그림 의 깊이 에 대한 우선 검색 알고리즘 이다).  역 추적 법 으로 문제 의 모든 해 를 구 할 때 는 뿌리 로 거 슬러 올 라 가 야 하고, 뿌리 가 맺 힌 모든 실행 가능 한 자 수 는 모두 수색 되 어야 끝난다.
특징:
(1) 주어진 문제 에 대해 문제 의 해결 공간 을 확인한다. 먼저 문제 의 해결 공간 을 명 확 히 정의 하고 문제 의 해결 공간 은 적어도 문제 의 하 나 를 포함해 야 한다.  (2) 노드 의 확장 검색 규칙 확인  (3) 깊이 우선 순위 로 공간 을 검색 하고 검색 과정 에서 가지치기 함수 로 잘못된 검색 을 피한다.(제약 함수 로 확장 노드 에서 제약 에 만족 하지 않 는 하위 트 리 를 자 르 고 한계 함수 로 가장 잘 풀 리 지 않 는 하위 트 리 를 자 릅 니 다. 이 두 가지 함 수 는 모두 가지치기 함수 라 고 합 니 다. 가지치기 함 수 를 사용 하면 잘못된 검색 을 피하 고 역 추적 법의 검색 효율 을 높 일 수 있 습 니 다.)
역 추적 법 을 적용 하여 해답 을 구 하 는 고전적 인 문제:

8 황후 문제,

그림 의 착색 문제,

적재 문제,

일괄 처리 작업 스케줄 문제,

기호 삼각형 문제,

6. 분기 한계 법
역 추적 법 과 유사 하 며 문제 풀이 공간 트 리 T 에서 문 제 를 검색 해 푸 는 알고리즘 이기 도 하 다.그러나 일반적인 상황 에서 분계 법 은 역 추적 법의 구 해 목표 와 다르다.역 추적 법의 구 해 목 표 는 T 에서 제약 조건 을 만족 시 키 는 모든 해 를 찾 는 것 이 고 분계 법의 구 해 목 표 는 제약 조건 을 만족 시 키 는 해 를 찾 거나 제약 조건 을 만족 시 키 는 해 에서 특정한 목표 함수 수 치 를 극 대 또는 극소 의 해 를 찾 는 것 이다. 즉, 특정한 의미 에서 가장 좋 은 해 를 찾 는 것 이다.
정책:
확장 노드 에서 선생님 은 모든 아들 노드 (분기) 가 된 다음 현재 활성 점 표 에서 다음 확장 점 을 선택 하 십시오.다음 확장 노드 를 효과적으로 선택 하여 검색 프로 세 스 를 가속 화하 기 위해 모든 활성 점 에서 함수 값 (한계) 을 계산 하고 계 산 된 함수 값 에 따라 현재 활성 점 표 에서 가장 유리 한 결점 을 확장 노드 로 선택 하여 검색 을 해 공간 트 리 에 가장 좋 은 지점 으로 추진 하여 가능 한 한 빨리 최 적 화 를 찾 을 수 있 도록 합 니 다.
소 급 법 과 의 차이:
역 추적 법: [방식 이 다 름] 깊이 우선 스 택 활성 점 을 검색 하 는 모든 실행 가능 한 하위 노드 가 옮 겨 다 닌 후에 야 스 택 에서 제약 조건 을 만족 시 키 는 모든 해 를 찾 을 수 있 습 니 다 [목표 가 다 름].
분기 한계 법: [방식 이 다 름] 범위 우선 또는 최소 소모 우선 검색 대기 열, 우선 대기 열 각 노드 는 한 번 만 활성 화 된 기회 로 제약 조건 을 만족 시 키 는 해 나 특정한 의미 에서 의 최 적 화 를 찾 을 수 있 습 니 다 [목표 가 다 름].