조합 최적화

수학적 최적화의 하위 분야
(조합최적화에서 넘어옴)

응용수학전산학에서 조합 최적화최적화 문제의 일종으로서, 운용 과학, 알고리즘 이론, 계산 복잡도 이론과 관련되어 있고, 인공지능, 수학, 소프트웨어 공학과 영역이 겹친다. 조합 최적화에서는 일반적으로 어렵다고 보는 문제를 풀려고 한다. 어려운 문제들은 보통 문제 공간이 크기 때문에 조합 최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데 중점을 둔다.

계산 복잡도 이론의 연구 결과가 조합 최적화에서 쓸모있는 경우가 많다. 조합 최적화 알고리즘은 보통 NP-완전인 문제를 다루는데, 일반적으로 NP-완전 문제는 쉽게 풀 수 없다고 보고 있다. 그러나 복잡도 이론의 여러 근사에 따르면 몇몇 특수한 경우에는 효율적으로 풀 수 있다. 조합 최적화에서는 바로 이러한 경우에 대해 관심을 갖는다. 이런 경우는 중요하고 실용적인 응용을 할 수 있을 때가 많다.

약식 정의

편집

조합 최적화의 영역은 가능해이산 집합에 속하거나 이산적인 것으로 변환될 수 있고, 가장 좋은 해를 찾는 것이 목적인 최적화 문제이다.

엄밀한 정의

편집

조합 최적화 문제의 인스턴스튜플 (X,P,Y,f,extr)로 쓸 수 있다. 여기서 각 기호는 아래와 같은 뜻이다.

대표적인 문제

편집

방법

편집

아래 열거한 발견 탐색 방법(메타휴리스틱 알고리즘)은 조합 최적화 문제를 푸는 데 흔히 사용된다.

관련글

편집

한 탐색 기법이 다른 기법들을 모든 문제에 대해서 능가할 수 있는가 하는 문제는 많은 사람들의 관심을 끌어 왔다. 수많은 문제군에 대해서 정답은 '아니오'이다:

참고 문헌

편집
  • Alexander Schrijver; A Course in Combinatorial Optimization February 1, 2006 (© A. Schrijver)
  • William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 0-471-55894-X.
  • Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
  • Christos H. Papadimitriou and Kenneth Steiglitz Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0-486-40258-4.
  • Arnab Das and Bikas K. Chakrabarti (Eds.) Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)

학술지

편집