컴퓨터는 공간을 탐색하여 문제의 해를 찾습니다.(미로에서 목표 상태로 가는 길 찾기 문제를 떠올려 보세요.) 복잡도가 크면 문제를 해결하는 데 오랜 시간과 노력이 들 것입니다. 복잡도를 줄이기 위해 컴퓨터는 여러 가지 탐색 방법(탐색 알고리즘)을 활용합니다.
우리 주변의 문제는 대부분 복잡도가 큽니다. 때문에 일상적인 문제로 컴퓨터의 탐색 방법을 이해하려면 머리가 지끈지끈 아파올 것 같습니다. 그래서 컴퓨터 과학자들은 이해를 돕기 위하여 8퍼즐, 틱텍토와 같이 쉽고 간단한 문제를 만들어서 탐색 방법을 설명하고 있습니다. 그 중 첫 번째로, 로봇의 눈을 통해 블라인드 탐색 방법을 알아보겠습니다.
1. 로봇의 눈으로 길을 찾아볼까요?
여러분이 로봇이 되었다고 상상하여 보세요. 여러분은 지금 아래 그림과 같이 어두운 미로 속 공간에 있습니다. 가운데의 파란 점이 바로 로봇인 여러분입니다. 문제는 ‘미로에서 목적지●를 찾는 것’이고, 이 공간을 탐색하여 목적지에 도착해야 합니다.
사람은 눈을 통해 목적지와 장애물을 보고 직관적으로 경로를 찾을 수 있지만 로봇에게는 눈이 없지요. 대신 센서나 카메라를 활용하여 앞에 장애물이 있는 지 확인합니다. 길이 어떻게 생겼는지 또 목적지가 어느 방향에 있는지 알지 못하는 여러분은 당장 눈, 아니 센서 앞에 있는 길밖에 보이지 않네요. 초기 상태에서 여러분이 갈 수 있는 길은 위, 왼쪽, 오른쪽, 아래의 길입니다. 이 상태에서 길 찾기 문제를 해결하여 봅시다!
아래의 스크래치 프로그램으로 ‘로봇의 눈으로 길 찾기’를 해보세요. ‘시작하기’ 버튼으로 시작할 수 있고 방향키로 움직일 수 있습니다.
2. 블라인드 탐색은 무엇인가요?
컴퓨터도 깜깜한 미로 속 로봇과 마찬가지입니다. 공간을 탐색하다가 더 나아갈 곳이 없으면 전에 왔던 곳으로 되돌아 갑니다. 되돌아 간 후에는 가보지 않은 길을 탐색합니다. 컴퓨터는 이 과정을 계속 반복하면서 길을 찾게 됩니다. 이러한 탐색 방법을 ‘블라인드 탐색’이라고 합니다.
‘블라인드 탐색(Blind Search)’은 어떠한 정보나 힌트 없이 차례대로 탐색하는 방법입니다.
‘로봇의 눈으로 길 찾기’ 문제에서처럼 컴퓨터는 목적지가 어디인지, 길이 어디로 향하는지 등의 사전 정보 없이 목적지를 찾을 때까지 모든 길을 탐색해 봅니다. 따라서 맹목적 탐색이라고 부르기도 합니다.
이제 간단한 길 찾기 문제에서 목표 상태에 도달할 때까지 컴퓨터의 탐색 방법을 차근차근 따라가 보려고 합니다. 그런데 미로가 복잡해서 한 눈에 정리하기 쉽지 않네요. 컴퓨터도 마찬가지겠지요? 컴퓨터가 이해하기 쉽도록 길을 정리해 주어야 겠습니다.
3. 복잡한 길을 탐색 트리로 정리해볼까요?
공간을 탐색할 때 공간이 너무 복잡하면 시간도 많이 걸리고 컴퓨터가 기억하는 데도 어려움이 있습니다. 그래서 컴퓨터가 이해하기 쉽게 길을 정리해주곤 합니다. 이처럼 컴퓨터에서 자료를 효율적으로 정리한 것을 자료 구조라고 합니다. 앞서 살펴보았던 그림에서 미로 속 길을 한 눈에 이해할 수 있도록 정리하여 다양한 자료 구조라고 표현할 수 있습니다. 구슬을 꿴 줄처럼 생긴 구조도 있고, 그물 모양의 자료 구조도 있습니다. 어떤 문제인지에 따라서 적당한 자료 구조를 선택하여 활용합니다. 그 중에서도 다음의 그래프처럼 표현한 것을 ‘탐색 트리(Search Tree)’라고 합니다. 마치 나무를 거꾸로 세운 것 같지요?
4. 어느 방향으로 탐색할까요? - 깊이 우선 탐색과 너비 우선 탐색
이제 자료도 보기 쉽게 정리 했으니 블라인드 탐색을 해 볼까요? 우리가 로봇의 눈으로 길 찾기를 할 때에는 정해진 순서가 없었지만 컴퓨터는 정해진 순서, 즉 규칙에 따라 탐색을 합니다. 규칙이 무엇인지에 따라 다양한 탐색 방법이 있습니다. 특히 탐색 트리에서는 어느 방향으로 탐색하느냐에 따라 종류가 다양합니다. 여기서는 ‘깊이 우선 탐색’과 ‘너비 우선 탐색’만 알아보도록 하겠습니다.
왼쪽의 아주 간단한 미로에서 갈림 길과 막 다른 길을 숫자로 표현하여 탐색하기 좋은 자료 구조로 만든다면 오른쪽과 탐색 트리와 같이 만들 수 있습니다.
‘깊이 우선 탐색’은 시작점에서 ‘깊이 방향’으로 탐색하는 것입니다. 왼쪽에 있는 것부터 탐색을 한다고 했을 때, 목적지가 ❺라고 한다면 ‘❶-❸-❹-❷-❺’ 순서로 탐색하는 것입니다. 손가락으로 하나하나 짚어보며 다음 길을 따라가 보세요. 먼저 출발지에서 갈림길 ❶까지 갑니다. 글씨를 읽을 때 처럼 왼쪽부터 탐색한다면 ❶에서 ❸으로 갑니다. ❸은 길이 막혀 있어 더이상 탐색할 수 가 없네요. 그러면 다시 ❶로 돌아간 후, 아직 가보지 않은 ❹를 갑니다. ❹에서도 더 탐색할 곳이 없으면 다시 돌아갑니다. ❶에서 갈 수 있는 길은 모두 가보았으므로 출발지로 돌아가서 ❷로 갑니다. ❷에서 갈 수 있는 곳은 ❺ 하나뿐입니다. ❺를 탐색하였더니 목표상태에 도달했습니다!
‘너비 우선 탐색’은 ‘너비 방향’으로 탐색하는 것입니다. 시작점에서 갈 수 있는 길을 모두 가본 후, 다음 갈림길을 방문하는 예로 생각할 수 있습니다. 예를 들어 목적지가 ❺라면, ‘❶-❷-❸-❹-❺’ 순서로 탐색하는 것입니다. 마찬가지로 손가락으로 짚어보며 길을 따라가 보세요. 너비 방향이란 가로 방향입니다. 보통 왼쪽에서 오른쪽으로 탐색합니다. 그러므로 가장 먼저 방문할 곳은 ❶입니다. ❶을 탐색하였더니 목표 상태가 아니네요. 그러면 다시 출발지로 돌아가 ❷를 탐색합니다. 아직 문제가 해결되지 않았으므로 이번에는 ❶과 ❷보다 더 깊은 곳을 탐색해보겠습니다. 마찬가지로 너비 방향으로 탐색합니다. 다시 ❶로 돌아가 ❸을 탐색합니다. ❸에서도 문제가 해결되지 않으면 ❶로 돌아간 후 ❹를 갑니다. ❹도 목표 상태가 아니므로 초기 상태(출발지)로 돌아갑니다. 이번에는 ❷에서 다음 깊이로 가보겠습니다. ❷에서 갈 수 있는 길은 ❺입니다. ❺를 탐색하였더니 목표상태에 도달했습니다!
어떤 문제인지에 따라 깊이 우선 탐색이 필요할 수도 있고, 때로는 너비 우선 탐색이 필요할 수도 있습니다. 두 가지 방법의 장점만 취한 또 다른 방법을 사용하기도 합니다.
5. 블라인드 탐색 방법은 일상의 문제를 해결하기에 유용할까요?
다시 ‘로봇의 눈으로 길 찾기’ 문제로 돌아가서 생각해 봅시다. 미로를 어떠한 규칙에 따라 탐색한다고 할 때, 블라인드 탐색 방법이 유용할까요? 블라인드 탐색은 모든 길을 돌아보느라 탐색 시간이 오래 걸리더라도 가장 빠르게 탈출하는 길을 찾아 줄 것입니다. 일상의 문제들 중에서도 블라인드 탐색 방법이 유용하게 쓰일 수 있는 것들이 있을 수 있겠지요. 하지만 만약 조금 더 복잡한 미로라면 어떨까요? 모든 경로를 돌아보는 것은 시간이 너무 많이 걸릴뿐더러 운도 상당히 좋아야 할 것 같습니다. 운이 좋으면 목적지에 빨리 도달할 수 있고 그렇지 않다면 더 많은 시간과 노력이 필요할 것입니다. 또 다녀온 길과 아직 가보지 않은 길을 기억하려면 머리에 쥐가 나겠지요? 즉, 미로보다 더 복잡한 현실 세계의 문제를 해결하기에 어떠한 정보나 힌트도 없이 탐색하는 블라인드 탐색은 효율성이 떨어집니다.
Think Good AI
인공지능을 이용하여 길을 찾는 네비게이션을 적용하였다. 빨리 가는 방법을 선호하는 사람의 특징을 파악하여 대부분의 경로를 빠른 길로 안내할 때 발생할 수 있는 문제는 무엇인가?
– 빨리 가는 경로로 낭떠러지와 같이 위험한 산을 통과하게 안내하는 경우
– 5분정도 빨리 가기 위해 통행료를 과하게 징수하는 길을 안내하는 경우
퀴즈
블라인드 탐색은 맹목적 탐색이라고도 하며, 사전 정보를 이용하지 않는다.
블라인드 탐색은 규칙 없이 탐색하여 시행착오를 겪으면서 문제의 해를 찾는 것이다.
정해진 순서에 따라 탐색하며, 순서에 따라 종류도 다양하다.
블라인드 탐색은 바둑이나 체스 같은 복잡한 게임의 수를 찾기에 적합하다.
- 블라인드 탐색은 효율성이 떨어져 실제 문제에 적용하기 어렵다.
다음 트리를 ‘깊이 우선 탐색’으로 탐색한다면 ❶-❸-❹-❷-❺-❼ 순서로 탐색하는 것이다.(단, 왼쪽부터 탐색한다고 한다.)
깊이 우선 탐색은 깊이 방향을 우선으로 탐색하는 것이다.
Think Good AI
인공지능을 이용하여 길을 찾는 네비게이션을 적용하였다. 빨리 가는 방법을 선호하는 사람의 특징을 파악하여 대부분의 경로를 빠른 길로 안내할 때 발생할 수 있는 문제는 무엇인가?(수정요망)
– 빨리 가는 경로로 낭떠러지와 같이 위험한 산을 통과하게 안내하는 경우
– 5분정도 빨리 가기 위해 통행료를 과하게 징수하는 길을 안내하는 경우
참고문헌
1. 이건명, 「인공지능 튜링테스트에서 딥러닝까지」, 생능출판(2018)
2. 미래인재연구소, 초등학교 STEAM 교사용 교재 ‘로봇의 눈으로 길찾기’, 한국과학창의재단(2019)