데이터 구조-욕심 많은 알고리즘

알고리즘은 주어진 문제에 대해 최적의 솔루션을 달성하도록 설계되었습니다. 탐욕스러운 알고리즘 접근 방식에서는 주어진 솔루션 도메인에서 결정이 내려집니다. 탐욕 스럽기 때문에 최적의 솔루션을 제공하는 것으로 보이는 가장 가까운 솔루션이 선택됩니다.

Greedy 알고리즘은 지역화 된 최적 솔루션을 찾으려고하는데, 결국 글로벌 최적화 솔루션으로 이어질 수 있습니다. 그러나 일반적으로 탐욕스러운 알고리즘은 전체적으로 최적화 된 솔루션을 제공하지 않습니다.

동전 세기

이 문제는 가능한 가장 적은 동전을 선택하여 원하는 값으로 계산하는 것이며 탐욕스러운 접근 방식은 알고리즘이 가능한 가장 큰 동전을 선택하도록합니다. ₹ 1, 2, 5, 10의 코인이 제공되고 ₹ 18을 세도록 요청받은 경우 탐욕스러운 절차는 다음과 같습니다.

• 1 − ₹ 10 동전 하나를 선택하면 남은 개수는 8 개입니다.

• 2 − 그런 다음 ₹ 5 동전 하나를 선택하면 남은 개수는 3 개입니다.

• 3 − 그런 다음 ₹ 2 동전 하나를 선택하면 남은 개수는 1입니다.

• 4 − 마지막으로 ₹ 1 코인 하나를 선택하면 문제가 해결됩니다.

그래도 잘 작동하는 것 같지만,이 카운트에서는 4 개의 동전 만 선택하면됩니다. 그러나 문제를 약간 변경하면 동일한 접근 방식으로 동일한 최적의 결과를 얻을 수 없습니다.

1, 7, 10 가치의 동전이있는 통화 시스템의 경우 가치 18에 대한 동전 계산이 절대적으로 최적이지만 15와 같은 계산의 경우 필요 이상으로 많은 동전을 사용할 수 있습니다. 예를 들어, 탐욕스러운 접근 방식은 10 + 1 + 1 + 1 + 1 + 1, 총 6 개의 동전을 사용합니다. 동전 3 개 (7 + 7 + 1) 만 사용하면 같은 문제를 해결할 수 있습니다.

따라서 탐욕스러운 접근 방식은 즉시 최적화 된 솔루션을 선택하고 글로벌 최적화가 주요 관심사 인 경우 실패 할 수 있다고 결론을 내릴 수 있습니다.

예

대부분의 네트워킹 알고리즘은 탐욕스러운 접근 방식을 사용합니다. 여기에 몇 가지 목록이 있습니다.

• 여행하는 세일즈맨 문제
• Prim의 최소 스패닝 트리 알고리즘
• Kruskal의 최소 스패닝 트리 알고리즘
• Dijkstra의 최소 스패닝 트리 알고리즘
• 그래프-지도 색칠
• 그래프-정점 커버
• 배낭 문제
• 작업 일정 문제

탐욕스러운 접근 방식을 사용하여 최적의 솔루션을 찾는 유사한 문제가 많이 있습니다.