지능적 탐색

지능적 탐색이란 무엇인가

트리를 다 확장할 수 없다면, 어디부터 살펴봐야 할까?

「무엇을 먼저 볼지 정하는 방법」이 왜 필요한지부터 살펴봅시다.

지도를 그렸다면 이제 길을 고른다

탐색으로 문제를 풀려면 먼저 문제를 상태 · 초기 상태 · 목표 상태 · 연산자 · 경로 비용 다섯 가지로 다시 써서 상태 공간 트리를 만듭니다. 여기까지는 지도를 그린 것에 해당합니다.

그런데 지도를 그렸다고 길이 저절로 찾아지지는 않습니다. 트리에는 아직 확장하지 않은 노드가 여러 개 쌓여 있고, 인공지능은 매번 「이 중에서 어느 것을 다음에 확장할까?」를 정해야 합니다. 여기서 다룰 것이 바로 그 고르는 방법입니다.

고르는 방법이 왜 중요한지는 바둑을 보면 알 수 있습니다. 바둑에서 나올 수 있는 판의 경우의 수는 우주에 있는 원자의 수보다 많다고 이야기할 정도입니다. 모든 가지를 끝까지 확장해 보는 일은 아무리 빠른 컴퓨터로도 불가능합니다. 그러니 어느 가지를 먼저 볼지, 어느 가지는 아예 보지 않을지를 정하는 것이 승부를 결정합니다.

지능적 탐색(intelligent search)

상태 공간 트리에서 다음에 확장할 노드를 정해진 원칙에 따라 골라 가며 목표 상태에 이르는 경로를 찾는 것을 말합니다. 아무렇게나 뒤적이지 않고, 고르는 원칙이 분명히 정해져 있다는 점에서 「지능적」이라고 부릅니다.

그 원칙을 어디에서 가져오느냐에 따라 지능적 탐색은 두 갈래로 나뉩니다. 문제에 대한 사전 정보를 쓰지 않고 정해진 순서만 따르면 맹목적 탐색, 목표까지 얼마나 남았는지를 어림한 정보를 함께 쓰면 정보 이용 탐색입니다.

오른쪽 끝 네 가지는 각 갈래의 대표적인 방법입니다. 이름을 지금 다 외울 필요는 없습니다. 지금은 두 갈래가 무엇이 다른지만 확실히 잡으면 충분합니다.

「지능적」이라는 말에 속지 말 것

맹목적 탐색도 지능적 탐색의 한 갈래입니다. 위 그림에서 둘 다 같은 상자 밑에 달려 있습니다. 「지능적」은 성능이 좋다는 뜻이 아니라, 노드를 고르는 원칙이 정해져 있어 같은 문제를 다시 풀어도 같은 방식으로 움직인다는 뜻입니다.

마찬가지로 「맹목적」도 어리석다는 뜻이 아닙니다. 목표가 어느 쪽에 있는지 알려 주는 정보를 쓰지 않는다는 뜻일 뿐입니다. 뒤에서 보겠지만, 정보가 아예 없는 상황에서는 맹목적 탐색이 유일하게 쓸 수 있는 방법이고, 조건이 맞으면 가장 짧은 경로를 확실히 보장하기도 합니다.

스스로 확인

친구가 「정보 이용 탐색은 지능적이고, 맹목적 탐색은 지능적이지 않다」고 말했습니다. 이 말은 어디가 틀렸을까요?

두 갈래를 하나씩 살펴보기

단서를 쓰는 탐색과 쓰지 않는 탐색은 무엇이 다를까?

두 갈래가 각각 무엇을 얻고 무엇을 내주는지 살펴봅시다.

방법 1

맹목적 탐색 (무정보 탐색)

Blind Search / Uninformed Search

목표가 어느 쪽에 있는지 알려 주는 사전 정보를 쓰지 않고, 정해진 순서만 따라 노드를 하나씩 확장하는 방법입니다. 쓸 정보가 없으니 모든 방향을 똑같이 대접할 수밖에 없습니다.

비유: 처음 가 보는 대형 마트에서 안내도도 없이 물건을 찾을 때, 입구부터 진열대를 차례대로 살펴보는 것과 같습니다. 어느 쪽에 있는지 알 방법이 없으니 순서를 정해 놓고 도는 것입니다.
대가: 목표와 정반대 방향까지 똑같이 확장하므로 경우의 수가 많아지면 시간과 메모리가 감당하기 어려워집니다.

순서를 어떻게 정하느냐에 따라 두 가지

너비 우선 탐색(BFS) — 루트에서 가까운 노드부터, 같은 깊이를 다 확장한 뒤 한 단계 더 내려갑니다. 물결이 퍼지는 모양이 됩니다.

