1. 여행을 갈 때 짐을 어떻게 챙겨야 할까?
즐거운 휴가, 기다리던 방학 여러분은 어떻게 보내려고 하나요? 많은 사람들은 휴가기간 동안 이곳저곳 여행 다닙니다. 그럴 때마다 한 번씩 했던 것들… 바로 여행 짐을 싸야 합니다. 이번 여행기간 동안 가는 곳을 이탈리아라고 합시다. 여행 기간은 6월 9일부터 6월 19일까지 10박 11일 코스로 짰습니다. 그 때 이탈리아의 날씨는 꽤나 덥겠네요. 그래도 필요한 옷가지와 화장품, 세면도구, 속옷 등은 기본적으로 준비해야겠지요? 또 사진 찍기를 좋아하는 사람에 따라 사진기, 멋 부리기를 좋아하는 사람들은 신발도 다양하게 준비를 하겠지요. 그런데 문제는 여행을 위해 준비한 캐리어가 하나 밖에 없다는 사실입니다.
나의 캐리어 안 공간에 비해 내가 가지고 가야할 것들은 너무나도 많습니다. 이럴 때 우리가 해야 하는 것은 바로 선택이지요. 주어진 조건에 우리가 맞추어 가장 합리적인 선택을 해야 합니다.
주어진 조건 속에서 우리가 선택해야 하는 것들… 이런 문제를 제약 만족 문제(Constraint Satisfaction Problem:CSP)라고 표현할 수 있습니다. 우리는 이와 같은 문제 상황을 일상생활에서 자주 마주하게 됩니다. 여행 기간 동안에도 많이 마주하게 되네요. 일정한 기간 동안 우리가 짜야할 코스, 정해진 시간 안에 갈 수 있는 대중교통 수단의 선택문제, 비행기가 지연되었을 때 어떤 순서로 비행기를 배치하는 스케쥴링 문제 등 즐거운 여행길에도 수많은 선택의 기로에 놓이게 되네요.
제약 만족 문제에 대해 살펴봅시다. 제약만족문제에서 따져보아야 하는 것은 주어진 제약조건, 이 제약조건을 충족시키기 위해 해답이 될 수 있는 변수 그리고 변수를 채울 수 있는 것들의 집합(정의역)이 도메인입니다. 짐 싸기 문제를 살펴보도록 하지요. 주어진 제약조건은 무엇일까요? 바로 캐리어가 하나라는 점입니다. 또 그 캐리어 안의 공간적인 제약도 있을 수 있겠네요. 그렇다면 변수는 무엇일까요? 변수는 바로 캐리어 안의 공간이라고 볼 수 있습니다. 이 공간 안에는 화장품, 옷, 컵라면 따위의 짐이 들어올 수 있겠네요. 이러한 짐들이 바로 도메인입니다. 짐들 중에는 선택되는 것들도 있고, 선택되지 않는 것들도 있겠네요. 제약만족문제는 도메인들을 변수에 넣어서 주어진 조건에 맞는 답을 구하는 것을 목표로 합니다. 위와 같은 상황에서는 캐리어 하나(제약조건)의 공간(변수)에 여러 짐들(도메인)을 넣어서 최적의 여행 짐을 쌓는 것이 목표라고 보면 되겠네요.
2. 하나씩 추적하여 해결하기! (백트래킹 알고리즘)
제약만족문제는 어떻게 해결할까요? 여행 짐 싸기의 경우를 생각해봅시다. 이 경우 여러분은 여행 시 필요한 목록을 생각해 볼 겁니다. 문제를 단순화하여 생각해봅시다. 여러분 가방 공간의 크기를 10이라고 해봅시다. 여러분은 물건이 공간을 차지하는 정도를 고려하여 물건을 챙길 수 있습니다.
구분 | 여행 짐 목록 | |||||||||
물품 | 옷 | 화장품 | 세면도구 | 수건 | 속옷 | 컵라면 | 김치 | 신발 | 모자 | 상비약 |
공간차지 | 5 | 3 | 3 | 3 | 2 | 2 | 3 | 4 | 3 | 1 |
위의 표는 짐 목록들과 그에 따른 공간차지와 중요도 정도를 정리한 것입니다. 물론 이 수치는 가정이며 상황에 따라 다를 수 있습니다. 지금은 위의 표와 같이 가정해봅시다. 가방의 크기를 10이라고 가정했기 때문에 여러 가지 조합이 만들어질 수 있습니다. 가령, (옷, 화장품, 컵라면), (수건, 속옷, 컵라면, 세면도구), (모자, 신발, 김치) 등 다양한 조합이 만들어질 수 있습니다. 이 조합이 충족시킨 조건은 전체 공간의 크기가 10이라는 점이지요. 이 조합들로 여러분은 캐리어에 짐을 꾸릴 수 있습니다.
인공지능은 어떻게 답을 찾아낼 수 있을까요? 인공지능은 가능한 모든 경우의 수를 모두 탐색하여 가능한 답을 모두 찾아냅니다. 아래 그림을 보며 트리구조로 해를 탐색해봅시다.
인공지능은 일단 위 그림처럼 옷을 선택합니다. 그리곤 가능한 물건을 또 탐색하겠지요. 옷의 공간이 5이니 이제 남은 공간은 5가 되겠네요. 그러면 5의 공간에서 가능한 물품을 또 탐색하게 됩니다.
그다음 화장품을 선택합니다. 화장품이 차지하는 공간이 3이므로 이제 남은 공간은 2가 되었네요. 그리곤 또다시 남은 물품 중에서 가능한 물품을 탐색하게 됩니다.
이제 공간이 2인 물건을 탐색해야 합니다. 일단 먼저 수건이 가능한지 살펴보겠지요. 그러나 수건의 공간은 3이기 때문에 저장 공간인 10을 넘게 됩니다. 그러면 우리가 원하는 답을 얻는데 실패했기 때문에 다른 답을 찾아야겠지요. 그러기 위해서 다시 세면도구로 돌아갑니다. 아래 그림처럼요.
이렇게 다시 돌아가는 과정이 바로 백트래킹(Backtracking)입니다. 세면도구로 다시 돌아간 다음엔 어떻게 할까요? 속옷이 가능하지 다시 살펴보겠지요. 속옷의 공간은 2가 되어 가능하네요. 우리가 원하는 저장 공간인 10이 꽉 채워집니다. 인공지능이 찾은 답은 (옷, 화장품, 세면도구, 속옷)이 됩니다.
그러나 이 답 외에도 많은 답이 있지요. 또 다른 답이 있는지 계속해서 지금과 같은 과정을 반복하게 됩니다. 모든 상황에 대입하여 가능한 답을 모두 찾아내는 것이지요. 이와 같은 백트래킹의 과정은 가능한 해를 샅샅이 찾아낼 수 있다는 점이 있지만 모든 가능성을 확인하게 되어 시간적인 비용이 많이 발생하게 됩니다(그래서 인공지능의 도움이 필요한 것일 수도!).
3. 대표적인 제약 만족 문제 N-Queen 문제
대표적인 제약만족문제로 N-QUEEN 문제가 있습니다. N×N 판에 N개의 퀸을 배치하는 문제이죠.
제약조건은 어떤 자리의 가로, 세로, 대각선 방향에 퀸이 있다면 그 자리에는 퀸을 둘 수 없다는 점입니다. 아래 그림은 4×4 퀸 문제의 해입니다.
위의 그림을 각 퀸의 관점에서 봅시다.
각 퀸의 가로, 세로, 대각선에는 다른 퀸이 위치하지 않죠. 그러므로 제약조건에 적합한 해를 찾았다고 볼 수 있습니다. N퀸 문제는 백트래킹 알고리즘을 사용하여 해를 찾을 수 있습니다.
문제를 해결하기 위해 N퀸 문제를 모델링해봅시다.
N퀸 문제는 (x1, x2, x3, … ,xn)을 구하는 문제라고 볼 수 있습니다.
퀸은 한 행에 한 개만 배치할 수 있습니다. 그러므로 각 행에 오는 퀸의 위치(x)를 (x1, x2, x3, … ,xn)과 같이 행열로 나타낼 수 있습니다. 왼쪽 그림의 경우 (3, 1, 4, 2)로 표현할 수 있습니다.
4퀸 문제의 해답을 구하는 과정을 백트래킹 알고리즘을 사용하여 알아봅시다.
1행의 1열에 퀸이 올 경우 2행에는 3열 또는 4열에 퀸이 올 수 있습니다.
먼저 2행 3열에 퀸을 배치해 봅시다. 그러면 다음 그림과 같이 3행에 퀸을 배치할 자리가 없게 되어 해를 구할 수 없게 됩니다.
그렇다면 어떻게 해야할까요? 백트래킹해서 위로 올라가 2행의 4열이 가능한 지를 판단하게 되겠지요. 그러나 2행에 4열을 추적하면 (1, 4, 2, ?)까지는 추적이 가능하나 4행에 올 수 있는 퀸의 자리가 없습니다. 그러므로 1행 1열에는 퀸이 올 수 없다는 결론을 얻게 됩니다.
다시 백트래킹 하여 1행 2열부터 추적을 시작합니다. 그 추적 결과를 상태공간트리로 나타내면 다음과 같습니다.
4×4 퀸의 문제의 해는 (2, 4, 1, 3)과 (3, 1, 4, 2)를 얻을 수 있습니다.
4×4 퀸 문제의 경우 해가 2개 뿐이기 때문에 쉽게 구할 수 있습니다. 그러나 N의 수가 점점 커지면 어떻게 될까요? N의 수에 따른 N퀸 문제의 해답은 다음과 같습니다.
N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … | 24 |
해의 수 | 1 | 0 | 0 | 1 | 2 | 1 | 6 | 12 | 46 | 92 | … | 28,439,272,956,934 |
해의 수 (대칭구별) | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | … | 227,514,171,973,736 |
N의 수가 증가함에 따라 해를 찾는데 소요되는 시간이 굉장히 늘어나겠군요.
4. N-Queen 문제 시뮬레이션
N퀸 문제의 조건을 달리하여 N퀸 문제를 해결해보고, N퀸 문제를 백트래킹으로 해결하는 과정을 체험해보세요!
퀸 대신 파란 공이 등장합니다. 공이 알맞은 위치에 놓였다면 경쾌한 소리와 함께 공이 반짝 빛납니다. 조건을 모두 만족하는 답을 찾았더라고 컴퓨터는 계속해서 탐색을 이어 나가며, 탐색을 마친 후에는 조건을 만족하는 답이 모두 몇 개 인지 알려줍니다.
퀴즈
제약 만족 문제에서는 주어진 조건과 변수에 따라 다양한 해답이 존재할 수 있다.
조건이 달라지므로 다양한 답이 존재한다.
다음 중 옳지 않은 것을 고르세요.
백트래킹은 오답을 만나더라도 계속해서 탐색을 이어간다.
N 퀸 문제에 대한 설명으로 맞는 것을 3가지 고르세요.
Please select 3 correct answers