할당제의 종결 조건(stopping criteria) 을 정의할 수 있을까
최적화와 종결조건 아주 특수한 몇 가지 경우를 제외하면 최적화 문제는 정확한 답을 구하기가 매우 어렵다. 어렵다는 것을 정확하게 정의하긴 힘들지만, 모든 가능한 답안을 적어서 내보고 하나씩 검사해봐야 최적해를 구할 수 있다면 그 문제는 매우 어려운 문제라고 할 수 있다. 예를 들어 숫자의 집합 {3,1,1,2,2,1}이 주어졌을 때, 이것을 합이 같은 두 개의 집합으로 나누는 문제의 답은 {3,1,1}{2,2,1}이 될 것이다. 이 문제는 직접 집합을 두개로 나눠보고 (답안을 적어서 내보고), 두 개의 합이 같은지를 확인 (검사)해야 내가 문제를 잘 풀었는지 알 수 있다. 이런 문제는 숫자가 더 많아지고 더러워질수록 난이도가 기하급수적으로 올라간다. 이를테면, {234,15412,5456,523,42,4..
2021. 6. 24.
