다섯 가지 고전적인 컴퓨터 알고리즘은 무엇입니까?

5가지 고전적인 컴퓨터 알고리즘: 1. 복잡한 문제를 두 개 이상의 동일하거나 유사한 하위 문제로 나누는 분할 정복 방법 2. 동적 프로그래밍 방법 3. 탐욕 알고리즘, 최적 검색 방법은 목표를 달성하기 위해 최적의 조건에 따라 탐색합니다. 5. 분기 및 경계 방법.

이 튜토리얼의 운영 환경: Windows 10 시스템, Dell G3 컴퓨터.

이력서를 제출하고 인턴십을 구하려고 하는데 아직 어떻게 해야할지 모르겠어서 너무 당황스럽습니다. 오늘부터 매일 2개 이상의 리트코드를 브러싱하고 요약해보겠습니다. , 그리고 다양한 면접 질문에 대한 지식 포인트를 앞으로 자주 검토하겠습니다.

leetcode를 브러싱할 때 사람들이 DP에 대해 이야기하는 것을 자주 봤습니다. 그러다가 DP가 무엇인지 알아보기 위해 Baidu에 갔더니 DP가 5가지 고전 알고리즘 중 하나라는 것을 깨달았습니다. 오늘은 5가지 고전 알고리즘을 요약하겠습니다. .

5가지 클래식 알고리즘은

1. 분할 및 정복 방법: 복잡한 문제를 두 개 이상의 동일하거나 유사한 하위 문제로 나눈 다음 하위 문제를 더 작은 하위 문제로 나눕니다. .. 끝까지 하위 문제는 간단하고 직접적으로 해결될 수 있으며, 원래 문제의 해결은 하위 문제에 대한 솔루션을 병합하는 것입니다.

2. 동적 프로그래밍 방법: 각 결정은 현재 상태에 따라 달라지며 즉시 상태 전환이 발생합니다. 변화하는 상태에서 결정 시퀀스가 ​​생성되므로 문제를 해결하기 위한 이러한 다단계 최적화 의사 결정 프로세스를 동적 프로그래밍이라고 합니다.

3. 탐욕 알고리즘: 문제를 해결할 때는 항상 현재 최선의 선택을 하세요. 즉, 그가 만든 것은 전체 최적해를 고려하지 않은 채 어떤 의미에서는 국소적 최적해에 불과했다. 일반적인 그리디 알고리즘에는 Prim 알고리즘과 Kruskal 알고리즘(둘 다 최소 스패닝 트리 추구)이 포함됩니다.

기본 아이디어: 문제를 여러 개의 작은 문제로 분해하고, 점차적으로 각 하위 문제의 국소 최적해를 얻은 다음, 최종적으로 이를 원래 문제의 해법으로 병합합니다.

4. 역추적 방법: 역추적 알고리즘은 실제로 열거형 검색 시도 프로세스입니다. 주로 검색 시도 중에 해결 조건이 더 이상 충족되지 않는 것으로 확인되면 " 역추적"을 선택하고 돌아가서 다른 것을 시도해 보세요. 심층 우선순위; 회고적 방법은 선택 조건에 따라 목표를 달성하기 위해 앞으로 검색하는 선택 검색 방법입니다. 그러나 탐색의 특정 단계에 도달하여 원래 선택이 최적이 아니거나 목표를 달성할 수 없다는 것을 알게 되면 한 걸음 물러서서 다른 선택을 하게 됩니다. 이것이 작동하지 않을 때 다시 시도하는 것입니다. 역추적 방법이며, 역추적 조건을 만족하는 특정 상태의 지점을 "역추적 지점"이라고 합니다.

5. 분기 및 경계 방법: 역추적 방법과 유사하게 문제의 해 공간 트리 T에서 문제의 해를 찾는 알고리즘이기도 합니다. 그러나 일반적으로 분기 및 경계 방식과 역추적 방식의 해결 목표는 서로 다릅니다. 역추적 방법의 풀이 목표는 T에서 제약 조건을 만족하는 모든 해를 찾는 것인 반면, 분기 및 경계 방법의 풀이 목표는 제약 조건을 만족하는 해를 찾거나 제약 조건을 만족하는 해를 찾는 것입니다. 특정 목적 함수 값이 최대 또는 최소 솔루션에 도달하도록 조건을 지정합니다. 이는 어떤 의미에서 최적 솔루션입니다.

1. 분할정복 방법 분할정복 방법으로 해결할 수 있는 문제는 일반적으로 다음과 같은 특징을 가지고 있습니다.

