모델 정의

 우리가 당면한 다양한 문제들을 푸는 데에 있어서 중요한 것은 문제를 분석하고 정의하는 것이다.

 내가 눈 앞에 있는 문제에서 어떠한 값을 알고 싶은지, 어떻게 구할 것인지, 구한 값이 적절한지 구하는 척도가 있어야 정확히 문제를 풀 수 있을 것이다.

Model Definition

Problem -> Model -> Solution

 이전 포스팅에서 문제의 난이도(complexity) 등 문제와 관련된 정의를 알아보았다. 이번 포스팅에서는 문제를 푸는 모델을 어떻게 정의 해야하는 가에 대해서 다루어 보겠다.

 우선 우리는 문제의 Solution을 찾아내기를 원한다. 이때 Solution 중 Feasible Solution을 찾기를 바랄 것이다. Feasible Solution이란 문제별 제약 조건을 충족하는 솔루션을 뜻한다. 여기서 제약 조건을 충족하는 솔루션이라고 말했는 데 솔루션은 항상 정답만 뜻하는 것은 아니기 때문이다. 오답도 Solution의 범주안에 들어간다. 따라서 우리는 소위말해서 정답을 찾으려고 할 것이다. (정확히는 정답이라는 표현도 틀린 표현이고 Optimal한 Solution이 정확한 표현이다.) 예를 들어 TSP 문제에서 모든 노드를 안거치는 Path는 틀린 Solution이라고 할 수 있지만 Feasible Solution이라고 할 수 없다. 모든 노드를 거치는 Path가 TSP문제의 Feasible Solution이 될 것이며 Path의 길이가 가장 짧은 Solution이 optimal한 Solution이 될 것이다.

 그렇다면 Feasible Solution을 구하기 위한 모델은 어떻게 정의 해야할까? 바로 3가지를 정의해야한다. TSP문제를 예시로 들어보자.

1. Representation

 문제에 대한 Solution을 어떻게 표시할 것인가? ex) 노드의 list

2. Objective Function

 문제에 대한 Solution을 어떻게 계산할지에 대한 수학적인 수식 ex) min ådist(x,y)

3. Evaluation Function

 구한 Solution이 적절한지 어떻게 평가할 것인가? ex) 구한 노드의 dist를 다 더한다.

위의 3가지 중 가장 중요한 것은 Objective Function이다. Objective Function은 실제로 Solution을 찾는 과정이기 때문에 잘 정의해야 좋은 Solution을 찾을 수 있을 것이다.