깊이 우선 탐색(DFS) — 한 가지를 잡으면 끝까지 내려갑니다. 막다른 곳에 닿으면 갈림길로 되돌아와 다른 쪽으로 다시 내려갑니다.

무엇을 보장하고 무엇을 보장하지 않나

둘 다 상태의 수가 유한하고, 이미 본 상태를 다시 확장하지 않는다면 답이 있는 한 언젠가는 찾아냅니다.
너비 우선 탐색은 가장 짧은 경로를 보장합니다 — 단, 간선 하나의 비용이 모두 같을 때만입니다. 구간마다 걸리는 시간이 다른 도로처럼 비용이 제각각이면 이 보장은 사라집니다.
깊이 우선 탐색은 가장 짧은 경로를 보장하지 않습니다. 먼저 잡은 가지 끝에서 목표를 만나면 그대로 답이 되므로, 훨씬 짧은 길을 옆에 두고도 지나칠 수 있습니다. 대신 지금 내려온 한 줄만 기억하면 되어 메모리를 훨씬 적게 씁니다.

방법 2

정보 이용 탐색 (휴리스틱 탐색)

Informed Search / Heuristic Search

문제에 대해 미리 알고 있는 것을 이용해 「이 상태는 목표에 얼마나 가까울까」를 어림한 값을 계산하고, 그 값이 좋은 노드부터 먼저 확장하는 방법입니다.

비유: 같은 마트라도 「라면은 과자 근처에 있을 것」이라고 짐작하고 그 구역부터 가 보는 것입니다. 확실히 아는 것이 아니라 짐작이라는 점이 중요합니다.
얻는 것: 목표와 반대쪽은 뒤로 미루어 거의 확장하지 않으므로 확장하는 노드 수가 크게 줄고, 복잡한 문제에서 탐색 시간을 많이 아낄 수 있습니다.
내주는 것: 어림값은 틀릴 수 있습니다. 그래서 빨리 찾더라도 그것이 가장 좋은 답이라는 보장은 없습니다.

어림값을 얼마나 믿느냐에 따라 두 가지

최상 우선 탐색 — 남은 거리의 어림값만 보고 가장 좋아 보이는 노드부터 확장합니다. 빠르지만, 지금까지 온 길이 얼마나 멀었는지는 고려하지 않으므로 돌아가는 길을 답으로 내놓기 쉽습니다.

A* 알고리즘 — 지금까지 온 비용 + 남은 거리의 어림값을 더해서 고릅니다. 어림값이 실제 남은 거리를 넘겨 잡지 않는다는 조건이 지켜지면 가장 짧은 경로를 보장합니다. 대신 계산할 것이 늘어납니다.

휴리스틱(heuristic)이란?

정확한 답을 계산하기에는 시간이나 정보가 모자랄 때, 경험을 바탕으로 빠르게 추정하는 방법을 가리키는 말입니다. 「찾아내다」라는 뜻의 그리스어에서 온 말로, 우리말로는 어림짐작이라고 옮길 수 있습니다.

탐색에서 휴리스틱은 평가 함수의 모습으로 쓰입니다. 평가 함수란 후보로 올라와 있는 노드 가운데 어느 것을 다음에 확장할지 정하려고 노드마다 매기는 점수입니다. 휴리스틱을 넣어 만든 평가 함수는 그 노드가 목표에 얼마나 가까운지를 어림한 숫자를 점수에 넣습니다. 최상 우선 탐색은 이 어림값만 점수로 쓰고, A*는 지금까지 온 비용에 이 어림값을 더해 점수로 씁니다. 여기서 다루는 평가 함수는 점수가 작을수록 좋다고 보고 그 노드부터 먼저 확장합니다.

여기서 꼭 기억할 점이 있습니다. 평가 함수에 들어가는 휴리스틱 값은 실제 남은 거리가 아니라 추정값입니다. 정답을 미리 알고 있다면 애초에 탐색을 할 필요가 없습니다. 추정이기 때문에 빠르고, 추정이기 때문에 틀릴 수 있습니다.

같은 문제에도 휴리스틱은 여러 가지로 잡을 수 있다

거리로 추정하기

지금 위치에서 목적지까지의 직선거리를 계산한다. 계산이 아주 간단하다. 대신 사이에 강이나 산이 있어도 그 사실을 모른다.

시간으로 추정하기

각 길의 예상 소요 시간을 쓴다. 교통 상황과 신호까지 반영되어 더 현실에 가깝지만, 그만큼 계산할 것이 많고 예측이 빗나가기도 한다.

8-퍼즐(3×3 판에서 타일을 빈칸으로 밀어 목표 배치를 만드는 퍼즐)에서는 제자리에 있지 않은 타일의 개수를 휴리스틱으로 쓸 수 있습니다. 타일이 많이 어긋나 있을수록 목표에서 멀다고 보는 것입니다. 어떤 값을 휴리스틱으로 잡을지는 문제를 아는 사람이 직접 설계합니다. 정보 이용 탐색이 얼마나 잘 작동하는지는 휴리스틱을 얼마나 잘 설계하느냐에 크게 달려 있습니다.