1) 문제의 규모를 줄이면 쉽게 문제를 해결할 수 있습니다. 2) 문제는 여러 개의 작은 규모의 동일한 문제로 분해될 수 있습니다. 즉, 문제는 최적의 하위 구조 속성을 갖습니다.

3) 이 문제로 분해된 하위 문제의 해는 이 문제의 해로 결합될 수 있습니다.

4) 이 문제에서 분해된 하위 문제는 서로 독립적입니다. 일반적인 하위 질문을 포함하지 않습니다.

세 번째 특성이 없으면 DP(동적 프로그래밍) 또는 그리디 방법을 사용하는 것을 고려해 볼 수 있습니다.

네 번째 특성이 없으면 동적 프로그래밍 사용을 고려해 볼 수 있습니다.

분할 정복 방법의 기본 단계:

1단계 분해: 원래 문제를 원래 문제와 동일한 형태의 더 작고 독립적인 하위 문제로 분해합니다.

2단계 해결책: 하위 문제가 작고 해결하기 쉬우면 직접 해결하고, 그렇지 않으면 각 하위 문제를 재귀적으로 해결하세요

3단계 병합: 각 하위 문제의 솔루션을 원래 문제의 솔루션으로 결합합니다.

2. 동적 프로그래밍 방법

과 분할 정복 방법의 가장 큰 차이점은 동적 프로그래밍 방법으로 해결하기에 적합한 문제의 경우 분해 후 얻은 하위 문제가 종종 그렇지 않다는 것입니다. 서로 독립적입니다(즉, 다음 하위 문제 각 단계의 솔루션은 추가 솔루션을 위해 이전 하위 단계의 솔루션을 기반으로 합니다).

적용 조건:

동적 프로그래밍으로 해결할 수 있는 문제는 일반적으로 세 가지 속성을 갖습니다.

(1) 최적화 원칙: 문제의 최적 솔루션에 포함된 하위 문제에 대한 솔루션도 최적인 경우 문제는 최적의 하위 구조를 가지고 있다고 말합니다. 즉, 최적화 원칙을 만족합니다.

(2) 후유증 없음: 즉, 특정 단계의 상태가 일단 결정되면 이 상태의 후속 결정에 영향을 받지 않습니다. 즉, 특정 상태 이후의 프로세스는 이전 상태에 영향을 주지 않고 현재 상태에만 관련됩니다.

(3) 중복되는 하위 문제가 있습니다. 즉, 하위 문제는 독립적이지 않으며 하위 문제는 의사 결정의 다음 단계에서 여러 번 사용될 수 있습니다. (이 속성은 동적 프로그래밍을 적용하기 위한 필수 조건은 아니지만, 이 속성이 없으면 동적 계획법 알고리즘은 다른 알고리즘에 비해 장점이 없습니다.)

케이스:

n개의 단계가 있고 한 사람이 한 단계 올라갑니다. 매번 수평 또는 두 걸음, n 걸음까지 올라갈 수 있는 방법이 몇 개인지 물어보세요.
분석: 동적 프로그래밍 구현의 핵심은 동적 프로그래밍 테이블을 정확하고 합리적으로 사용하여 실제 문제를 추상화할 수 있는지 여부에 있습니다. 이 문제에서 f(n)은 n 단계 위로 올라가는 방법의 수를 나타냅니다.

그러면 n이 1일 때 f(n) = 1, n이 2일 때 f(n) =2, 즉 단계가 하나만 있을 때 메서드 수는 1개이며, 2단계. 이때 메소드 수는 2개입니다. 그래서 n단계 올라가려면 n-1단계에서 한 단계, n-2단계에서 두 단계를 거쳐야 하므로 n단계에 도달하는 방법의 수는 n-1단계에 도달하는 방법과 숫자 더하기가 되어야 합니다. n-2단계에 도달하는 방법의 수를 합한 것입니다. 즉, f(n) = f(n-1)+f(n-2), dp[n]을 사용하여 동적 프로그래밍 테이블 dp[i],i>0,i<=n을 나타냅니다. 레벨 i 도달 단계 수.

int fun(int n){  
    if (n==1||n==2)  
        return n;  
    /*判断n-1的状态有没有被计算过*/  
    if (!dp[n-1])  
        dp[n-1] = fun(n-1);  
    if(!dp[n-2])  
        dp[n-2]=fun(n-2);  
    return dp[n-1]+dp[n-2];  
}

3. 탐욕 알고리즘

