조합 최적화

조합 최적화

• 주어진 이산적인 탐색 공간에서 최적의 해를 찾는 수학적 최적화 문제를 다루는 분야
  • 이러한 문제는 가능한 경우의 수가 너무 많아서 완전 탐색에는 비효율적이다. 그래서 보다 효율적인 알고리즘 개발이 중요
• 주요 특징
  • 이산적인 탐색 공간 : 해의 후보들이 이산적인 집합으로 정의되며, 연속적인 값이 아닌 경우가 많다.
  • np-완전 문제로 분류된다.
• 대표적인 조합 최적화 문제
  • 외판원 문제
    • 여러 도시를 한번씩만 방문하고 출발지로 돌아오는 최소 비용의 경로를 찾는 문제
  • 배낭 문제
    • 한전된 용량의 배낭에 최대 가치를 가지는 아이템들을 선택하는 문제
  • 최소 비용 신장 트리
    • 모든 노드를 연결하는 최소 비용의 트리를 찾는 문제
• 조합 최적화를 해결하려면?
  • 정확한 알고리즘을 사용한다
    • ex) 동적 계획법 , branch and bound , integer linear programming
  • 근사 알고리즘으로 근사해를 구한다.
    • ex) 유전 알고리즘 , tabu search , simulated annealing