탐욕적 방법은 문제를 해결하기 위해 사용되는 분할 정복과 같은 전략 중 하나입니다. 이 방법은 최적화 문제를 해결하는 데 사용됩니다. 최적화 문제는 최대 또는 최소 결과를 요구하는 문제입니다. 몇 가지 용어를 통해 이해해 봅시다.
Greedy 방법은 가장 간단하고 직접적인 접근 방식입니다. 알고리즘은 아니지만 기술입니다. 이 접근 방식의 주요 기능은 현재 이용 가능한 정보를 기반으로 결정이 내려진다는 것입니다. 현재 정보가 무엇이든 현재 결정이 미래에 미칠 영향을 걱정하지 않고 결정이 내려집니다.
자바 날짜 현재
이 기술은 기본적으로 최적일 수도 있고 아닐 수도 있는 실행 가능한 솔루션을 결정하는 데 사용됩니다. 실현 가능한 솔루션은 주어진 기준을 만족하는 하위 집합입니다. 최적의 솔루션은 하위 집합에서 가장 좋고 가장 유리한 솔루션입니다. 실행 가능한 경우, 둘 이상의 솔루션이 주어진 기준을 충족하면 해당 솔루션은 실행 가능한 것으로 간주되는 반면, 최적 솔루션은 모든 솔루션 중에서 가장 좋은 솔루션입니다.
Greedy 방식의 특징
그리디 메소드의 특징은 다음과 같습니다.
- 최적의 방식으로 솔루션을 구성하기 위해 이 알고리즘은 한 세트에는 선택한 모든 항목이 포함되고 다른 세트에는 거부된 항목이 포함되는 두 개의 세트가 생성됩니다.
- Greedy 알고리즘은 솔루션이 실현 가능하거나 최적이어야 한다는 희망으로 좋은 로컬 선택을 수행합니다.
그리디 알고리즘의 구성요소
그리디 알고리즘에 사용할 수 있는 구성 요소는 다음과 같습니다.
MB에서 GB로
그리디 알고리즘의 응용
- 최단 경로를 찾는 데 사용됩니다.
- 프림(Prim) 알고리즘이나 크루스칼(Kruskal) 알고리즘을 이용하여 최소신장트리를 찾는 데 사용됩니다.
- 마감일이 있는 작업 순서에 사용됩니다.
- 이 알고리즘은 분수 배낭 문제를 해결하는 데에도 사용됩니다.
그리디 알고리즘의 의사 코드
Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } 위는 그리디 알고리즘이다. 처음에는 솔루션에 0 값이 할당됩니다. 그리디 알고리즘에 배열과 요소 수를 전달합니다. for 루프 내에서 요소를 하나씩 선택하고 솔루션이 가능한지 여부를 확인합니다. 솔루션이 실현 가능하면 합집합을 수행합니다.
예를 통해 이해해 봅시다.
문제 'P'가 있다고 가정해보자. 아래와 같이 A에서 B로 이동하고 싶습니다.
피 : A → B
문제는 우리가 A에서 B로 가는 이 여정을 여행해야 한다는 것입니다. A에서 B로 가는 데는 다양한 해결책이 있습니다. 우리는 다음과 같이 A에서 B로 갈 수 있습니다. 산책, 자동차, 자전거, 기차, 비행기 , 등. 이 여행은 12시간 이내에 여행해야 한다는 제약이 있습니다. 기차나 비행기로만 가면 이 거리를 12시간 안에 갈 수 있어요. 이 문제에 대한 해결책은 많지만 제약 조건을 충족하는 해결책은 두 가지뿐입니다.
우리가 최소한의 비용으로 여행을 감당해야 한다고 말한다면. 이는 이 거리를 가능한 한 최소로 이동해야 함을 의미하므로 이 문제를 최소화 문제라고 합니다. 지금까지 우리는 두 가지 가능한 솔루션, 즉 기차를 이용하는 방법과 항공을 이용하는 방법을 가지고 있습니다. 기차로 여행하면 비용이 최소화되므로 최적의 솔루션입니다. 최적의 솔루션은 실현 가능한 솔루션이기도 하지만 최상의 결과를 제공하므로 솔루션은 최소 비용으로 최적의 솔루션이 됩니다. 최적의 솔루션은 단 하나뿐입니다.
최소 또는 최대 결과가 필요한 문제를 최적화 문제라고 합니다. Greedy 방법은 최적화 문제를 해결하는 데 사용되는 전략 중 하나입니다.
자바스크립트 인쇄
Greedy 알고리즘 사용의 단점
Greedy 알고리즘은 더 광범위한 문제를 고려하지 않고 각 단계에서 사용 가능한 정보를 기반으로 결정을 내립니다. 따라서 탐욕스러운 솔루션이 모든 문제에 대해 최상의 솔루션을 제공하지 못할 가능성이 있을 수 있습니다.
전역 최적을 찾으려는 의도로 각 단계에서 지역 최적 선택을 따릅니다. 예를 통해 이해해 봅시다.
아래에 주어진 그래프를 고려하십시오.
우리는 최소한의 비용으로 출발지에서 목적지까지 이동해야 합니다. 비용 경로가 10, 20, 5인 세 가지 가능한 솔루션이 있으므로 5가 최소 비용 경로이므로 최적 솔루션입니다. 이것이 지역 최적해(Local Optimal)이며, 이와 같이 전역 최적해(Global Optimal Solution)를 계산하기 위해 각 단계에서 지역 최적해(Local Optimal)를 찾는다.
자바의 char + int