Graph Coloring with ILP
오늘 랩미팅에서의 이슈를 한글로 정리해서 올린당.
ILP는 Exhausted Search를 한다.
즉 모든 경우를 하나하나 따진다는 것인데 이렇게 하면
Search Space가 커질 수록 실행 시간도 크게 늘어나므로,
Constraint를 잘 주어야 할 거 같다.
ILP가 이렇게 고생해서 얻은 답은 '정답' 이다.
이 정확한 값 하나를 얻기 위해서 오랜시간 값을 구한 것인데..
사실 이렇게 정확한 값 까지는 필요없고 대충 근사값만 있어도 좋을 때가 있다.
이럴 때 Heuristic Algorithm을 쓰는데,
Genetic Algorithm 이라든가... 정확한 참값까지는 필요치 않을때 사용한다.
나중엔 GA 정리를 해놔야겠다...
댓글남기기