탐욕 알고리즘

위키백과 ― 우리 모두의 백과사전.

표제어를 변경하자는 제안이 있습니다. (토론)

탐욕 알고리듬(貪慾 - , Greedy Algorithm 그리디 알고리듬^[*])은 최적의 해를 구하기 위해, 결정을 해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간(local)에는 최적이지만, 그 선택들을 계속 수집하여 최종적인(global) 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

탐욕 알고리듬이 최적해를 구한다는 것을 보장하려면 두 가지 조건이 성립해야 한다. 탐욕스런 선택 조건과 최적 부분 구조 조건이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리듬은 최적해를 구하지 못한다. 그러나 이러한 경우에도 탐욕 알고리즘은 여전히 유용할 수 있다. 탐욕 알고리듬은 대개 빠르게 작동하기 때문에 좋은 근사 알고리즘^[통용]이 될 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

[편집] 메이트로이드(matroid)

이 부분의 본문은 메이트로이드입니다.

어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리듬이 언제나 최적해를 찾아낼 수 있다. 이 구조를 메이트로이드(matroid, IPA: [ˈmeɪtrɔɪd] )라 한다. 메이트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리듬의 활용도를 높여 준다.

[편집] 참고 문헌

• 토머스 코르먼, 찰스 E. 레이서슨, 로널드 L. 라이베스트, 클리포드 스타인 (2001). "16. 그리디 알고리즘^[통용]", Introduction to Algorithms, 2판, MIT Press and McGraw-Hill. ISBN 0-262-53196-8

이 글은 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.