5 대 상용 알고리즘 중 하나 인 분할 알고리즘
4809 단어 알고리즘 클래스
기본 개념
컴퓨터 과학 에서 분 치 법 은 매우 중요 한 알고리즘 이다.글자 의 해석 은'나 누 어 다스 리 는 것'이다.바로 복잡 한 문 제 를 두 개 이상 의 똑 같 거나 비슷 한 서브 문제 로 나 누고 서브 문 제 를 더 작은 서브 문제 로 나 누 는 것 이다.이 기 교 는 많은 효율 적 인 알고리즘 의 기초 이다.예 를 들 어 정렬 알고리즘(빠 른 정렬,병합 정렬),부 립 엽 변환(빠 른 부 립 엽 변환).컴퓨터 로 풀 수 있 는 모든 문제 에 필요 한 계산 시간 은 그 규모 와 관계 가 있다.문제 의 규모 가 작 을 수록 직접 풀 기 쉽 고 문제 풀이 에 필요 한 계산 시간 도 적다.예 를 들 어 n 개 요소 의 정렬 문제 에 대해 n=1 일 때 계산 이 필요 하지 않 습 니 다.n=2 시,한 번 만 비교 하면 순 서 를 정할 수 있다.n=3 시 3 번 만 비교 하면 됩 니 다.n 이 비교적 클 때 문 제 는 쉽게 처리 되 지 않 는 다.규모 가 큰 문 제 를 직접 해결 하려 면,때로는 상당히 어렵다.
2.기본 사상 과 전략
분 치 법의 디자인 사상 은 직접적 으로 해결 하기 어 려 운 큰 문 제 를 규모 가 작은 똑 같은 문제 로 나 누 어 각각 격파 하고 나 누 어 다스 리 도록 하 는 것 이다.
분 치 전략 은 한 규모 가 n 인 문제 에 대해 이 문 제 를 쉽게 해결 할 수 있다 면(예 를 들 어 규모 n 이 비교적 작다)직접 해결 하 는 것 이다.그렇지 않 으 면 이 를 k 개의 규모 가 작은 서브 문제 로 분해 하 는 것 이다.이런 서브 문 제 는 서로 독립 되 고 원래 의 문제 형식 과 같 으 며 이 몇 가지 문 제 를 재 귀적 으로 해결 한 다음 에 각 서브 문제 의 해 제 를 합병 하여 원래 의 문 제 를 해결 하 는 것 이다.이런 알고리즘 설계 전략 을 분 치 법 이 라 고 한다.
만약 에 원래 의 문 제 를 k 키 문제 로 나 눌 수 있 고 이런 문 제 를 모두 풀 수 있 으 며 이런 문 제 를 이용 하여 원래 의 문 제 를 풀 수 있다 면 이런 분 치 법 은 실행 가능 하 다.분 치 법 에서 발생 하 는 서브 문 제 는 흔히 원래 문제 의 작은 모델 로 재 귀 기술 을 사용 하 는 데 편 의 를 제공한다.이런 상황 에서 분 치 수단 을 반복 적 으로 응용 하면 서브 문 제 를 원래 의 문제 유형 과 일치 시 킬 수 있 지만 그 규 모 는 계속 줄 어 들 고 결국은 서브 문 제 를 직접적 으로 해결 하기 쉬 울 정도 로 축소 시 킬 수 있다.이것 은 자연히 귀속 과정의 발생 을 야기한다.분 치 와 재 귀 는 쌍둥이 형제 처럼 알고리즘 디자인 에 자주 응용 되 고 이 로 인해 많은 효율 적 인 알고리즘 이 생 긴 다.
3.분 치 법 이 적용 되 는 상황
분 치 법 이 해결 할 수 있 는 문 제 는 일반적으로 다음 과 같은 몇 가지 특징 을 가진다.
1)이 문제 의 규 모 를 어느 정도 축소 하면 쉽게 해결 할 수 있다
2)이 문 제 는 몇 개의 규모 가 작은 똑 같은 문제 로 나 눌 수 있다.즉,이 문 제 는 가장 좋 은 서브 구조 성 을 가진다.
3)이 문제 로 분 해 된 하위 문제 의 해 를 이용 하여 이 문제 의 해 로 합 칠 수 있다.
4)이 문제 에서 분 해 된 각 하위 문 제 는 서로 독립 된 것 이다.즉,하위 문제 사이 에 공공 하위 문 제 를 포함 하지 않 는 다.
첫 번 째 특징 은 절대 다수의 문제 가 모두 만족 할 수 있다 는 것 이다.왜냐하면 문제 의 계산 복잡성 은 일반적으로 문제 규모 의 증가 에 따라 증가 하기 때문이다.
두 번 째 특징 은 분 치 법 을 응용 하 는 전제 이자 대부분 문제 가 만족 할 수 있다 는 것 이다.이 특징 은 재 귀 사상의 응용 을 나타 낸다.
세 번 째 특징 은 관건 이다.분 치 법 을 이용 할 수 있 느 냐 없 느 냐 는 문제 가 세 번 째 특징 을 가지 고 있 느 냐 에 달 려 있다.만약 에 첫 번 째 와 두 번 째 특징 을 가지 고 세 번 째 특징 을 가지 지 않 으 면 욕심 법 이나 동태 계획 법 을 사용 하 는 것 을 고려 할 수 있다.
제4 조 특징 은 분 치 법의 효율 과 관련된다.만약 에 각 서브 문제 가 독립 되 지 않 으 면 분 치 법 은 불필요 한 일 을 많이 하고 공공 서브 문 제 를 반복 적 으로 풀 어야 한다.이때 분 치 법 을 사용 할 수 있 지만 보통 동태 계획 법 을 사용 하 는 것 이 좋다.
4.분 치 법의 기본 절차
분 치 법 은 각 층 의 순환 에 있어 세 가지 절차 가 있다.
step 1 분해:원래 의 문 제 를 몇 개의 규모 가 작고 서로 독립 되 며 원래 의 문제 형식 과 같은 서브 문제 로 분해 합 니 다.step 2 해결:하위 문제 의 규모 가 작고 해결 되 기 쉬 우 면 직접 해결 합 니 다.그렇지 않 으 면 각 하위 문 제 를 재 귀적 으로 해결 합 니 다 step 3 합병:각 하위 문제 의 해 제 를 원래 문제 의 해 로 합 칩 니 다.
그것 의 일반적인 알고리즘 디자인 모델 은 다음 과 같다.
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. P P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ Pi
6. T ← MERGE(y1,y2,...,yk) △
7. return(T)4.567917.n0 은 한도 값 으로 문제 P 의 규모 가 n0 을 초과 하지 않 을 때 문 제 는 직접 풀 리 기 쉬 우 므 로 더 이상 분해 할 필요 가 없다 는 것 을 나타 낸다
4
5.분 치 법의 복잡성 분석
4.567917.하나의 분 치 법 은 n 규모 의 문 제 를 k 개 규모 가 n/m 인 서브 문제 로 나 누 어 푼다
4.567917.분해 밸브 값 n0=1 을 설치 하고 adhoc 분해 규모 가 1 인 문 제 는 1 개 단위 의 시간 을 소모 합 니 다
4.567917.원래 문 제 를 k 키 문제 로 분해 하고 merge 로 k 키 문 제 를 원래 문제 로 해결 하 는 데 필요 한 f(n)단위 시간 을 설정 합 니 다.T(n)로 이 분 치 법 해 규 모 를|P|=n 으로 표시 하 는 데 필요 한 계산 시간 은 다음 과 같다
T（n）= k T(n/m)+f(n)교체 법 을 통 해 방정식 의 해 를 구하 다.
재 귀 방정식 과 그 해 는 n 이 m 와 같은 방 멱 시 T(n)의 값 만 제시 하지만 T(n)가 충분히 매끈매끈 하 다 고 생각한다 면 n 이 m 와 같은 방 멱 시 T(n)의 값 으로 T(n)의 성장 속 도 를 평가 할 수 있다.보통 T(n)가 단조 로 운 상승 이 라 고 가정 하여
mi≤n，T(mi)≤T(n)。 6.분 치 법 으로 해결 할 수 있 는 전형 적 인 문제 들
(1)2 분 검색(2)대 정수 곱셈(3)Strassen 매트릭스 곱셈(4)바둑판 덮어 쓰기(5)병합 정렬(6)빠 른 정렬(7)선형 시간 선택(8)가장 가 까 운 점 대 문제(9)순환 일정표(10)한 노 타
7.분 치 법 에 따라 절 차 를 설계 할 때의 사고 과정
실제로 수학 귀납법 과 유사 하 게 본 문 제 를 해결 하 는 방정식 공식 을 찾 아 방정식 공식 에 따라 재 귀 절 차 를 설계 하 는 것 이다.1.반드시 최소 문제 규 모 를 찾 을 때 해결 방법 2.그 다음 에 문제 의 규모 가 커지 면서 해결 방법 3.해결 의 재 귀 함수 식 을 찾 은 후에(각종 규모 나 인자)재 귀 절 차 를 설계 하면 된다.
좋은 웹페이지 즐겨찾기
