안나의 취뽀일기 (˵ •̀ ᴗ - ˵ ) ✧/SW 부트캠프2 [SW_2] Meta-heuristic: TSP(외판원문제) - simulated annealing(담금질 기법) 1. Meta-heuristic : 특정 문제에 특화되지 않고 자연에서 영감을 얻은 경험적 방법 대표적인 meta-heuristic : Simulated Annealing, Tabu Search, Genetic Algorithms, Ant Colony Optimizatio 2. Simulated Annealing(담금질 기법) : 커다란 탐색공간에서 주어진 함수의 전역 최적점(global optimum)에 대 한 훌륭한 근사치를 찾으려고 하는 전역최적화 문제에 대한 일반적인 활률적 휴리스틱 접근 방법이다. 금속의 담금질(annealing) 이란 고체를 녹을때 까지 가열하고 난 후 그것을 완전한 결정체가 될때까지 식히는 물리적인 과정으로 이 과정에서 고체의 자유에너지는 최소화된다. 이런 과정에서 내부의 결.. 2022. 9. 15. [SW_2] Heuristic: a routing problem(TSP, 외판원문제) - Greedy 1. Heuristic : "경험적인, 스스로 발견하게 하는" 이라는 뜻으로 시간이나 정보가 부족하여 합리적인 판단을 할수 없거나 굳이 판단하지 않아도 사람들이 빠르게 사용할 수 있도록 하는 간편추론의 방법이다. 휴리스틱의 알고리즘은 문제에 대한 모든 솔루션 중 최선일 수도 있고 단순히 정확한 솔루션에 근접할 수 있다. 즉 휴리스틱을 통해 해결된 문제에 대한 답은 가장 좋은 답이 아닐 수도 있다. 관련 알고리즘으로는 가지치기(pruning) 기법, Simulated Annealing(담금질 기법), Genetic Algorithms(유전알고리즘) 이 있다. 2. Routing problem : 여러 노드를 방문하는 경로에 대해 가장 최소로 하는 최적의 경로를 찾는 문제 3. 외판원 문제(Traveling.. 2022. 9. 15. 이전 1 다음 반응형
