Travelling Salesman Problem

https://medium.com/ivymobility-developers/algorithm-a168afcd3611

Algorithm

 

개인적 공부를 공유하기 위한 게시글

오역, 의역에 주의하세요!

 

 

그리디 알고리즘이라고 일컬어지는 것들은, 언제나 그 순간에 최선의 선택을 한다.

이것은 지엽적인 최적의 선택이 전체적으로 최적의 해결책되기를 희망하는 것이다. (역자 해설 : 국소 범위의 최선의 선택을 하는 방법이 전체에 적용되었을 때에도 최적의 선택이길 바란다는 뜻)

 

어떤 선택이 최선인지 어떻게 결정할까?

최적화 될 필요가있는 objective function이 있다고 가정하자. 

그리디 알고리즘은 objective function의 최적화를 확실하게 하기 위해 각 단계에서 탐욕적인 선택을 한다.

그리디 알고리즘은 계산할 오직 한번의 기회를 가진다. 그래서 결정을 되돌리지 않는다.

 

그리디 알고리즘은 장점과 단점을 가진다.

장점

1. 문제를 위해 그리디 알고리즘을 생각해내기 매우 쉽다
2. 다른 테크닉들 보다 그리디 알고리즘을 위한 작동시간을 분석하는것은 더 쉽다. 왜냐하면, branching 또는 backtracking이 없기 때문이다.

단점

1. 이는 최적의 솔루션을 제공하지 않는다.
2. 그리디 알고리즘이 맞는지 증명하는것은 어렵다

넓은 범위의 문제에서 그리디 알고리즘은 매우 강력하고 잘 작동한다.

많은 알고리즘들은 그리디 알고리즘의 applications로 볼 수 있다.

예를 들어 :

 

1. Minimum Spanning Tree
2. dijkstra's algorithm for shortest paths from a single source
3. Huffmans codes (data-compression codes)

Travelling Salesman Problem에서 그리디 알고리즘이 어떻게 작동하는지 살펴보자

 

TSP를 위한 그리디 알고리즘

이 알고리즘은 지엽적인 최적 값을 검색하거나 전체적인 최적 값을 위해 지엽적 솔루션을 최적화 한다.

이것은 모든 모서리를 정렬하는것으로 시작하며, 그 뒤에 최소값의 모서리를 선택한다.

이는 반복이 생기지 않도록하는 조건에서, 계속해서 최선의 선택을 한다.

그리디 알고리즘의 계산적인 복잡성은 O( N 2 log2 (N))이고, 전체적인 최적 솔루션이 발견된다는 보장은 없다.

 

 

관련된 이미지는 직접 들어가서 확인해주세요!

오직 텍스트의 번역만을 제공합니다!