2. 하나씩 추적하여 해결하기! (백트래킹 알고리즘)
제약만족문제는 어떻게 해결할까요? 여행 짐 싸기의 경우를 생각해봅시다. 이 경우 여러분은 여행 시 필요한 목록을 생각해 볼 겁니다. 문제를 단순화하여 생각해봅시다. 여러분 가방 공간의 크기를 10이라고 해봅시다. 여러분은 물건이 공간을 차지하는 정도를 고려하여 물건을 챙길 수 있습니다.
구분 | 여행 짐 목록 | |||||||||
물품 | 옷 | 화장품 | 세면도구 | 수건 | 속옷 | 컵라면 | 김치 | 신발 | 모자 | 상비약 |
공간차지 | 5 | 3 | 3 | 3 | 2 | 2 | 3 | 4 | 3 | 1 |
위의 표는 짐 목록들과 그에 따른 공간차지와 중요도 정도를 정리한 것입니다. 물론 이 수치는 가정이며 상황에 따라 다를 수 있습니다. 지금은 위의 표와 같이 가정해봅시다. 가방의 크기를 10이라고 가정했기 때문에 여러 가지 조합이 만들어질 수 있습니다. 가령, (옷, 화장품, 컵라면), (수건, 속옷, 컵라면, 세면도구), (모자, 신발, 김치) 등 다양한 조합이 만들어질 수 있습니다. 이 조합을 위한 충족한 조건은 전체 공간의 크기가 10이라는 점이지요. 이 조합들로 여러분은 캐리어에 짐을 꾸릴 수 있습니다.
인공지능은 어떻게 답을 찾아낼 수 있을까요? 인공지능은 가능한 모든 경우의 수를 모두 탐색하여 가능한 답을 모두 찾아냅니다. 아래 그림을 보며 트리구조로 해를 탐색해봅시다.
그다음 화장품을 선택합니다. 화장품이 차지하는 공간이 3이므로 이제 남은 공간은 2가 되었네요. 그리곤 또다시 남은 물품 중에서 가능한 물품을 탐색하게 됩니다.
이제 공간이 2인 물건을 탐색해야 합니다. 일단 먼저 수건이 가능한지 살펴보겠지요. 그러나 수건의 공간은 3이기 때문에 저장 공간인 10을 넘게 됩니다. 그러면 우리가 원하는 답을 얻는데 실패했기 때문에 다른 답을 찾아야겠지요. 그러기 위해서 다시 세면도구로 돌아갑니다. 아래 그림처럼요.
이렇게 다시 돌아가는 과정이 바로 백트래킹(Backtracking)입니다. 세면도구로 다시 돌아간 다음엔 어떻게 할까요? 속옷이 가능하지 다시 살펴보겠지요. 속옷의 공간은 2가 되어 가능하네요. 우리가 원하는 저장 공간인 10이 꽉 채워집니다. 인공지능이 찾은 답은 (옷, 화장품, 세면도구, 속옷)이 됩니다.
그러나 이 답 외에도 많은 답이 있지요. 또 다른 답이 있는지 계속해서 지금과 같은 과정을 반복하게 됩니다. 모든 상황에 대입하여 가능한 답을 모두 찾아내는 것이지요. 이와 같은 백트래킹의 과정은 가능한 해를 샅샅이 찾아낼 수 있다는 점이 있지만 모든 가능성을 확인하게 되어 시간적인 비용이 많이 발생하게 됩니다(그래서 인공지능의 도움이 필요한 것일 수도!).