가장 일반적으로 사용되는 5가지 알고리즘은 무엇입니까?

일반적으로 사용되는 알고리즘은 다음과 같습니다. 1. 분할 및 정복 방법 2. 특정 최적 솔루션 문제를 위한 더 간단하고 빠른 설계 기술인 탐욕 알고리즘 4. 역추적 방법, 선택 및 최적화 검색 방법 5. 분기 및 바인딩 방법.

가장 일반적으로 사용되는 5가지 알고리즘은 분할 정복 방법, 탐욕 알고리즘, 동적 프로그래밍 알고리즘, 역추적 방법, 분기 및 경계 방법입니다.

알고리즘이란 무엇인가요?

알고리즘은 문제 해결 솔루션에 대한 정확하고 완전한 설명을 의미합니다. 이는 문제 해결을 위한 일련의 명확한 지침입니다. 알고리즘은 문제 해결을 위한 전략적 메커니즘을 설명하는 체계적인 방법을 나타냅니다.

알고리즘은 특정 문제를 해결하는 데 사용되는 일련의 단계라고 이해할 수 있습니다. 알고리즘에는 다음 세 가지 중요한 특성이 있어야 합니다.

1. 유한한 수의 단계를 실행한 후에는 알고리즘이 종료되어야 합니다.

2. 정확성. 알고리즘의 각 단계는 정확하게 정의되어야 합니다.

3. 타당성. 특정 알고리즘은 특정 시간 내에 특정 문제를 해결할 수 있어야 합니다.

가장 일반적으로 사용되는 5가지 알고리즘

분할 및 정복 방법

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

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

1) 문제의 규모를 어느 정도 축소하면 쉽게 해결할 수 있습니다. 여러 규모로 분해됨 더 작은 동일한 문제, 즉 문제가 최적의 하위 구조 속성을 가짐

3) 이 문제에 의해 분해된 하위 문제에 대한 솔루션이 이 문제의 솔루션으로 결합될 수 있음

4) , 이 문제에 의해 분해된 솔루션 각 하위 문제는 서로 독립적입니다. 즉, 하위 문제 사이에 공통 하위 문제가 없습니다.

그리디 알고리즘

그리디 알고리즘은 특정 최적의 솔루션 문제에 대한 더 간단하고 빠른 설계 기술입니다.

탐욕적 방법 설계 알고리즘은 단계별로 진행되는 것이 특징이며, 가능한 다양한 전체 상황을 고려하지 않고 현재 상황과 최적화 조치를 기반으로 최적의 선택을 하는 경우가 많습니다. 모든 가능성을 소진하는 데는 많은 시간이 소요됩니다. 하향식 및 반복적 방법을 사용하여 연속적인 탐욕스러운 선택을 할 때마다 원하는 문제는 각각의 One-Problem을 통해 더 작은 하위 문제로 단순화됩니다. 단계 탐욕적 선택은 문제에 대한 최적의 솔루션을 얻을 수 있습니다. 각 단계에서 로컬 최적 솔루션을 얻을 수 있는지 확인하는 것이 필요하지만 결과적인 전역 솔루션이 반드시 최적이 아닐 수도 있으므로 그리디 알고리즘은 역추적하지 않습니다.

동적 프로그래밍 알고리즘

동적 프로그래밍은 수학과 컴퓨터 과학에서 중복되는 하위 문제가 포함된 최적화 문제를 해결하는 데 사용되는 방법입니다. 기본 아이디어는 원래 문제를 유사한 하위 문제로 분해하고, 문제를 해결하는 과정에서 하위 문제의 해결을 통해 원래 문제에 대한 해결책을 얻는 것입니다. 동적 프로그래밍의 아이디어는 많은 알고리즘의 기초이며 컴퓨터 과학 및 엔지니어링 분야에서 널리 사용됩니다.

동적 프로그래밍 방법은 일반적으로 최적화 문제를 해결하는 데 사용됩니다. 이러한 유형의 문제에는 여러 가지 가능한 솔루션이 있을 수 있습니다. 각 솔루션에는 최적의 값이 있는 솔루션을 찾는 것이 최적 솔루션이 아니라 문제에 대한 최적 솔루션이라고 합니다. 솔루션에는 모두 최적의 값에 도달하는 솔루션이 여러 개 있을 수 있습니다.

동적 프로그래밍 알고리즘 설계 단계:

1) 최적 솔루션의 구조적 특성 특성화

2) 최적 솔루션의 값을 재귀적으로 정의

3) 최적 솔루션의 값 계산, 일반적으로 자동 상향식 방법

4)을 사용하여 계산된 정보를 사용하여 최적의 솔루션을 구성합니다

동적 프로그래밍은 분할 정복 방법과 유사하며 둘 다 원래 문제를 해결하기 위해 하위 문제에 대한 솔루션을 결합합니다. 분할정복 방식과의 차이점은 분할정복 방식은 하위 문제가 서로 독립적으로 존재하는 반면, 동적 프로그래밍은 하위 문제가 겹칠 때 사용된다는 점이다.

역추적 방법

역추적 방법(탐색 및 역추적 방법)은 목표를 달성하기 위해 최적의 조건에 따라 앞으로 탐색하는 최적 검색 방법입니다. 그러나 탐색의 특정 단계에 도달하여 원래 선택이 최적이 아니거나 목표를 달성할 수 없다는 것을 알게 되면 한 걸음 물러나서 작동하지 않을 때 다시 시도하는 이 기술은 다음과 같습니다. 역추적 방법과 역추적 조건을 만족하는 특정 상태의 지점을 '룩백 포인트'라고 합니다.

기본 아이디어는 문제에 대한 모든 솔루션을 포함하는 솔루션 공간 트리에서 깊이 우선 검색 전략에 따라 루트 노드에서 시작하여 솔루션 공간 트리를 깊이 탐색하는 것입니다. 노드를 탐색할 때 먼저 노드에 문제에 대한 솔루션이 포함되어 있는지 확인해야 합니다. 포함되어 있으면 이 노드에서 계속 탐색합니다. 노드에 문제에 대한 솔루션이 포함되어 있지 않으면 해당 노드로 계층별로 진행합니다. 조상. 노드 역추적.

분기 및 바인딩 방법

분기 및 바인딩 방법은 매우 널리 사용되는 알고리즘입니다. 이 알고리즘의 사용은 매우 능숙하며 다양한 유형의 문제에 대한 솔루션도 다릅니다.

분기 및 경계 방법의 기본 아이디어는 제약 조건이 있는 최적화 문제에 대해 가능한 모든 솔루션(제한된 수)의 공간을 검색하는 것입니다. 알고리즘이 구체적으로 실행되면 전체 실현 가능한 솔루션 공간이 점점 더 작은 하위 집합(분기라고 함)으로 분할되고 각 하위 집합의 솔루션 값에 대해 하한 또는 상한(구분이라고 함)이 계산됩니다. 각 분기 후에는 한계가 알려진 실행 가능한 솔루션 값을 초과하는 하위 집합에 대해 더 이상 분기가 생성되지 않습니다. 이러한 방식으로 솔루션의 많은 하위 집합(즉, 검색 트리의 많은 노드)을 무시할 수 있으므로 검색 범위가 좁아집니다. 범위. 이 프로세스는 값이 하위 집합의 범위보다 크지 않은 실행 가능한 솔루션을 찾을 때까지 계속됩니다. 따라서 이 알고리즘은 일반적으로 최적의 솔루션을 얻을 수 있습니다.

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