탐욕 알고리즘

탐욕 알고리즘은 각 ^[1]단계에서 국소적으로 최적의 선택을 하는 문제 해결 휴리스틱을 따르는 알고리즘입니다.많은 문제에서 탐욕적 전략은 최적의 솔루션을 생산하지 않지만 탐욕적 휴리스틱은 합리적인 시간 내에 전체적으로 최적의 솔루션에 가까운 최적의 솔루션을 국소적으로 생산할 수 있다.

예를 들어, 여행 중인 세일즈맨 문제에 대한 탐욕스러운 전략(계산 복잡성이 높음)은 다음과 같은 경험적 접근법입니다. "여행의 각 단계에서 방문하지 않은 가장 가까운 도시를 방문하십시오."이 휴리스틱은 최적의 해결책을 찾는 것이 아니라 적당한 수의 단계로 종료됩니다.이러한 복잡한 문제에 대한 최적의 해결책을 찾는 데는 일반적으로 불합리하게 많은 단계가 필요합니다.수학적 최적화에서 탐욕 알고리즘은 매트로이드의 특성을 갖는 조합 문제를 최적으로 해결하고 하위 모듈 구조의 최적화 문제에 상수 요인 근사치를 제공한다.

사양

탐욕스러운 알고리즘은 어떤 수학적인 문제에는 좋은 해결책을 제시하지만 다른 문제에는 그렇지 않습니다.대부분의 문제에는 다음 두 가지 속성이 있습니다.

욕심 많은 선택 속성

현재 최선의 선택이라고 생각되는 것은 무엇이든 할 수 있으며, 그 후 발생하는 서브 문제를 해결할 수 있습니다.탐욕 알고리즘에 의한 선택은 지금까지 이루어진 선택에 따라 달라질 수 있지만, 미래의 선택이나 하위 문제에 대한 모든 해결책에 따라 달라지는 것은 아니다.반복적으로 욕심 많은 선택을 반복하여 주어진 문제를 더 작은 문제로 축소합니다.즉, 탐욕스러운 알고리즘은 그 선택을 재고하지 않습니다.이것이 완전하고 해결책을 찾을 수 있는 동적 프로그래밍과의 주요 차이점이다.모든 단계 후에 동적 프로그래밍은 이전 단계에서 이루어진 모든 결정을 기반으로 결정을 내리고 솔루션에 대한 이전 단계의 알고리즘 경로를 재고할 수 있습니다.

최적의 하부 구조

문제에 대한 최적의 해결책이 하위 문제에 ^[2]대한 최적의 해결책을 포함하는 경우 문제는 최적의 하위 구조를 나타냅니다.

실패 사례

탐욕스러운 알고리즘은 다른 많은 문제에 대한 최적의 해결책을 도출하지 못하고 심지어 가능한 한 최악의 해결책을 도출할 수도 있습니다.한 가지 예는 위에서 언급한 여행 세일즈맨 문제입니다. 각 도시 수마다, 가장 가까운 이웃의 휴리스틱이 가능한 최악의 ^[3]투어를 생성하는 도시들 사이의 거리가 할당됩니다.다른 가능한 예는 수평 효과를 참조하십시오.

종류들

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2018년 6월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

탐욕 알고리즘은 '근시안적'으로, '복구 불가'로 특징지을 수 있습니다.이들은 '최적의 하부구조'를 가진 문제에만 이상적입니다.그럼에도 불구하고 많은 간단한 문제에 대해 가장 적합한 알고리즘은 탐욕적입니다.단, 탐욕 알고리즘은 검색 내 옵션 또는 분기 및 경계 알고리즘에서 우선 순위를 지정하는 선택 알고리즘으로 사용할 수 있습니다.그리디 알고리즘에는 몇 가지 종류가 있습니다.

• 순수 탐욕 알고리즘
• 직교 그리디 알고리즘
• 느슨한 탐욕 알고리즘

이론.

탐욕 알고리즘은 조합 최적화와 이론 컴퓨터 과학에 대한 오랜 연구 역사를 가지고 있습니다.탐욕적 휴리스틱스는 많은 ^[4]문제에 대해 차선의 결과를 생성하는 것으로 알려져 있으며, 따라서 다음과 같은 자연스러운 질문이 있습니다.

• 탐욕 알고리즘이 최적으로 작동하는 문제는 무엇입니까?
• 탐욕 알고리즘이 거의 최적의 솔루션을 보장하는 문제는 무엇입니까?
• 탐욕 알고리즘이 최적의 솔루션을 생성하지 않도록 보장되는 문제는 무엇입니까?

모트로이드와 같은 일반적인 종류의 문제와 세트 커버와 같은 특정 문제에 대한 이러한 질문에 대한 많은 문헌이 존재한다.

매트로이드

매트로이드는 벡터 공간에서 임의의 집합으로 선형 독립의 개념을 일반화하는 수학적 구조입니다.최적화 문제가 매트로이드의 구조를 가지고 있는 경우, 적절한 탐욕 알고리즘은 그것을 ^[5]최적으로 해결한다.

서브모듈러 함수

set$$${\displaystyle \omega }$ \ $displaystyle$\$Omega }$의 서브셋에 정의되어 있는 $함수{\displaystyle }$f { $displaystyle$ f$}$는 s${\displaystyle ,}$ $t,$ $subseteq$\ $Omega }$마다 $f{\displaystyle (S)}$ + ${\displaystyle f(T)}$+${\displaystyle f(S}$t T) +${\displaystyle }$F${\displaystyle (S}$ ${\displaystyle t}$ T ${\displaystyle t}$ S${\displaystyle )}$가 있는 경우 서브 모듈러라고 불립니다.