탐욕 알고리즘은 문제를 해결할 때 항상 현재 최선의 선택을 한다는 의미입니다. 즉, 전체적인 최적해를 고려하지 않고 어떤 의미에서는 국소적 최적해만을 만든다는 것이다. 탐욕 알고리즘은 모든 문제에 대해 전체적인 최적의 솔루션을 얻지 못합니다. 핵심은 탐욕 전략을 선택하는 것입니다. 선택한 탐욕 전략은 후유증이 없어야 합니다. 즉, 특정 상태의 이전 프로세스가 후속 상태에 영향을 미치지 않아야 합니다. 그러나 현재 상태에만 영향을 미칩니다.
문제 해결을 위한 일반적인 단계는 다음과 같습니다.
1. 문제를 설명하는 수학적 모델을 설정합니다.
2. 해결해야 할 문제를 여러 하위 문제로 나누고 로컬 최적의 솔루션을 얻습니다.

4. 하위 문제의 로컬 최적 솔루션을 원래 문제의 솔루션으로 결합합니다.

예: 환전 문제

이 문제는 일상생활에서 더 흔합니다. 각각 1위안, 2위안, 5위안, 10위안, 20위안, 50위안, 100위안의 c0, c1, c2, c3, c4, c5, c6 지폐가 있다고 가정합니다. 이제 이 돈으로 K 위안을 지불하려면 최소한 몇 장의 지폐를 사용해야 합니까? 그리디 알고리즘이라는 아이디어를 활용하면 각 단계에서 액면가가 큰 지폐만 최대한 사용할 수 있다는 것은 자명합니다. 우리는 일상생활에서 자연스럽게 이것을 합니다. 값은 프로그램에서 오름차순으로 정렬되었습니다.

public class charge {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
    	int res = charge(84);
    	System.out.println(res);
    }
 
   private static int charge(int money) {
	   int count = 0;
       int value[] = {50,20,10,5,2,1};
       while(money>0){
       	int length = value.length;
       	for(int i=0;i=value[i]){
       			money=money-value[i];
       			count++;
       			//System.out.println(money);
       		}
       	}
       }
       return count;
	}     
}

4. 역추적 방법 
 역추적 방법은 문제에 대한 해결책을 체계적으로 찾는 방법입니다. 검색 과정에서 문제에 대한 해결책을 찾으려고 노력하십시오. 찾을 수 없다면 한 걸음 물러서서 다시 시작하십시오(가지치기 과정). 역추적은 복잡하고 대규모의 여러 문제에 사용될 수 있습니다. 
 역추적 방법의 기본 아이디어는 깊이 우선 검색 전략을 따르고 루트 노드에서 검색을 시작하는 것입니다. 특정 노드에 도달하면 해당 노드에 문제에 대한 해결책이 포함되어 있는지 확인해야 합니다. 포함되어 있으면 해당 노드에서 검색을 계속합니다. 포함되지 않은 경우 상위 노드로 역추적을 검색합니다. 문제에 대한 모든 해결책을 찾기 위해 역추적 방법을 사용하는 경우 루트까지 다시 추적해야 하며 종료하기 전에 루트 노드의 가능한 모든 하위 트리를 검색해야 합니다. 그리고 어떤 해결책을 찾기 위해 역추적 방법을 사용한다면, 문제에 대한 해결책을 찾는 한 종료할 수 있습니다. 

      역추적 방법에서 흔히 사용되는 가지치기 함수: (1) 제약 함수: 노드에서 제약을 만족하지 않는 하위 트리를 뺍니다. (2) 경계 함수: 최적해를 얻을 수 없는 하위 트리를 뺍니다. 
일반 단계:
1. 주어진 문제에 대해 문제의 해 공간을 결정합니다.
2. 검색에 적합한 방법을 사용하여 해 공간을 구성합니다.
3. 깊이를 먼저 사용하여 해 공간을 검색합니다. 검색 프로세스 중에 사용합니다. 정리 기능은 잘못된 검색을 방지합니다. 


 5. 분기 및 경계 방법 
