맹목적 탐색 알고리즘
아무 단서도 없을 때, 어떤 순서로 확장해야 할까?
두 가지 대표적인 순서를 실제로 따라가 봅시다.
지능적 탐색은 두 갈래로 나뉩니다. 사전 정보를 쓰지 않고 정해진 순서만 따라 확장하는 맹목적 탐색, 그리고 목표에 얼마나 가까울지를 어림한 값을 보고 고르는 정보 이용 탐색입니다.
여기서는 그 두 갈래를 각각 대표하는 알고리즘이 실제로 어떤 순서로 움직이는지 따라가 보고, 그것으로 문제를 풀어 봅니다. 먼저 맹목적 탐색부터입니다.
깊이 우선 탐색(depth-first search, DFS)
루트 노드에서 시작하여 한 방향(분기)으로 갈 수 있을 때까지 가장 깊은 곳까지 탐색한 후, 더 이상 갈 곳이 없으면 되돌아와서 다른 방향을 탐색하는 방법입니다.
비유: 미로 찾기에서 오른손을 벽에 댄 채 끝까지 걸어가 보는 것
특징: 메모리를 적게 쓰지만, 가장 빠른 지름길을 찾는다는 보장이 없습니다.
탐색 순서: A → B → D → E → C → F → G
너비 우선 탐색(breadth-first search, BFS)
루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 같은 깊이(레벨)의 노드를 모두 탐색한 후, 다음 레벨로 넘어갑니다. 여기서 레벨은 루트 노드를 0으로 두고 자식 노드로 한 칸 내려갈 때마다 1씩 커지는 깊이를 말합니다.
비유: 잔잔한 호수에 돌을 던졌을 때, 물결이 동심원을 그리며 서서히 퍼져나가는 모습
특징: 가까운 곳부터 탐색하기 때문에 가장 적은 이동 횟수로 가는 길을 찾아냅니다. 한 번 이동하는 비용이 모두 같다면 그 길의 비용도 가장 작습니다. 대신 같은 깊이의 노드를 모두 기억해야 해서 메모리가 많이 필요합니다.
탐색 순서: A → B → C → D → E → F → G
DFS와 BFS 비교
| 구분 | 깊이 우선 탐색 (DFS) | 너비 우선 탐색 (BFS) |
|---|---|---|
| 탐색 방향 | 한 방향으로 끝까지 탐색 후 되돌아옴 | 같은 깊이를 모두 탐색 후 다음 레벨로 |
| 메모리 사용 | 적음 (현재 경로만 기억) | 많음 (같은 깊이의 모든 노드 기억) |
| 답을 찾아내는가 | 상태의 수가 유한하고 지나온 상태를 다시 확장하지 않는다면 찾아낸다 | 같은 조건에서 찾아낸다 |
| 찾은 답이 가장 짧은가 | 보장하지 않는다 | 한 번 이동하는 비용이 모두 같을 때만 보장한다 |
| 적합한 상황 | 해가 깊은 곳에 있을 때 | 해가 얕은 곳에 있을 때 |
어느 쪽이 더 빠른가는 미리 정해져 있지 않습니다
위 두 그림에서는 일곱 노드를 모두 확장했지만, 실제로는 목표를 만나는 순간 탐색을 멈춥니다. 그래서 목표가 트리의 어디에 있느냐에 따라 두 방법이 확장하는 노드 수가 달라집니다. 목표가 왼쪽 아래 깊숙한 곳에 있으면 깊이 우선 탐색이 몇 걸음 만에 닿지만, 목표가 오른쪽 위 얕은 곳에 있으면 깊이 우선 탐색은 엉뚱한 가지를 끝까지 파고든 뒤에야 되돌아옵니다.
「어느 알고리즘이 더 좋은가」라는 질문에는 답이 없습니다. 목표가 어디쯤 있을 것 같은지, 메모리가 얼마나 넉넉한지, 가장 짧은 답이 꼭 필요한지를 놓고 그때그때 고르는 것입니다.
탐구활동 · 맹목적 탐색으로 가계도 탐색해 보기
할아버지가 손주인 「나」를 찾으려고 한다. 아래 가계도를 트리로 보고, 각 탐색 방법의 방문 순서를 직접 적어 보자.
형제 노드는 왼쪽부터 살펴본다고 약속합니다. 즉 할아버지의 자식은 아버지 → 작은아버지 → 고모 순, 아버지의 자식은 나 → 여동생 순으로 확인합니다.
깊이 우선 탐색(DFS)이라면?
할아버지에서 시작해 한쪽 자녀 방향으로 끝까지 내려간 뒤 되돌아오는 순서를 적어 보자.
너비 우선 탐색(BFS)이라면?
할아버지와 같은 항렬(레벨)을 모두 확인한 뒤 다음 레벨로 넘어가는 순서를 적어 보자.
너비 우선 탐색이 「가장 짧은 답」을 찾아 준다고 말하려면 어떤 조건이 붙어야 했나요? 간선 비용이 1, 1, 5처럼 제각각인 트리라면, 너비 우선 탐색이 가장 먼저 찾은 답의 비용이 가장 작다고 말할 수 있을까요?
정보 이용 탐색 알고리즘
「이쪽이 더 가까울 것 같다」는 짐작을 숫자로 적으면?
어림한 값을 보고 다음 노드를 고르는 방법들을 살펴봅시다.
언덕 등반 탐색(Hill Climbing) 참고
눈을 가리고 산을 오를 때, 주변을 더듬어 보고 무조건 「지금보다 더 높은 곳」으로만 한 걸음씩 이동하는 방식입니다. 당장 좋아 보이는 방향으로만 움직여 계산이 빠릅니다.
최상 우선 탐색(Best-First Search)
목적지까지 「앞으로 얼마나 남았을까?」 (예상 남은 거리)만 평가해서, 가장 목적지와 가까워 보이는 길을 최우선으로 선택합니다.
A*(에이스타) 알고리즘
「지금까지 걸어온 실제 거리」와 「앞으로 남은 예상 거리」를 모두 더해서 가장 유리해 보이는 길을 선택합니다. 내비게이션의 경로 안내, 게임 속 캐릭터의 이동, 로봇의 장애물 회피처럼 지도 위에서 길을 찾는 일에 널리 쓰입니다.
g(n): 출발지로부터 「실제」 거리
h(n): 목적지까지의 「예상」 거리
최상 우선 탐색과 A* 알고리즘, 평가 함수 자세히 보기
g(n)
출발점(초기 상태)에서 현재 노드 n까지 실제로 이동한 비용(거리·횟수)입니다. 이미 지나온 길이므로 정확히 계산할 수 있습니다.
h(n)
현재 노드 n에서 목표 상태까지 남았을 것으로 추정하는 비용입니다. 아직 가보지 않았으므로 휴리스틱(어림짐작)으로 계산합니다.
f(n) = g(n) + h(n)
지금까지의 실제 비용과 앞으로의 예상 비용을 더한 값으로, 이 값이 가장 작은 노드를 다음 탐색 대상으로 선택합니다.
최상 우선 탐색은 평가 함수로 h(n)만 사용해 「목표에 가까워 보이는」 노드를 우선 선택합니다.
빠르게 목표를 향해 나아가지만, 지금까지 온 비용을 고려하지 않아 최단 경로를 보장하지 못할 수 있습니다.
A* 알고리즘은 여기에 g(n)까지 더해 f(n) = g(n) + h(n)이 가장 작은 노드를 선택합니다.
지나온 비용과 남은 비용을 모두 고려하므로, h(n)이 실제로 남은 비용을 넘겨 잡지만 않는다면
최단 경로를 찾아냅니다.
h(n)을 실제보다 크게 잡으면 A*도 최단 경로를 놓칠 수 있습니다
실제보다 작게 잡으면
가장 짧은 답은 찾아냅니다. 다만 「아직 희망이 있어 보이는」 노드가 많아져 필요 이상으로 많이 확장합니다. 답은 맞아도 시간이 더 드는 쪽입니다.
실제보다 크게 잡으면
사실은 가까운 길을 「멀겠다」고 판단해 일찌감치 제쳐 둡니다. 빨리 끝날 수는 있지만 가장 짧은 답을 놓칠 수 있습니다.
좋은 휴리스틱이란 실제 남은 비용을 넘지 않으면서 되도록 그에 가까운 값을 주는 것입니다.
휴리스틱 h(n)은 어떻게 정할까? — 대표적인 두 가지 예시
직선 거리 (유클리드 거리)
두 지점을 새가 날아가듯 일직선으로 이었을 때의 거리입니다. 내비게이션처럼 자유롭게 이동할 수 있는 실제 지도에서 남은 거리를 추정할 때 주로 사용합니다.
맨해튼 거리 참고
가로로 이동한 칸 수 + 세로로 이동한 칸 수를 더한 값입니다. 8-퍼즐이나 미로처럼 대각선 이동 없이 격자 모양으로만 움직일 수 있는 문제에서 주로 사용합니다.
2022 개정 교육과정에서는 다루지 않는 참고 자료입니다.
최상 우선 탐색과 A*는 무엇을 보고 다음 노드를 고르나요? 두 방법이 쓰는 값의 차이를 한 문장으로 적어 보세요.
평가 함수와 값이 붙은 트리
다음에 어느 노드를 확장할지, 무엇을 보고 정할까?
「정보 이용 탐색 알고리즘」 절에서 본 f(n) = g(n) + h(n)은 A*만의 식이 아닙니다. 정보 이용 탐색은 모두 노드마다 점수를 매기고 그 점수를 보고 고릅니다. 그 점수를 평가 함수라고 부릅니다.
평가 함수(evaluation function)란
평가 함수 f(n)은 「지금 후보로 올라와 있는 노드들 중에서 어느 것을 다음에 확장할까」를 정하기 위해 노드 n에 매기는 점수입니다. 여기서 다루는 평가 함수는 값이 작을수록 먼저 고릅니다. 클수록 좋은 평가 함수도 있는데, 그 이야기는 「평가 함수는 작을수록 좋은가, 클수록 좋은가?」 절에 있습니다. 방법마다 이 점수에 무엇을 넣느냐가 다를 뿐, 「점수를 매겨 고른다」는 뼈대는 같습니다.
| 방법 | 평가 함수 | 무엇을 보는가 | 고르지 않은 후보를 남겨 두는가 |
|---|---|---|---|
| 맹목적 탐색 (DFS · BFS) |
없음 | 아무것도 보지 않고 정해진 순서만 따른다 | 남겨 둔다 |
| 언덕 등반 탐색 참고 | f(n) = h(n) | 목표까지 남았을 것으로 어림한 값만 본다 | 남기지 않는다 — 되돌아갈 수 없다 |
| 최상 우선 탐색 | f(n) = h(n) | 같다 — 남은 어림값만 본다 | 남긴다 — 되돌아갈 수 있다 |
| A* 알고리즘 | f(n) = g(n) + h(n) | 걸어온 비용까지 더해서 본다 | 남긴다 |
언덕 등반 탐색과 최상 우선 탐색은 평가 함수가 같습니다. 둘을 구분하는 것은 식이 아니라 고르지 않은 후보를 남겨 두는가입니다. 언덕 등반은 한 걸음 옮기면 옆에 있던 다른 후보를 버립니다. 그래서 막다른 곳에 이르면 되돌아갈 데가 없어 거기서 멈춥니다. 앞에서 본 지역 최적해 함정이 바로 이것입니다.
값이 붙은 트리 읽는 법
지금부터 나올 트리에는 노드와 간선에 숫자가 붙습니다. 어느 숫자가 무엇인지부터 익혀 둡시다. 이것만 읽을 줄 알면 나머지는 더하기와 크기 비교뿐입니다.
- 간선 위의 숫자 — 그 간선을 한 번 지나는 데 드는 비용입니다.
- 노드 아래의 h — 그 노드에서 목표까지 남았을 것이라 어림한 값입니다. 아직 가 보지 않았으므로 어디까지나 짐작이고, 실제와 다를 수 있습니다.
- g — 출발 노드에서 그 노드까지 실제로 지나온 간선 비용의 합입니다. 부모의 g에 방금 지난 간선 비용을 더하면 됩니다.
- f — g와 h를 더한 값입니다. 위 그림에서 R은 g=1, h=2이므로 f=3입니다.
열린 목록(open list) 참고
확장해서 후보로는 올라왔지만 아직 고르지 않은 노드들의 목록입니다. 최상 우선 탐색과 A*는 매 단계 이 목록에서 f가 가장 작은 것을 하나 꺼내 확장하고, 그 자식들을 다시 목록에 넣습니다. 언덕 등반에는 이 목록이 없습니다. 이름까지 외울 필요는 없습니다. 아래 표의 「열린 목록」 칸이 무엇을 적은 것인지만 알면 됩니다.
값이 같으면 어떻게 하나요? 이 강의노트에서는 왼쪽에 있는 노드를 먼저 고른다고 약속합니다. 맹목적 탐색에서 「형제는 왼쪽부터」라고 약속했던 것과 같습니다. 실제 프로그램에서도 이런 규칙을 하나 정해 두어야 결과가 매번 같아집니다.
언덕 등반 탐색과 최상 우선 탐색은 평가 함수가 같습니다. 그런데도 결과가 달라지는 까닭은 무엇인가요?
같은 트리를 여러 방법으로 탐색해 보기
평가 함수만 바꾸면 순서가 얼마나 달라질까?
트리 세 개를 준비했습니다. 트리는 그대로 두고 평가 함수만 바꿔 가며 탐색해 봅시다. 그림이 같으니, 순서가 달라지는 까닭은 고르는 규칙 하나밖에 없습니다. (아래 숫자는 원리를 확인하려고 지어낸 값입니다.)
트리 1 — 세 방법을 나란히 따라가기
목표는 L 하나입니다. 노드 옆 초록 숫자가 h, 간선 위 파란 숫자가 이동 비용입니다.
① 언덕 등반 탐색 참고
지금 노드보다 h가 작은 자식이 있으면 그중 가장 작은 쪽으로 한 걸음 옮깁니다. 없으면 멈춥니다.
- A(h=6)의 자식은 B(2)·C(4)·D(5). 가장 작은 B(2)로 이동.
- B(h=2)의 자식은 E(3)·F(1). 더 작은 F(1)로 이동.
- F(h=1)의 자식은 K(2) 하나뿐. 1보다 작지 않으므로 갈 곳이 없습니다.
F에서 멈춥니다. 목표 L에는 닿지 못했습니다. C와 D는 아직 확장해 보지도 않았는데, 언덕 등반은 그 후보들을 남겨 두지 않아 되돌아갈 수 없습니다. 이것이 지역 최적해 함정입니다.
② 최상 우선 탐색 — f(n) = h(n)
확장한 노드의 자식을 모두 열린 목록에 넣고, 그중 h가 가장 작은 것을 꺼내 확장합니다.
| 단계 | 고른 노드 | 새로 들어온 후보 | 고른 뒤 열린 목록 |
|---|---|---|---|
| 1 | A (출발) | B(2) · C(4) · D(5) | B2 · C4 · D5 |
| 2 | B (h=2) | E(3) · F(1) | C4 · D5 · E3 · F1 |
| 3 | F (h=1) | K(2) | C4 · D5 · E3 · K2 |
| 4 | K (h=2) | 없음 (잎 노드) | C4 · D5 · E3 |
| 5 | E (h=3) | 없음 (잎 노드) | C4 · D5 |
| 6 | C (h=4) | G(5) · H(2) | D5 · G5 · H2 |
| 7 | H (h=2) | L(0) | D5 · G5 · L0 |
| 8 | L (h=0) — 목표 도달 | — | — |
확장한 노드는 A · B · F · K · E · C · H · L 여덟 개입니다. 언덕 등반이 갇혔던 F에서 되돌아 나와 목표에 닿았습니다. 다만 h(B)=2라는 어림값에 이끌려 B 쪽 가지를 한참 헤맸습니다.
③ A* 알고리즘 — f(n) = g(n) + h(n)
같은 트리에 걸어온 비용 g를 더합니다. A에서 B로 가는 데 5가 드는 것이 이제 눈에 들어옵니다.
| 단계 | 고른 노드 | 새로 들어온 후보 (g + h = f) | 고른 뒤 열린 목록 |
|---|---|---|---|
| 1 | A (출발, f=6) | B(5+2=7) · C(2+4=6) · D(3+5=8) | B7 · C6 · D8 |
| 2 | C (f=6) | G(4+5=9) · H(4+2=6) | B7 · D8 · G9 · H6 |
| 3 | H (f=6) | L(6+0=6) | B7 · D8 · G9 · L6 |
| 4 | L (f=6) — 목표 도달 | — | — |
확장한 노드는 A · C · H · L 네 개뿐입니다. B는 h가 2로 작아 「가까워 보였」지만, 거기까지 가는 비용 5를 더하니 f=7이 되어 C(f=6)에게 밀렸습니다. 어림값에 속지 않은 것은 g 덕분입니다.
세 방법이 찾아낸 길은 어떤가요? 언덕 등반은 아예 닿지 못했고, 최상 우선과 A*는 똑같이 A → C → H → L을 찾았습니다. 트리에서는 어떤 노드로 가는 길이 하나뿐이라, 목표가 하나면 찾아낸 길은 같을 수밖에 없습니다. 달라지는 것은 가는 길에 몇 개를 확장해 보았는가(8개 대 4개)입니다.
트리 2 — 직접 채워 보기
이번에는 여러분이 따라가 봅니다. 목표는 N입니다.
각 단계에서 어느 노드를 고를지만 적으면 됩니다. 열린 목록은 접힌 정답에서 확인하세요. 값이 같으면 왼쪽 노드를 먼저 고릅니다. (적은 내용은 저장되지 않습니다.)
최상 우선 탐색 — h만 본다
| 단계 | 고른 노드 |
|---|---|
| 1 | A (출발) |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 |
A* — g를 더해서 본다
| 단계 | 고른 노드 |
|---|---|
| 1 | A (출발) |
| 2 | |
| 3 | |
| 4 | |
| 5 |
정답 확인하기
최상 우선 탐색 — A · D · I · C · G · K · N (7개)
- A를 확장한다 → 열린 목록 B4 · C3 · D1 → D
- D를 확장한다 → B4 · C3 · I2 → I
- I를 확장한다 → B4 · C3 · M3 → C (M3과 같으므로 왼쪽인 C)
- C를 확장한다 → B4 · M3 · G2 · H4 → G
- G를 확장한다 → B4 · M3 · H4 · K1 · L3 → K
- K를 확장한다 → B4 · M3 · H4 · L3 · N0 → N 목표 도달
A* — A · C · G · K · N (5개)
- A를 확장한다 → B(2+4=6) · C(2+3=5) · D(5+1=6) → C
- C를 확장한다 → B6 · D6 · G(3+2=5) · H(4+4=8) → G
- G를 확장한다 → B6 · D6 · H8 · K(4+1=5) · L(4+3=7) → K
- K를 확장한다 → N(5+0=5) → N 목표 도달
최상 우선은 h(D)=1에 이끌려 D 쪽 가지를 먼저 뒤졌습니다. 하지만 A에서 D로 가는 데 5가 들기 때문에, g까지 보는 A*는 그쪽을 아예 고르지 않았습니다.
트리 3 — 목표가 둘일 때
답이 여러 개인 문제입니다. K와 L 둘 다 목표이고, 어느 쪽에 닿아도 됩니다.
트리 1에서 두 방법이 같은 길을 찾은 것은 목표가 하나뿐이었기 때문입니다. 목표가 둘이면 「어느 목표로 갈 것인가」라는 선택이 생기고, 여기서 두 방법의 결과가 달라집니다.
최상 우선 탐색 — h만 본다
- A를 확장한다 → B1 · C2 · D4 → B
- B를 확장한다 → C2 · D4 · E3 · F1 → F
- F를 확장한다 → C2 · D4 · E3 · K0 → K
찾은 답: A → B → F → K
실제로 든 비용: 4 + 1 + 1 = 6
A* — g를 더해서 본다
- A를 확장한다 → B(4+1=5) · C(1+2=3) · D(2+4=6) → C
- C를 확장한다 → B5 · D6 · G(2+3=5) · H(2+1=3) → H
- H를 확장한다 → B5 · D6 · G5 · L(3+0=3) → L
찾은 답: A → C → H → L
실제로 든 비용: 1 + 1 + 1 = 3
둘 다 세 걸음 만에 목표를 찾았지만, 답의 비용이 두 배 차이 납니다. 최상 우선은 h(B)=1만 보고 「B가 목표에 가깝다」고 판단했습니다. 맞는 말입니다 — B에서 목표까지는 정말 가깝습니다. 다만 A에서 B까지 가는 데 4가 든다는 것을 보지 않았을 뿐입니다. 「정보 이용 탐색 알고리즘」 절에서 「최상 우선은 가장 짧은 답을 보장하지 못한다」고 한 것이 이 장면입니다.
트리 3에서 최상 우선 탐색이 비싼 답을 고른 까닭을 한 문장으로 적어 보세요. 무엇을 보지 않았나요?
A*를 문제에 적용해 보기
식을 알았으니, 이제 실제로 실행해 보면 어떻게 될까?
지도 위의 길 찾기와 8-퍼즐, 두 가지 문제에 같은 방법을 써 봅시다.
① 지도에서 길 찾기 — A* 탐색의 단계별 진행
집(S)에서 도서관(G)까지 가는 길을 A*로 찾는다고 가정해 봅시다. 매 단계마다 f(n)이 가장 작은 노드를 선택해 탐색을 넓혀 갑니다. (아래 수치는 수업에서 원리를 확인하려고 지어낸 값입니다.)
길 지도 — 선 위의 숫자는 구간 거리, 노드 아래 숫자는 h(n)
S에서 A로 가는 길은 3, B로 가는 길은 4입니다. A는 지금까지 온 거리는 짧지만 목표까지 남은 거리 h가 8이나 되어 f = 3 + 8 = 11로 커집니다. 반면 B는 f = 4 + 5 = 9로 더 작아 B가 먼저 선택됩니다. C를 거쳐 G로 가면 6 + 4 = 10이지만 D를 거치면 7 + 2 = 9라서, A*는 D → G 경로를 최단으로 찾아냅니다.
| 단계 | 노드 | g(n) 실제 이동 거리 |
h(n) 목표까지 예상 거리 |
f(n)=g+h | 선택 결과 |
|---|---|---|---|---|---|
| 1 | S (출발) | 0 | 9 | 9 | 선택 → 이웃 A, B 확장 |
| 2 | A | 3 | 8 | 11 | 대기 (열린 목록) |
| 2 | B | 4 | 5 | 9 | 선택 (f 최소) → 이웃 C, D 확장 |
| 3 | C | 6 | 3 | 9 | 대기 (열린 목록) |
| 3 | D | 7 | 1 | 8 | 선택 (f 최소) → 이웃 G 확장 |
| 4 | G (목표) | 9 | 0 | 9 | 목표 도달, 탐색 종료 |
4단계에서는 G와 C의 f가 9로 같습니다. 여기서는 f가 같으면 목표인 G를 먼저 꺼낸다고 두었습니다. A는 f(n)=11로 값이 더 컸기 때문에 끝까지 선택되지 않았습니다. 이렇게 A*는 매 단계 f(n)이 가장 작은 노드부터 확인하면서, 가망이 없어 보이는 경로는 뒤로 미뤄 둡니다. 이 지도의 h(n)은 모두 실제 남은 거리를 넘겨 잡지 않았으므로, 여기서 찾은 S → B → D → G가 실제로 가장 짧은 길입니다.
이 지도에서 A는 왜 끝까지 선택되지 않았나요? f(n) 값을 비교해 설명해 보세요.
h(n)은 문제마다 달라진다
지도가 아닌 문제에서는 무엇을 어림값으로 삼을까?
② 8-퍼즐 맞추기 — 「거리」가 없는 문제에서는?
지도에서는 남은 거리가 곧 h(n)이었습니다. 그런데 탐색으로 푸는 문제가 모두 지도인 것은 아닙니다. 8-퍼즐은 3×3 판에 1부터 8까지의 타일과 빈칸이 하나 있고, 빈칸에 이웃한 타일을 빈칸 쪽으로 밀어 목표 배치를 만드는 문제입니다. 여기에는 「몇 km 남았다」고 할 만한 거리가 없습니다.
그래서 다른 어림값을 씁니다. 제자리에 있지 않은 타일이 몇 개인가를 세는 것입니다. 한 번 밀 때 타일 하나가 자리를 옮기므로, 이 값은 「적어도 이만큼은 더 밀어야 한다」는 뜻이 됩니다. 빈칸은 타일이 아니므로 세지 않습니다.
지금 배치와 목표 배치
지금 배치
제자리에 없는 타일 2개 → h = 2
목표 배치
h = 0
빈칸에 이웃한 타일은 2, 4, 5, 6 넷입니다. 즉 다음에 갈 수 있는 배치가 넷이므로, 각각의 g(지금까지 민 횟수) + h(제자리에 없는 타일 수)를 계산해 f가 가장 작은 것을 고릅니다.
5를 위로
g=1, h=1
f = 2
선택
2를 아래로
g=1, h=3
f = 4
4를 오른쪽으로
g=1, h=3
f = 4
6을 왼쪽으로
g=1, h=3
f = 4
f가 가장 작은 「5를 위로」 배치를 고릅니다. 여기서 8을 왼쪽으로 한 번 더 밀면 목표 배치가 되어 두 번 만에 끝납니다. 지도의 길 찾기와 완전히 같은 절차인데, h(n)을 무엇으로 정하느냐만 문제에 맞게 바꾼 것입니다.
이 h(n)도 넘겨 잡지 않습니다. 한 번 미는 것으로 제자리를 찾는 타일은 많아야 하나이므로, 제자리에 없는 타일 수는 남은 이동 횟수보다 클 수 없습니다. 그래서 A*가 가장 적은 횟수의 답을 찾아 줍니다.
직접 해 보는 탐색 알고리즘 실습
이론으로 배운 탐색 방법들을 시뮬레이터를 통해 직접 눈으로 확인해 보세요.
지도의 길 찾기와 8-퍼즐은 h(n)을 서로 다르게 정했습니다. 두 문제가 각각 무엇을 h(n)으로 삼았는지 적어 보세요.
탐색으로 퍼즐 풀기: 농부의 강 건너기
퍼즐 하나를 탐색으로 풀면 어떤 모습이 될까?
상태 공간 트리 위에서 알고리즘을 골라 실제로 답을 찾아 봅시다.
이 문제를 탐색으로 풀려면 먼저 상태를 무엇으로 볼지(농부·늑대·양·양배추가 각각 어느 쪽 강가에 있는가), 연산자를 무엇으로 볼지(농부가 혼자 또는 하나를 데리고 건너기)를 정해 상태 공간 트리를 그립니다.
트리를 그리는 것은 지도를 그리는 일입니다. 여기서는 그 지도 위에서 어느 노드를 먼저 확장할지 고르는 일, 즉 알고리즘을 골라 실제로 답에 닿아 봅니다.
농부가 늑대, 양, 양배추를 배에 싣고 무사히 강을 건너야 합니다.
반드시 지켜야 할 규칙
- 농부는 한 번에 한 가지만 배에 실을 수 있습니다.
- 농부가 없을 때, 늑대와 양만 남겨 두면 늑대가 양을 먹습니다.
- 농부가 없을 때, 양과 양배추만 남겨 두면 양이 양배추를 먹습니다.
인공지능의 문제 해결 과정
인공지능은 이 문제를 풀기 위해 현재 상태에서 배를 움직이는
모든 경우의 수를 트리 모양으로 그려나갑니다.
탐색 도중 규칙을 어기는 경로(예: 늑대와 양만 남는 경우)는 바로 잘라 내고,
모두 무사히 건너간 상태(목표 상태)에 도달할 때까지
끊임없이 탐색을 진행하여 정답 경로를 찾아냅니다.
이 문제에는 어떤 알고리즘이 어울릴까?
너비 우선 탐색
배가 한 번 오가는 것을 모두 똑같이 한 번으로 세므로, 얕은 쪽부터 탐색하면 가장 적은 횟수로 건너는 방법을 찾아냅니다. 상태가 열여섯 가지밖에 안 되어 메모리 부담도 없습니다.
깊이 우선 탐색
답에는 닿습니다. 다만 배를 탔다 되돌아오기를 반복하며 지나온 상태를 다시 밟을 수 있으므로, 이미 본 상태를 기억해 두어야 합니다. 찾은 답이 가장 적은 횟수라는 보장도 없습니다.
정보 이용 탐색
쓸 수는 있지만 h(n)을 정하기가 마땅치 않습니다. 「건너편에 몇이 가 있는가」로 세어 보면 답에 가까워지다가도 하나를 도로 데려와야 하는 순간이 있어, 어림값이 오히려 길을 막습니다.
좋은 어림값을 만들 수 없는 문제도 있습니다. 그럴 때는 맹목적 탐색이 오히려 자연스러운 선택입니다. 「정보 이용 탐색이 언제나 낫다」가 아니라, 문제가 어떤 정보를 내주느냐에 따라 고르는 것입니다.
헷갈리기 쉬운 점
Q. 인공지능은 세상의 모든 문제를 다 「탐색」으로 해결할 수 있나요?
A. 아니요. 탐색으로 풀 수 없는 문제도 아주 많습니다.
탐색을 하려면 문제를 [초기 상태 → 연산자(규칙) → 목표 상태]로 확실하게 정의할 수 있어야 합니다. 예를 들어 「감기에 걸린 것 같은데 병원에 가야 할까?」 같은 문제에는 출발점도 목표 상태도 없습니다. 이런 문제에는 아는 것을 규칙으로 적어 두고 거기서 새 사실을 이끌어 내는 다른 방법이 필요합니다.
인공지능이 판단하는 방법에는 탐색 / 지식의 표현과 추론 / 기계학습 세 갈래가 있습니다. 여기서 본 것은 그 가운데 탐색 하나입니다.
핵심 정리
-
1
탐색(Search): 상태 공간 트리에서 목표 상태(또는 그 상태에 이르는 경로) 찾기
-
2
맹목적 탐색(무정보 탐색): 사전 정보 없이 정해진 순서로 확장하기 (DFS: 한 갈래를 끝까지, BFS: 얕은 레벨부터). BFS는 한 번 이동하는 비용이 모두 같을 때 가장 짧은 답을 보장
-
3
정보 이용 탐색(휴리스틱 탐색): 목표에 얼마나 가까울지 어림한 값을 보고 고르기 (최상 우선 탐색은 h만, A*는 g+h). 어림값을 넘겨 잡으면 가장 짧은 답을 놓칠 수 있음
-
4
어느 쪽이 늘 낫다는 답은 없다: 목표가 어디쯤 있는지, 좋은 어림값을 만들 수 있는지에 따라 그때그때 고르는 것
늑대를 고양이로, 양을 쥐로, 양배추를 치즈로 바꾼 강 건너기 문제라면 「갈 수 없는 상태」는 어떤 경우일까요? 상태 공간 트리의 모양은 달라질까요?
평가 함수는 작을수록 좋은가, 클수록 좋은가?
평가 함수를 만들었다면 반드시 먼저 확인해야 할 것이 하나 있습니다. 이것을 놓치면 완전히 반대의 답이 나옵니다.
더 알아보기: 평가 함수의 방향(작을수록 좋은 값과 클수록 좋은 값)
「평가 함수 값이 가장 좋은 노드를 고른다」는 설명은 절반만 맞는 말입니다. 무엇이 「좋은」 것인지가 평가 함수마다 다르기 때문입니다. 같은 트리, 같은 숫자를 놓고도 방향을 잘못 잡으면 정반대의 노드를 고르게 됩니다.
작을수록 좋은 평가 함수 (비용형)
값이 손해·부담·남은 일의 양을 뜻하는 경우입니다. 0에 가까울수록 목표에 가깝습니다.
- 남은 거리 (직선거리, 맨해튼 거리)
- 남은 이동 횟수, 8-퍼즐에서 제자리에 없는 타일 수
- 걸리는 시간, 드는 요금
클수록 좋은 평가 함수 (점수형)
값이 이득·유리한 정도·일치도를 뜻하는 경우입니다. 클수록 목표에 가깝습니다.
- 오목·체스에서 내가 유리한 정도(점수)
- 8-퍼즐에서 제자리에 있는 타일 수
- 추천 시스템의 예상 만족도, 승률
같은 문제, 뒤집힌 정의 — 결과는 정반대
8-퍼즐에서 어떤 배치를 평가한다고 해 봅시다. 타일이 8개라면 두 정의는 항상 (제자리 타일 수) + (제자리에 없는 타일 수) = 8을 만족합니다. 즉 같은 정보인데 방향만 반대입니다.
| 후보 노드 | 제자리에 없는 타일 수 (작을수록 좋음) |
제자리에 있는 타일 수 (클수록 좋음) |
어느 쪽이든 선택 결과 |
|---|---|---|---|
| 가 | 5 | 3 | 선택 안 됨 |
| 나 | 2 | 6 | min으로도 max로도 「나」가 선택됨 |
| 다 | 7 | 1 | 선택 안 됨 |
정의와 선택 방향을 짝지어 맞게 쓰면 결론은 같습니다. 그러나 「제자리에 있는 타일 수」를 써 놓고 min을 적용하면 가장 나쁜 노드인 「다」를 고르게 됩니다. 방향을 확인하지 않고 식을 쓰면 이런 실수가 생깁니다.
A*의 f(n) = g(n) + h(n)이 성립하기 위한 숨은 전제
눈에 잘 띄지 않지만, 두 값을 더한다는 것은 대단히 강한 약속입니다. g(n)은 지금까지 든 비용이므로 작을수록 좋은 값입니다. 따라서 h(n)도 반드시 같은 방향(작을수록 좋음)이고 같은 단위여야 더한 f(n)이 의미를 가집니다.
올바른 조합
g = 지금까지 이동한 거리(km), h = 목표까지 남은 직선거리(km).
둘 다 작을수록 좋고 단위도 km이므로 f = g + h는 「이 길로 가면 총 몇 km쯤 될까」라는
뜻이 됩니다. 그래서 f가 가장 작은 노드를 고릅니다.
잘못된 조합
g = 지금까지 이동한 거리(km), h = 목표에 가까울수록 커지는 점수.
방향이 반대라 f = g + h는 아무 뜻도 없습니다. 목표에 가까워질수록 h가 커져
f도 커지는데, f가 작은 것을 고르면 목표에서 멀어지는 쪽을 고르게 됩니다.
고치는 방법: 점수형 휴리스틱을 꼭 써야 한다면 방향을 뒤집어 비용형으로 바꿉니다. 예를 들어 점수의 최댓값이 8이라면 h′ = 8 − h로 두면 됩니다. (8-퍼즐에서 「제자리에 있는 타일 수」를 8에서 빼면 「제자리에 없는 타일 수」가 되는 것과 같습니다.) 이렇게 방향을 맞춘 뒤에야 f = g + h′ 를 계산할 수 있습니다.
평가 함수를 만들면 이 세 가지를 점검하자
- 방향: 이 값은 작을수록 좋은가, 클수록 좋은가? → min을 쓸지 max를 쓸지가 여기서 결정된다.
- 단위: 다른 값과 더하거나 뺄 것이라면, 두 값의 단위와 방향이 같은가?
- 목표에서의 값: 목표 상태에서 h(n)이 0(비용형) 또는 최댓값(점수형)이 되는가? 그렇지 않다면 평가 함수가 목표 쪽을 제대로 가리키지 못한다. A*라면 h(목표)가 0보다 클 때 이미 실제 남은 비용(0)을 넘겨 잡은 것이다.
확인 퀴즈
배운 내용을 확인해 봅시다.