이 문서는 Google Cloud Translation API를 사용해 자동 번역되었습니다.
어떤 문서는 원문을 읽는게 나을 수도 있습니다.
Greedy 알고리즘은 전체 목표를 달성하기 위해 각 단계에서 최선의 선택을 하는 알고리즘 유형입니다. 예를 들어 목표가 A지점에서 B지점까지의 최단 경로를 찾는 것이라면 그리디 알고리즘은 전체 경로 길이에 관계없이 각 단계에서 최단 경로를 선택합니다.
탐욕 알고리즘의 가장 유명한 예 중 하나는 여행하는 세일즈맨 문제입니다. 이 문제의 목표는 각 도시를 정확히 한 번 방문하고 출발점으로 돌아가는 최단 경로를 찾는 것입니다. 이 문제에 대한 순진한 접근 방식은 가능한 모든 경로를 시도하고 각각의 길이를 비교하는 것입니다. 그러나 이것은 매우 비효율적이며 실행하는 데 오랜 시간이 걸립니다.
반면 탐욕적인 알고리즘은 다음 단계를 수행합니다.
위의 단계는 항상 경로를 찾지만 최단 경로는 아닐 수 있습니다. 경우에 따라 그리디 알고리즘을 사용하여 최적의 솔루션을 찾을 수 있습니다. 다른 경우에는 그렇지 않습니다.
다음과 같은 도시와 그 사이의 거리가 있다고 가정해 보겠습니다.
City 1: 0km
City 2: 100km
City 3: 200km
City 4: 300km
City 5: 400km
위에서 설명한 그리디 알고리즘을 사용하는 경우 취한 경로는 다음과 같습니다.
City 1 -> City 2 -> City 3 -> City 4 -> City 5 -> City 1
총 거리는 다음과 같습니다.
0 + 100 + 200 + 300 + 400 + 0 = 1000km
그러나 최적의 경로는 다음과 같습니다.
City 1 -> City 5 -> City 4 -> City 3 -> City 2 -> City 1
총 거리는 다음과 같습니다.
0 + 400 + 300 + 200 + 100 + 0 = 1000km
보시다시피 탐욕 알고리즘이 항상 최적의 솔루션을 찾는 것은 아닙니다. 그러나 일반적으로 무차별 대입 방식과 같은 다른 알고리즘보다 훨씬 빠르므로 실제로 자주 사용됩니다.
City 1: 0km
City 2: 10km
City 3: 15km
City 4: 20km
City 5: 25km
이동한 경로와 총 거리는 얼마입니까? 이것이 최적의 경로입니까?
City 1: 0km
City 2: 100km
City 3: 200km
City 4: 300km
City 5: 400km
이동한 경로와 총 거리는 얼마입니까? 이것이 최적의 경로입니까?
다른 도시 및 거리 집합을 시도하고 알고리즘이 선택한 경로를 확인합니다. 알고리즘이 최적의 경로를 찾지 못하는 집합을 찾을 수 있습니까?
항상 최적의 경로를 찾도록 알고리즘을 개선하십시오.