조합최적화

위키백과 ― 우리 모두의 백과사전.

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

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

이 문서는 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.