은 역추적 방법과 유사하며 문제의 해 공간 트리 T에서 문제의 해를 찾는 알고리즘이기도 합니다. 그러나 일반적으로 분기 및 경계 방식과 역추적 방식의 해결 목표는 서로 다릅니다. 역추적 방법의 풀이 목표는 T에서 제약 조건을 만족하는 모든 해를 찾는 것인 반면, 분기 및 경계 방법의 풀이 목표는 제약 조건을 만족하는 해를 찾거나 제약 조건을 만족하는 해를 찾는 것입니다. 특정 목적 함수 값이 최대 또는 최소 솔루션에 도달하도록 조건을 지정합니다. 이는 어떤 의미에서 최적 솔루션입니다. (1) 분기 검색 알고리즘
 소위 "분기"는 너비 우선 전략을 사용하여 E-노드의 모든 분기를 순서대로 검색하는 것입니다. 즉, 모든 인접 노드를 검색하고 그렇지 않은 노드는 버립니다. 제약 조건을 충족하고 나머지 노드가 슬립낫 테이블에 참여하려면 클릭하세요. 그런 다음 테이블에서 다음 E-노드로 노드를 선택하고 검색을 계속합니다. 
 다음 E-node를 선택하는 방법에 따라 여러 가지 분기 검색 방법이 있습니다. 
 1) FIFO 검색 
 2) LIFO 검색 
 3) 우선순위 대기열 검색 
 (2) 분기 및 경계 검색 알고리즘 
 분기 및 경계 방법의 일반적인 프로세스 

 솔루션 목표가 다르기 때문에 솔루션 공간 트리 T에서 분기 및 경계 방법과 역추적 방법은 서로 다른 검색 방법을 갖습니다. 역추적 방법은 깊이 우선 방식으로 솔루션 공간 트리 T를 검색하는 반면, 분기 및 경계 방법은 너비 우선 또는 최소 비용 우선 방식으로 솔루션 공간 트리 T를 검색합니다. 
 분기 및 경계 방법의 검색 전략은 다음과 같습니다. 확장 노드에서 먼저 모든 하위 노드(분기)를 생성한 후 현재 라이브 노드 테이블에서 다음 확장 쌍 포인트를 선택합니다. 다음 확장 노드를 효과적으로 선택하고 검색 속도를 높이기 위해 각 라이브 노드에서 함수 값(바운드)을 계산하고, 계산된 함수 값을 기반으로 현재 라이브 노드 테이블에서 가장 좋은 값을 선택합니다. 유리한 노드는 가능한 한 빨리 최적의 솔루션을 찾기 위해 솔루션 공간 트리에서 최적의 솔루션이 있는 분기를 향해 검색을 진행하는 확장 노드 역할을 합니다. 
 분기 및 경계 방법은 너비 우선 또는 최소 비용(최대 이익) 우선 방식으로 문제의 해 공간 트리를 검색하는 경우가 많습니다. 문제의 솔루션 공간 트리는 문제의 솔루션 공간을 나타내는 순서 트리입니다. 일반적인 트리에는 부분 집합 트리와 순열 트리가 포함됩니다. 문제의 해 공간 트리를 검색할 때 분기 경계 방법과 역추적 방법은 현재 확장 노드에 대해 서로 다른 확장 방법을 사용합니다. 분기 결합 방식에서는 각 라이브 노드가 확장 노드가 될 수 있는 기회가 단 한 번 있습니다. 라이브 노드가 확장 노드가 되면 모든 하위 노드가 한 번에 생성됩니다. 이러한 하위 노드 중에서 실현 불가능한 솔루션이나 최적이 아닌 솔루션으로 이어지는 노드는 삭제되고 나머지 하위 노드는 라이브 노드 목록에 추가됩니다. 이후, 라이브 노드 테이블에서 노드를 가져와서 현재 확장 노드가 되며, 위의 노드 확장 과정을 반복한다. 이 프로세스는 원하는 솔루션을 찾거나 liveknot 테이블이 비어 있을 때까지 계속됩니다. 
역추적 방법과 분기 및 경계 방법의 차이점

 어떤 문제는 실제로 역추적 방법이나 분기 및 경계 방법을 사용하여 잘 해결될 수 있지만 다른 문제는 그렇지 않습니다. 어쩌면 분기 및 경계를 사용할 때와 역추적을 사용할 때와 같은 보다 구체적인 분석이 필요할 수도 있습니다. 
역추적 방법과 분기 및 경계 방법 간의 몇 가지 차이점: 
 솔루션 공간 트리에 대한 방법의 검색 방법 노드 저장을 위한 공통 데이터 구조 노드 저장 기능의 일반적인 응용 
 역추적 방법 깊이 우선은 가능한 모든 하위를 검색합니다. -스택 라이브 노드의 노드 포인트를 순회한 후 제약 조건을 만족하는 모든 솔루션을 찾기 위해 스택에서 팝됩니다
 분기 및 경계 방법 너비 우선 또는 최소 소비 우선 순위 검색 대기열, 우선 순위 대기열 각 노드에는 제약 조건을 만족하는지 알아보기 위해 라이브 노드가 될 수 있는 한 번의 기회 특정 의미에서 솔루션 또는 최적의 솔루션
더 많은 관련 지식을 보려면 FAQ 칼럼을 방문하세요! 
위 내용은 다섯 가지 고전적인 컴퓨터 알고리즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!