스스로 확인

구간마다 걸리는 시간이 다른 도로 지도에서 너비 우선 탐색으로 길을 찾았습니다. 이 길을 「가장 빨리 가는 길」이라고 말할 수 있을까요? 그렇게 답한 까닭도 말해 보세요.

같은 지도, 두 가지 탐색

두 방법을 같은 문제에 걸어 보면 무엇이 다를까?

말이 아니라 움직이는 화면으로 차이를 확인해 봅시다.

같은 문제를 두 가지 방법으로 풀어 보기

말로만 들으면 두 방법의 차이가 잘 와닿지 않습니다. 똑같은 지도를 놓고 두 탐색을 나란히 실행해 보면 차이가 한눈에 보입니다. 왼쪽 S에서 오른쪽 G까지 가는데, 가운데에 벽이 있고 위·아래로 돌아가는 틈이 있습니다.

왼쪽 · 맹목적 탐색 (너비 우선)

어느 칸이 목표에 가까운지 전혀 모릅니다. 그래서 지금까지 찾은 칸 중 먼저 발견한 순서대로 하나씩 확장합니다. 결과적으로 물결처럼 사방으로 고르게 퍼집니다.

오른쪽 · 정보 이용 탐색 (휴리스틱)

각 칸에서 목표까지 남은 거리를 어림한 값 h를 계산할 수 있습니다. h는 목표까지의 가로 칸 수와 세로 칸 수를 더한 값입니다. 그래서 h가 가장 작은 칸부터 확장합니다. 결과적으로 목표 쪽으로 곧장 뻗어 갑니다.

맹목적 탐색 (너비 우선)

확장한 칸 0개

정보 이용 탐색 (휴리스틱)

확장한 칸 0개

확장한 칸 발견했지만 아직 안 확장한 칸 벽

구분	맹목적 탐색	정보 이용 탐색
공통점	둘 다 상태 공간 트리를 만들며, 초기 상태에서 시작해 연산자를 적용해 자식 노드를 확장한다.
다음에 확장할 노드를 고르는 기준	발견한 순서(너비 우선은 먼저 찾은 것부터, 깊이 우선은 가장 나중에 찾은 것부터)	휴리스틱 값 h(n)을 넣은 평가 함수 값이 가장 좋은 것부터
문제에 대한 추가 정보	쓰지 않는다	「목표까지 얼마나 남았나」를 어림한 값을 쓴다
확장하는 모양	사방으로 고르게 퍼진다	대체로 목표 방향으로 좁고 길게 뻗는다
답을 찾아내는가	상태의 수가 유한하고 이미 본 상태를 다시 확장하지 않는다면, 답이 있는 한 찾아낸다	대체로 훨씬 빨리 찾지만, 어림값이 크게 어긋나면 헤맬 수 있다
찾은 답이 가장 짧은가	너비 우선은 간선 비용이 모두 같을 때 보장한다. 깊이 우선은 보장하지 않는다	보장하지 않는다. 단 A처럼 어림값이 실제보다 크지 않게* 설계하면 보장할 수 있다
주로 드는 비용	확장하는 노드 수가 많아 시간과 메모리를 많이 쓴다	좋은 휴리스틱을 사람이 설계해야 하고, 매 단계 평가 함수를 계산해야 한다
언제 쓰나	목표가 어디인지 짐작할 단서가 아예 없을 때	문제를 잘 알고 있어 쓸 만한 어림값을 만들 수 있을 때

주목할 점 하나: 오른쪽도 벽에 부딪히면 잠깐 멈칫합니다. 휴리스틱은 벽이 있다는 사실을 모른 채 가로·세로 칸 수만 보고 추정하기 때문입니다. 「정보를 쓴다」는 말이 「정답을 안다」는 뜻은 아니라는 점을 기억하세요.

주목할 점 둘: 여기서 비교한 것은 얼마나 적게 확장했는가일 뿐, 어느 쪽 답이 더 짧은가가 아닙니다. 이 지도는 한 칸 이동의 비용이 모두 같아서 왼쪽(너비 우선)이 찾은 경로는 가장 짧은 경로임이 보장됩니다. 오른쪽은 빨리 도착했지만 그 길이 가장 짧다는 보장은 없습니다. 빠른 것과 좋은 답은 다른 이야기입니다.

스스로 확인

가운데 벽을 없앤 빈 지도라면, 두 방법이 확장하는 칸 수의 차이는 더 커질까요, 줄어들까요? 휴리스틱이 무엇을 모르는지에 비추어 답해 보세요.