f{$displaystyle$ f$\}$를 $최대화$하는 S${displaystyle$ S$}$ $세트$를 찾고 싶다고 가정합니다.는 점진적으로 가장 각 단계에서 f{\displaystyle f}을 향상시키는 요소를 첨가하여 1세트 S{S\displaystyle} 쌓이는 탐욕 알고리즘,, 출력으로서}.[6]와 함께 있고 탐욕스러운 상태가 살고 있는 세트 적어도(1− 1/e)최대 XΩ f({\displaystyle(1-1/e)\max_{X\subseteq)}(X)⊆을 생산한다.에서( ${\displaystyle 1}$-${\displaystyle 1}$ /${\displaystyle e}$ )${\displaystyle 0}$0.${\displaystyle 63}${ $displaystyle$( 1 - 1 / $e$)\ $0$0.63$$$。{\displaystyle }$

출력에 카디널리티 ^[7]제약과 같은 추가 제약이 가해진 경우에도 유사한 보증이 가능하지만, 종종 탐욕 알고리즘에 약간의 변화가 요구됩니다.개요에 대해서는, 을 참조해 주세요.

보증에 관한 기타 문제

탐욕 알고리즘이 최적의 솔루션이 아닌 강력한 보증을 제공하는 다른 문제는 다음과 같습니다.

• 세트 커버
• Steiner 트리 문제
• 로드 밸런싱^[9]
• 독립 집합

이러한 문제의 대부분은 일치하는 하한을 가지고 있습니다.즉, 탐욕 알고리즘은 최악의 경우 보증보다 더 나은 성능을 발휘하지 못합니다.

적용들

이 섹션은 확장해야 합니다.추가해서 도와주시면 됩니다. (2018년 6월)

일반적으로 그리디 알고리즘은 모든 데이터에 대해 완전히 동작하지 않기 때문에(항상 그렇지는 않지만) 글로벌하게 최적의 솔루션을 찾지 못합니다.특정 선택을 너무 일찍 약속하여 나중에 최적의 솔루션을 찾지 못하게 할 수 있습니다.예를 들어 그래프 색칠 문제와 다른 모든 NP-완전 문제에 대해 알려진 모든 탐욕 색칠 알고리즘은 일관되게 최적의 해결책을 찾지 못합니다.그럼에도 불구하고, 그것들은 생각이 빠르고 종종 최적의 근사치를 제공하기 때문에 유용하다.

탐욕 알고리즘이 주어진 문제 클래스에 대해 전역 최적화를 제공하는 것을 증명할 수 있는 경우, 동적 프로그래밍과 같은 다른 최적화 방법보다 빠르기 때문에 일반적으로 선택 방법이 됩니다.이러한 탐욕 알고리즘의 예로는 최소 스패닝 트리를 찾는 Kruskal 알고리즘과 Prim 알고리즘, 최적의 Huffman 트리를 찾는 알고리즘 등이 있습니다.

그리디 알고리즘은 네트워크 라우팅에도 표시됩니다.그리디 루팅을 사용하면 메시지는 수신처에 "가장 가까운" 인접 노드로 전송됩니다.노드의 로케이션(및 「근접성」)의 개념은, 애드혹네트워크에 의해서 사용되는 지리적 라우팅과 같이, 노드의 물리적인 로케이션에 의해서 결정되는 경우가 있습니다.로케이션은 소규모 월드 라우팅 및 분산 해시 테이블과 같이 완전히 인위적인 구성일 수도 있습니다.

예

• 액티비티 선택 문제는 이러한 종류의 문제의 특징이며, 목표는 서로 충돌하지 않는 액티비티의 최대 수를 선택하는 것입니다.
• 매킨토시 컴퓨터 게임 Crystal Quest의 목적은 출장 세일즈맨 문제와 유사한 방식으로 크리스털을 수집하는 것입니다.이 게임에는 데모 모드가 있는데, 이 모드에서는 게임이 모든 크리스털로 이동하는 탐욕스러운 알고리즘을 사용합니다.인공지능은 장애물을 설명하지 않기 때문에 데모 모드가 빨리 종료되는 경우가 많습니다.
• 매칭 추구는 신호 근사치에 적용되는 탐욕 알고리즘의 예입니다.
• 탐욕 알고리즘은 원의 총 면적을 최대화하는 주어진 삼각형 내에서 세 개의 분리된 원을 찾는 말파티의 문제에 대한 최적의 해결책을 찾는다. 같은 탐욕 알고리즘이 임의의 수의 원에 최적이라고 추측된다.
• Gready 알고리즘은 최적의 솔루션을 찾는 Huffman 코딩 중에 Huffman 트리를 구성하기 위해 사용됩니다.
• 의사결정 트리 학습에서는 탐욕 알고리즘이 일반적으로 사용되지만 최적의 솔루션을 찾을 수 있다고 보장되지는 않는다.
  • 그러한 알고리즘 중 하나는 의사결정 트리 구축을 위한 ID3 알고리즘입니다.
• Dijkstra 알고리즘 및 관련 A* 검색 알고리즘은 그래프 검색 및 최단 경로 찾기에 검증 가능한 최적의 그리디 알고리즘입니다.
  • A* 검색은 조건부로 최적입니다.패스 비용을 과대평가하지 않는 "허용 가능한 경험적 접근법"이 필요합니다.
• Kruskal 알고리즘과 Prim 알고리즘은 연결된 그래프의 최소 스패닝 트리를 구성하기 위한 탐욕 알고리즘입니다.이들은 항상 최적의 솔루션을 찾으며, 이는 일반적으로 고유하지 않을 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

원천

외부 링크

• "Greedy algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Gift, Noah. "Python greedy coin example".