조합 최적화 문서 원본 보기

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

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

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

== 엄밀한 정의 ==
조합 최적화 문제의 [[인스턴스]]는 [[튜플]] {{수학|(''X,P,Y,f,''extr)}}로 쓸 수 있다. 여기서 각 기호는 아래와 같은 뜻이다.

* ''X'' - [[문제 공간]] (이 공간상에서 ''f''와 ''P''가 정의된다)
* ''P'' - 유효성을 나타내는 [[술어]]
* ''Y'' - 가능해의 집합
* ''f'' - [[목적 함수]]
* extr - 극단값 (보통 [[최솟값]]이나 [[최댓값]])

== 대표적인 문제 ==
* [[차량 경로 문제]]
* [[외판원 문제]]
* [[최소 비용 걸침 나무]] 문제
* [[선형계획법]] (해의 공간이 어떤 변수를 [[심플렉스법|기본]] 변수로 할 것인지 고르는 것과 같다면)
* [[여덟 퀸 문제]]. ([[제약 만족 문제]]이다. 이러한 문제에 표준 조합 최적화 알고리즘을 적용할 때는 문제 전체가 만족되었는지 여부를 나타내는 불 변수 하나보다는 만족되지 않은 제약 조건의 수를 최적화하는 목적 함수를 주로 사용한다.)
* [[배낭 문제]]

== 방법 ==
아래 열거한 발견 탐색 방법([[메타휴리스틱]] 알고리즘)은 조합 최적화 문제를 푸는 데 흔히 사용된다.
<div style="-moz-column-count:2; column-count:2;">
* [[지역 탐색 (최적화)|지역 탐색]]
* [[담금질 기법]]
* [[양자 담금질]]
* [[탐욕적 확률적 적응형 탐색 절차|GRASP]]
* [[무리 지능]]
* [[타부 탐색]]
* [[유전 알고리즘]]
* [[개미 집단 최적화]]
* [[반응 탐색]]
</div>

== 관련글 ==
* [[이산 최적화]]
* [[탐색 알고리즘]]
* [[전역 탐색]]

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

== 참고 문헌 ==
* Alexander Schrijver; [http://homepages.cwi.nl/~lex/files/dict.pdf ''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, [http://www.nada.kth.se/%7Eviggo/wwwcompendium/ ''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)

== 학술지 ==
* [http://www.kluweronline.com/issn/1382-6905 Journal of Combinatorial Optimization] {{웹아카이브|url=https://web.archive.org/web/20081121193541/http://www.kluweronline.com/issn/1382-6905}}
* [http://www.elsevier.com/locate/disopt Discrete Optimization]

{{전거 통제}}
{{위키데이터 속성 추적}}

[[분류:조합 최적화| ]]
[[분류:계산 복잡도 이론]]
[[분류:알고리즘]]
[[분류:이론 컴퓨터 과학]]