두 방법을 직접 비교해 보기

어느 쪽이 늘 낫다고 말할 수 있을까?

탐구활동 · 여행 계획으로 비교하는 두 가지 탐색

모둠을 나누어 하루 동안 다녀올 여행 계획을 세워 보자. 한 모둠은 맹목적 탐색으로, 다른 모둠은 정보 이용 탐색으로 방문 순서를 정해 비교해 본다.

① 맹목적 탐색으로 계획하기

지역 관광 지도만 보고, 정보 없이 정해 둔 순서대로 모든 권역을 하나씩 방문하는 당일치기 계획을 세운다.

② 정보 이용 탐색으로 계획하기

인터넷에서 각 관광지의 인기도·소요 시간 등 정보를 미리 찾아본 뒤, 이를 근거(휴리스틱)로 방문 순서를 정한다.

계획을 다 세웠으면, 아래 표의 빈칸에 직접 적어 두 방법을 비교해 보세요. 어느 한쪽이 늘 낫다는 결론이 나오지 않아도 됩니다. 그것이 오히려 정확한 결론입니다. (적은 내용은 저장되지 않으니, 남겨야 한다면 따로 옮겨 적으세요.)

비교할 것	맹목적 탐색으로 짠 계획	정보 이용 탐색으로 짠 계획
계획을 짜는 데 든 시간
빠뜨린 곳은 없었나
이동한 총 거리
미리 알아야 했던 정보

생각해 보기 1: 정보 이용 탐색으로 짠 계획은 무엇을 미리 알고 있어야 가능했나요? 그 정보가 없거나 틀렸다면 어떻게 되었을까요?

생각해 보기 2: 처음 가 보는 도시라 인터넷도 지도도 쓸 수 없다면 두 방법 중 어느 쪽밖에 쓸 수 없을까요?

스스로 확인

정보 이용 탐색이 유리해지려면 무엇이 먼저 갖춰져야 하나요? 그 조건이 없을 때 남는 방법은 무엇인가요?

직접 실행해 보는 탐색

탐색이 노드를 확장하는 순서를 눈으로 따라가 볼까?

시뮬레이터를 조작하며 위에서 배운 차이를 직접 확인해 보세요.

너비 우선 · 깊이 우선 탐색

맹목적 탐색 두 가지가 노드를 확장하는 순서 차이를 나란히 확인하기

휴리스틱 탐색

점수를 어림값만 · 지금까지 온 비용만 · 둘을 더한 값으로 바꿔 가며 찾는 순서와 찾은 길이 어떻게 달라지는지 확인하기

헷갈리기 쉬운 점

Q. 정보 이용 탐색은 언제나 맹목적 탐색보다 빠른가요?

A. 아니요. 휴리스틱이 얼마나 좋은지에 달려 있습니다.

휴리스틱은 목표까지 남은 거리를 추정한 값일 뿐, 정확한 값이 아닙니다. 어림값이 실제와 많이 어긋나면 엉뚱한 방향을 먼저 살펴보게 되어 오히려 맹목적 탐색보다 느려질 수도 있습니다. 정보 이용 탐색이 빠른지 느린지는 휴리스틱이 크게 좌우합니다.

Q. 그럼 정보 이용 탐색이 찾은 답은 가장 좋은 답인가요?

A. 그렇다고 볼 수 없습니다.

어림값을 따라 먼저 도착한 길일 뿐, 더 짧은 길이 옆에 있었을 수도 있습니다. A*처럼 어림값을 실제보다 크게 잡지 않도록 설계한 방법이라야 가장 짧은 경로를 보장합니다. 정보 이용 탐색은 대개 빨리 찾는 대신 가장 좋은 답이라는 보장을 내줍니다.

핵심 정리

1
지능적 탐색: 상태 공간 트리에서 다음에 확장할 노드를 정해진 원칙에 따라 골라 가며 목표까지의 경로를 찾는 것. 아래 둘을 모두 포함한다
2
맹목적 탐색(무정보 탐색): 목표가 어디인지에 대한 사전 정보 없이 정해진 순서만 따라 확장하는 방법. 너비 우선 탐색과 깊이 우선 탐색이 대표적이다
3
정보 이용 탐색(휴리스틱 탐색): 목표에 얼마나 가까운지를 추정한 값(휴리스틱)을 이용해 유망한 쪽부터 확장하는 방법. 최상 우선 탐색과 A*가 대표적이다
4
휴리스틱은 추정값이다. 빠른 대신 가장 좋은 답이라는 보장을 내준다. 가장 짧은 경로가 필요하면 조건을 갖춘 방법(간선 비용이 같을 때의 너비 우선, 어림값을 넘겨 잡지 않는 A*)을 써야 한다

확인 퀴즈

배운 내용을 확인해 봅시다.

지능적 탐색